Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Образец для цитирования:

Сергушичев А. А., Александров А. В., Казаков С. В., Царев Ф. Н., Шалыто А. А. Совместное применение графа де Брёйна, графа перекрытий и микросборки для de novo сборки генома // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 51-57. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-51-57

Опубликована онлайн: 
25.05.2013
Язык публикации: 
русский
Рубрика: 
УДК: 
004.021

Совместное применение графа де Брёйна, графа перекрытий и микросборки для de novo сборки генома

Авторы: 
Сергушичев Алексей Александрович, Санкт-Петербургский национальный исследовательский университет информационных технологий
Александров Антон Вячеславович, Санкт-Петербургский национальный исследовательский университет информационных технологий
Казаков Сергей Владимирович, Санкт-Петербургский национальный исследовательский университет информационных технологий
Царев Федор Николаевич, Санкт-Петербургский национальный исследовательский университет информационных технологий
Шалыто Анатолий Абрамович, Санкт-Петербургский национальный исследовательский университет информационных технологий
Аннотация: 

 В работе предлагается метод сборки контигов геномных последовательностей из парных чтений. Особенностью этого метода является разбиение процесса сборки контигов на три этапа: сборка квазиконтигов из чтений, сборка контигов из квазиконтигов и микросборка. На первом из этапов используется граф де Брёйна, на втором — граф перекрытий. Описываются результаты экспериментального исследования разработанного метода на чтениях геномов бактерии E. Coli (размергенома — 4.5 миллиона нуклеотидов) и рыбы Maylandia zebra (размер генома — миллиард нуклеотидов). Преимущество разработанного метода состоит в том, что для его работы требуется существенно меньше оперативной памяти по сравнению с существующими программными средствами для сборки генома.

DOI: 
10.18500/1816-9791-2013-13-2-2-51-57
Библиографический список: 
  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).  
Краткое содержание:
(downloads: 9)
Полный текст в формате PDF:
(downloads: 11)