DOI: 10.17586/2226-1494-2016-16-1-108-114


УДК004.9

МЕТОД ИСПРАВЛЕНИЯ ОШИБОК ВСТАВКИ И УДАЛЕНИЯ В НАБОРЕ ЧТЕНИЙ НУКЛЕОТИДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

Александров А. В., Шалыто А. А.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования: Александров А.В., Шалыто А.А. Метод исправления ошибок вставки и удаления в наборе чтений нуклеотидной последовательности // Научно-технический вестник информационных технологий, механики и оптики. 2016. Т. 16. № 1. С. 108–114.

Аннотация

Предмет исследования.Разработан метод исправления ошибок вставки и удаления в наборе геномных чтений гаплоидного организма. Приведены результаты тестирования на двух библиотеках – искусственно сгенерированном наборе чтений из генома бактерии Escherichia coli и реальной библиотеке чтений бактерии Pseudomonas stutzeri. Метод. Работа метода основана на использовании k-меров. В отличие от большинства распространенных методов исправления ошибок, k-меры используются только для поиска похожих друг на друга чтений. Для похожих чтений вычисляется строка-консенсус, которая затем используется для исправления ошибок в самих чтениях. Основные результаты. Алгоритм реализован в виде самостоятельного программного модуля. Программный модуль протестирован на реальных и синтезированных данных. Качество исправления ошибок разработанного метода выше, чем у известных современных аналогов. Для сравнения использовалась метрика N50, а также суммарная и максимальная длина контига. Практическая значимость. Разработанный метод может быть использован в связке с распространенными методами сборки генома, не приспособленными для использования с чтениями, содержащими ошибки вставки и удаления.


Ключевые слова: сборка генома, исправление ошибок, ошибки вставки и удаления

Список литературы

1. Rothberg J.M., Hinz W., Rearick T.M. et al. An integrated semiconductor device enabling non-optical ge-nome sequencing // Nature. 2011. V. 475. N 7356. P. 348–352. doi: 10.1038/nature10242
2. Bentley D.R., Balasubramanian S., Swerdlow H. et al. Accurate whole human genome sequencing using re-versible terminator chemistry // Nature. 2008. V. 456. N 7218. P. 53–59. doi: 10.1038/nature07517
3. Roach J., Boysen C., Wang K., Hood L. Pairwise end sequencing: a unified approach to genomic mapping and sequencing // Genomics. 1995. V. 26. N 2. P. 345–353. doi: 10.1016/0888-7543(95)80219-C
4. Bragg L.M., Stone G., Butler M.K., Hugenholtz P., Tyson G.W. Shining a light on dark sequencing: charac-terizing errors in ion torrent PGM data // PLOS Computational Biology. 2013. V. 9. N 4. Art. e1003031. doi: 10.1371/journal.pcbi.1003031
5. Александров А.В., Казаков С.В., Мельников С.В., Сергушичев А.А., Царев Ф.Н., Шалыто А.А. Метод исправления ошибок в наборе чтений нуклеотидной последовательности // Научно-технический вест-ник СПбГУ ИТМО. 2011. № 5 (75). С. 81–84.
6. Simpson J.T., Wong K., Jackman S.D., Schein J.E., Jones S.J.M., Birol I. ABySS: a parallel assembler for short read sequence data // Genome Research. 2009. V. 19. N 6. P. 1117–1123. doi: 10.1101/gr.089532.108
7. Kelley D.R., Schatz M.C., Salzberg S.L. Quake: quality-aware detection and correction of sequencing errors // Genome Biology. 2010. V. 11. N 11. Art. R116. doi: 10.1186/gb-2010-11-11-r116
8. Medvedev P., Scott E., Kakaradov B., Pevzner P. Error correction of high-throughput sequencing datasets with non-uniform coverage // Bioinformatics. 2011. V. 27. N 13. P. i137–i141. doi: 10.1093/bioinformatics/btr208
9. 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 whole-genome shotgun microreads // Genome Research. 2008. V. 18. N 5. P. 810–820. doi: 10.1101/gr.7337908
10. de Bruijn N.G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. V. 49. P. 758–764.
11. Pevzner P.A., Tang H., Waterman M.S. An Eulerian path approach to DNA fragment assembly // Proceed-ings of the National Academy of Sciences of the USA. 2001. V. 98. N 17. P. 9748–9753. doi: 10.1073/pnas.171285098
12. Zerbino D.R., Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs // Genome Research. 2008. V. 18. N 5. P. 821–829. doi: 10.1101/gr.074492.107
13. Riley M., Abe T., Arnaud M.B., Berlyn M.K., Blattner F.R., Chaudhuri R.R., Glasner J.D., Horiuchi T., Keseler I.M., Kosuge T., Mori H., Perna N.T., Plunkett III G., Rudd K.E., Serres M.H., Thomas G.H., Thomson N.R., Wishart D., Wanner B.L. Escherichia coli K-12: a cooperatively developed annotation snapshot-2005 // Nucleic Acids Research. 2006. V. 34. N 1. P. 1–9. doi: 10.1093/nar/gkj405
14. Chen M., Yan Y., Zhang W., Lu W., Wang J., Ping S., Lin M. Complete genome sequence of the type strain Pseudomonas stutzeri CGMCC 1.1803 // Journal of Bacteriology. 2011. V. 193. N 21. P. 6095. doi: 10.1128/JB.06061-11
15. Chevreux B., Wetter T., Suhai S. Genome sequence assembly using trace signals and additional sequence information // Computer Science and Biology: Proceedings of the German Conference on Bioinformatics (GCB). 1999. V. 99. P. 45–56.
16. Miller J.R., Koren S., Sutton G. Assembly algorithms for next-generation sequencing data // Genomics. 2010. V. 95. N 6. P. 315–327. doi: 10.1016/j.ygeno.2010.03.001
 

Информация 2001-2017 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика