Статья

Название статьи РЕШЕНИЕ ЗАДАЧИ СБОРКИ МОЛЕКУЛЫ ДНК НА РЕКОНФИГУРИРУЕМОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ
Автор А. И. Левина, Е. Е. Семерникова, Д. А. Сорокин
Рубрика РАЗДЕЛ IV. РЕКОНФИГУРИРУЕМЫЕ И НЕЙРОСЕТЕВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ
Месяц, год 08, 2018
Индекс УДК 004.273
DOI 10.23683/2311-3103-2018-8-204-212
Аннотация Статья посвящена исследованиям, направленным на поиск методов и средств решения задачи сборки молекулы ДНК, обеспечивающих существенное сокращение времени вычислений при сохранении заданной точности. Рассматривается возможность применения реконфигурируемых вычислительных систем для решения задачи ассемблирования на примере реализации одной из ключевых процедур в составе алгоритма сборки генома Velvet Assembler – процедуры формирования контигов VelvetH. В основе сборщика Velvet Assembler лежит метод нового поколения, предполагающий построение графа де Брюйна, что порождает в NP-полной задаче ассемблирования ДНК существенно переменную интенсивность потоков данных. Поэтому, помимо традиционной для реконфигурируемых вычислительных систем технологии структурно-процедурной организации вычислений, для обеспечения принципиальной возможности решения подобных задач на реконфигурируемых вычислительных системах, применялись специальные методы синтеза параллельно-конвейерных программ. Для оценки эффективности применения реконфигурируемых вычислительных систем была разработана параллельно-конвейерная программа сборки генома из коротких чтений молекулы ДНК Staphylococcus aureus на основе процедуры VelvetН. Данные были взяты из базы данных Sequence Read Archive на сайте National Center for Biotechnology Information. Испытания данной прараллельно-конвейерной программы проводились на реконфигурируемой вычислительной системе “Tertius”, построенной на базе четырёх программируемых логических интегральных схем Kintex UltraScale XCKU 095 производства фирмы Xilinx. Применение данной реконфигурируемой вычислительной системы обеспечивает сокращение времени выполнения процедуры формирования контигов задачи ассемблирования ДНК в 24 и более раз по сравнению с существующими аналогами. Всё это позволяет сделать вывод о том, что реконфигурируемые вычислительные системы являются перспективным средством для решения задачи ассемблирования ДНК, требующим проведения дальнейших научно-технических исследований.

Скачать в PDF

Ключевые слова Программируемые логические интегральные схемы; реконфигурируемые вычислительные системы; сборка ДНК технологии нового поколения; ускорение вычислений.
Библиографический список 1. Ohashi H., Hesegawa M., Wakimoto K., Miyamoto - Sato E. Next - generation technologies for multiomics approaches including interactome sequencing // BioMed Research Internat ional.
– 2015. – Vol. 2015. Article No.104209.
2. Zerbino D., Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs // Genome Research. – 2008. – Vol. 18, No. 5. – P. 821-829.
3. Ohashi H., Hesegawa M., Wakimoto K., Miyamoto - Sato E. Next - generation technologies for multiomics approaches including interactome sequencing // BioMed Research Internat ional.
– 2015. – Vol. 2015. Article No.104209.
4. Chapman J.A., Ho I., Sunkara S., Luo S., Schroth G.P., et al. Meraculous: De Novo Genome Assembly with Short Paired-End Reads. PLoS ONE 6(8)e23501. – 2011. Doi:10.1371/journal.pone.0023501.
5. Романенко К.В., Сальников A.H., Алексеевский А.В. Параллельный метод объединения результатов работы программ по сборке генома // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. – 2016. – Т. 5, № 1. – С. 24-34. DIO: 10.14529/cmse160103.
6. Сычев A.A. Анализ геномных данных с использованием графических ускорителей: магистерская диссертация, по специальности 09.04.01.01 «Высокопроизводительные вычислительные системы». Научный руководитель Кузьмин Д.А. – Красноярск, 2016. – 42 c.
– URL: http://elib.sfu-kras.ru/bitstream/handle/2311/29230/sychev_zashifrovan.pdf? sequence=2&isAllowed=y (дата обращения 15.11.2018).
7. Кирилова А.А. Разработка алгоритма неточного поиска чтений в геноме с применением вычислений на видеокартах: магистерская диссертация, по специальности 01.03.02 «Прикладная математика и информатика». Научный руководитель Шалыто А.А.
– Санкт-Петербург, 2014. – С. 45. – URL:http://is.ifmo.ru/diploma-theses/2015/master/ kirillova/kirillova.pdf (дата обращения 15.11.2018).
8. Назипова Н.Н., Исаев Е.А., Корнилов В.В., Первухин Д.В., Морозова А.А., Горбунов А.А., Устинин М.Н. Большие данные в биоинформатике // Математическая биология и биоинформатика. – 2017. – № 12:1. – С. 102-119.
9. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. – М.: Янус-К, 2003. – 380 с.
10. Сорокин Д.А., Дордопуло А.И. Методика сокращения аппаратных затрат в сложных системах при решении задач с существенно-переменной интенсивностью потоков данных // Известия ЮФУ. Технические науки. – 2012. – № 4 (129). – С. 213-219.
11. Левин И.И., Сорокин Д.А., Мельников А.К., Дордопуло А.И. Решение задач с су-щественно-переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах // Вестник компьютерных и информационных технологий.
– 2012. – № 2. – С. 49-56.
12. Каляев А.В., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейрные вычислительные структуры. – 2-е изд. перераб. и доп. / под общ. ред.
И.А. Каляева. – Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. – 344 с. ISBNN 978-5-902982-61-6.
13. Дордопуло А.И. Каляев И.А., Левин И.И., Семерников Е.А. Семейство многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой // Многопроцессорные вычислительные и управляющие системы: Материалы научно-технической конференции. – Таганрог, 2007. – С. 11-17.
14. Каляев И.А., Левин И.И., Семерников Е.А., Дордопуло А.И. Реконфигурируемые вычислительные системы на основе ПЛИС семейства VERTEX-6 // Параллельные вычислительные технологии (ПАВТ’2011): Труды международной научной конференции.
– 2011. – С. 203-211.
15. Раскладкин М.К. Библиотека масштабируемых интерфейсов для реконфигурируемых вычислительных систем на основе ПЛИС // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы девятой международной конференции-семинара. – Владимир, 2009. – 438 с. ISBN 978-5-89368-958-7.
16. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы: пер. с англ. / под ред. А. Шеня. – М.: МЦНМО, 2014. – 320 с. ISBN 978-5-4439-0236-4.
17. Illumina whole genome shotgun sequencing of genomic DNA library 'Solexa-1123' containing sample ROAD: SEQUENCING_SAMPLE:15760.0. – URL: https://www.ncbi.nlm.nih.gov/ sra/SRR022823 (дата обращения 10.11.2018).
18. Бойко В.А. Разработка алгоритма сборки и анализа больших геномов // Молодой ученый. – 2017. – № 3. – С. 27-28. – URL https://moluch.ru/archive/137/38530/ (дата обращения 10.11.2018).
19. Zerbino D.R., McEwen G.K., Margulies E.H., Birney E. Pebble and rock band: heuristic resolution of repeats and scaffolding in the velvet short-read de novo assembler // PLoS One.
– 2009. – No. 4 (12): e8407.
20. Алексеева А.Е., Бруснигина Н.Ф. Возможности и перспективы применения методов массивного параллельного секвенирования в диагностике и эпидемиологическом надзоре за инфекционными заболеваниями // МедиАль. – 2014. – № 2 (12).
21. Левина А.И. Аппаратная реализации сборки генома из коротких чтений на основе графа де Брюйна // ХIV ежегодная молодежная научная конференция студентов, аспирантов и молодых ученых «Достижения и перспективы молодых ученых в интересах развития Юга России». – Ростов-на-Дону, 2018. – С. 75.
22. Varma B.S.C., Paul K., Balakrishnan M. and Lavenier D. Hardware acceleration of de novo genome assembly // Int. J. Embedded Systems. – 2017. – Vol. 9, No. 1. – P. 74-89.

Comments are closed.