Graph Theoretical Strategies in De Novo Assembly
De novo genome assemblers assume the reference genome is unavailable, incomplete, highly fragmented, or significantly altered as in cancer tissues. Algorithms for de novo assembly have been developed to deal with and assemble a large number of short sequence reads from genome sequencing. In this rev...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9684373/ |
| _version_ | 1798024807679262720 |
|---|---|
| author | Kimia Behizadi Nafiseh Jafarzadeh Ali Iranmanesh |
| author_facet | Kimia Behizadi Nafiseh Jafarzadeh Ali Iranmanesh |
| author_sort | Kimia Behizadi |
| collection | DOAJ |
| description | De novo genome assemblers assume the reference genome is unavailable, incomplete, highly fragmented, or significantly altered as in cancer tissues. Algorithms for de novo assembly have been developed to deal with and assemble a large number of short sequence reads from genome sequencing. In this review paper, we have provided an overview of the graph-theoretical side of de novo genome assembly algorithms. We have investigated the construction of fourteen graph data structures related to OLC-based and DBG-based algorithms in order to compare and discuss their application in different assemblers. In addition, the most significant and recent genome de novo assemblers are classified according to the extensive variety of original, generalized, and specialized versions of graph data structures. |
| first_indexed | 2024-04-11T18:08:46Z |
| format | Article |
| id | doaj.art-735be4de815d434ab5c6683180c3ff77 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-11T18:08:46Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-735be4de815d434ab5c6683180c3ff772022-12-22T04:10:14ZengIEEEIEEE Access2169-35362022-01-01109328933910.1109/ACCESS.2022.31441139684373Graph Theoretical Strategies in De Novo AssemblyKimia Behizadi0Nafiseh Jafarzadeh1https://orcid.org/0000-0002-1816-2994Ali Iranmanesh2Department of Mathematics, Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, IranDepartment of Mathematics, Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, IranDepartment of Mathematics, Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, IranDe novo genome assemblers assume the reference genome is unavailable, incomplete, highly fragmented, or significantly altered as in cancer tissues. Algorithms for de novo assembly have been developed to deal with and assemble a large number of short sequence reads from genome sequencing. In this review paper, we have provided an overview of the graph-theoretical side of de novo genome assembly algorithms. We have investigated the construction of fourteen graph data structures related to OLC-based and DBG-based algorithms in order to compare and discuss their application in different assemblers. In addition, the most significant and recent genome de novo assemblers are classified according to the extensive variety of original, generalized, and specialized versions of graph data structures.https://ieeexplore.ieee.org/document/9684373/Combinatorial data structuresde-Bruijn graphde novo assembly algorithmshigh throughput sequencingoverlap graph |
| spellingShingle | Kimia Behizadi Nafiseh Jafarzadeh Ali Iranmanesh Graph Theoretical Strategies in De Novo Assembly IEEE Access Combinatorial data structures de-Bruijn graph de novo assembly algorithms high throughput sequencing overlap graph |
| title | Graph Theoretical Strategies in De Novo Assembly |
| title_full | Graph Theoretical Strategies in De Novo Assembly |
| title_fullStr | Graph Theoretical Strategies in De Novo Assembly |
| title_full_unstemmed | Graph Theoretical Strategies in De Novo Assembly |
| title_short | Graph Theoretical Strategies in De Novo Assembly |
| title_sort | graph theoretical strategies in de novo assembly |
| topic | Combinatorial data structures de-Bruijn graph de novo assembly algorithms high throughput sequencing overlap graph |
| url | https://ieeexplore.ieee.org/document/9684373/ |
| work_keys_str_mv | AT kimiabehizadi graphtheoreticalstrategiesindenovoassembly AT nafisehjafarzadeh graphtheoreticalstrategiesindenovoassembly AT aliiranmanesh graphtheoreticalstrategiesindenovoassembly |