Geodesic
Combining de Bruijn graphs, overlap graphs and microassembly for de novo genome assembly
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 51-57 
A. A. Sergushichev; A. V. Alexandrov; S. V. Kazakov; F. N. Tsarev; A. A. Shalyto. Combining de Bruijn graphs, overlap graphs and microassembly for de novo genome assembly. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 51-57. http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a7/
@article{ISU_2013_13_2_a7,
     author = {A. A. Sergushichev and A. V. Alexandrov and S. V. Kazakov and F. N. Tsarev and A. A. Shalyto},
     title = {Combining de {Bruijn} graphs, overlap graphs and microassembly for de novo genome assembly},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {51--57},
     year = {2013},
     volume = {13},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a7/}
}
TY  - JOUR
AU  - A. A. Sergushichev
AU  - A. V. Alexandrov
AU  - S. V. Kazakov
AU  - F. N. Tsarev
AU  - A. A. Shalyto
TI  - Combining de Bruijn graphs, overlap graphs and microassembly for de novo genome assembly
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2013
SP  - 51
EP  - 57
VL  - 13
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a7/
LA  - ru
ID  - ISU_2013_13_2_a7
ER  - 
%0 Journal Article
%A A. A. Sergushichev
%A A. V. Alexandrov
%A S. V. Kazakov
%A F. N. Tsarev
%A A. A. Shalyto
%T Combining de Bruijn graphs, overlap graphs and microassembly for de novo genome assembly
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2013
%P 51-57
%V 13
%N 2
%U http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a7/
%G ru
%F ISU_2013_13_2_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we present a method for de novo genome assembly that splits the process into three stages: quasicontig assembly; contig assembly from quasicontigs; contig postprocessing with microassembly. The first stage uses de Bruijn graph, the second one uses overlap graph. We have carried out experiments of assembling the E. Coli genome (size $\approx4.5$ Mbp) and Maylandia zebra genome (size $\approx1$ Gbp). Advantage of proposed method is a low memory consumption.

[1] Illumina, Inc., URL: , (data obrascheniya: 18.05.2012) http://www.illumina.com/

[2] Böckenhauer H.-J., Bongrratz D., Algorithmic Aspects of Bioinformatics, Springer, Berlin, 2007, 396 pp. | MR

[3] Pevzner P. A., “1-Tuple DNA sequencing: computer analysis”, J. Biomol. Struct. Dyn., 7 (1989), 63–73

[4] Zerbino D. R., Birney E., “Velvet: Algorithms for de novo short read assembly using de Bruijn graphs”, Genome Research, 18 (2008), 821–829 | DOI

[5] Butler J., MacCallum I., Kleber M., Shlyakhter I. A., Belmonte M. K., Lander E. S., Nusbaum C., Jaffe D. B., “ALLPATHS: de novo assembly of wholegenome shotgun microreads”, Genome Research, 18 (2008), 810–820 | DOI

[6] Simpson J. T., Wong K., Jackman S. D., Schein J. E., Jones S. J., Birol I., “ABySS: a parallel assembler for short read sequence data”, Genome Research, 19 (2009), 1117–1123 | DOI

[7] Li R., Zhu H., Ruan J., Qian W., Fang X., Shi Z., Li Y., Li S., Shan G., Kristiansen K., Li S., Yang H., Wang J., Wanget J., “De novo assembly of human genomes with massively parallel short read sequencing”, Genome Research, 20 (2010), 265–272 | DOI

[8] Pevzner P. A., Tang H., Waterman M. S., “EULER: An Eulerian path approach to DNA fragment assembly”, Proc. Natl. Acad. Sci., 98 (2001), 9748–9753 | DOI | MR | Zbl

[9] Aleksandrov A. V., Kazakov S. V., Melnikov S. V., Sergushichev A. A., Tsarev F. N., Shalyto A. A., “Errors Correction Method in the Readings Set of Nucleotide Sequence”, Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 5, 81–84

[10] Okanohara D., Sadakane K., Practical entropy-compressed rank/select dictionary, Computing Research Repository, 2006, (data obrascheniya: 18.05.2012), arXiv: 0610001

[11] Chikhi R., Rizk G., “Space-efficient and exact de Bruijn graph representation based on a Bloom filter”, Algorithms in Bioinformatics, Lecture Notes in Computer Science, 7534, 2012, 236–248 | DOI

[12] Gusfield D., Algorithms on String, Trees and Sequences. Computer Science and Computational Biology, Cambridge Univ. Press, 1997, 554 pp. | Zbl

[13] The Assemblathon, URL: , (data obrascheniya: 18.05.2012) http://www.assemblathon.org