Образец для цитирования:
Сергушичев А. А., Александров А. ., Казаков С. В., Царев Ф. Н., Шалыто . А. Совместное применение графа де Брёйна, графа перекрытий и микросборки для de novo сборки генома // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 51-57. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-51-57
Совместное применение графа де Брёйна, графа перекрытий и микросборки для de novo сборки генома
В работе предлагается метод сборки контигов геномных последовательностей из парных чтений. Особенностью этого метода является разбиение процесса сборки контигов на три этапа: сборка квазиконтигов из чтений, сборка контигов из квазиконтигов и микросборка. На первом из этапов используется граф де Брёйна, на втором — граф перекрытий. Описываются результаты экспериментального исследования разработанного метода на чтениях геномов бактерии E. Coli (размергенома — 4.5 миллиона нуклеотидов) и рыбы Maylandia zebra (размер генома — миллиард нуклеотидов). Преимущество разработанного метода состоит в том, что для его работы требуется существенно меньше оперативной памяти по сравнению с существующими программными средствами для сборки генома.
1. Illumina, Inc. URL: http://www.illumina.com/ (дата обращения : 18.05.2012).
2. Bockenhauer H.-J., Bongrratz D. ¨ Algorithmic Aspects of Bioinformatics. Berlin : Springer, 2007. 396 p.
3. Pevzner P. A. 1-Tuple DNA sequencing : computer analysis // J. Biomol. Struct. Dyn. 1989. Vol. 7. P. 63–73.
4. Zerbino D. R., Birney E. Velvet : Algorithms for de novo short read assembly using de Bruijn graphs // Genome Research. 2008. Vol. 18. P. 821–829.
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. 2008. Vol. 18. P. 810–820.
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. 2009. Vol. 19. P. 1117–1123.
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. 2010. Vol. 20. P. 265–272.
8. Pevzner P. A., Tang H., Waterman M. S. EULER : An Eulerian path approach to DNA fragment assembly // Proc. Natl. Acad. Sci. 2001. № 98. P. 9748–9753.
9. Александров А. В., Казаков С. В., Мельников С. В., Сергушичев А. А., Царев Ф. Н., Шалыто А. А. Метод исправления ошибок в наборе чтений нуклеотидной последовательности // Науч.-техн. вестн. С.-Петерб. гос. ун-та информационных технологий, механики и оптики. 2011. № 5. С. 81–84.
10. OkanoharaD., SadakaneK. Practical entropy-compressed rank/select dictionary // Computing Research Repository. 2006. URL: http://arxiv.org/abs/cs/0610001 (дата обращения : 18.05.2012).
11. Chikhi R., Rizk G. Space-efficient and exact de Bruijn graph representation based on a Bloom filter // Algorithms in Bioinformatics. 2012. P. 236–248.
12. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. СПб. : Невский диалект, 2003. 656 с.
13. The Assemblathon. URL: http://www.assemblathon.org (дата обращения : 18.05.2012).
