РЕШЕНИЕ ЗАДАЧИ СБОРКИ МОЛЕКУЛЫ ДНК НА РЕКОНФИГУРИРУЕМОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

  • А.И. Левина ООО"НИЦ супер-ЭВМ и нейрокомпьютеров"
  • Е.Е. Семерникова ООО"НИЦ супер-ЭВМ и нейрокомпьютеров"
  • Д.А. Сорокин ООО"НИЦ супер-ЭВМ и нейрокомпьютеров"
Ключевые слова: Программируемые логические интегральные схемы, реконфигурируемые вычислительные системы, сборка ДНК технологии нового поколения, ускорение вычислений

Аннотация

Статья посвящена исследованиям, направленным на поиск методов и средств реше-ния задачи сборки молекулы ДНК, обеспечивающих существенное сокращение времени вы-числений при сохранении заданной точности. Рассматривается возможность применения реконфигурируемых вычислительных систем для решения задачи ассемблирования на при-мере реализации одной из ключевых процедур в составе алгоритма сборки генома Velvet Assembler – процедуры формирования контигов VelvetH. В основе сборщика Velvet Assembler лежит метод нового поколения, предполагающий построение графа де Брюйна, что порождает в NP-полной задаче ассемблирования ДНК существенно переменную ин-тенсивность потоков данных. Поэтому, помимо традиционной для реконфигурируемых вычислительных систем технологии структурно-процедурной организации вычислений, для обеспечения принципиальной возможности решения подобных задач на реконфигурируемых вычислительных системах, применялись специальные методы синтеза параллельно-конвейерных программ. Для оценки эффективности применения реконфигурируемых вы-числительных систем была разработана параллельно-конвейерная программа сборки гено-ма из коротких чтений молекулы ДНК Staphylococcus aureus на основе процедуры VelvetН. Данные были взяты из базы данных Sequence Read Archive на сайте National Center for Bio-technology Information. Испытания данной прараллельно-конвейерной программы проводи-лись на реконфигурируемой вычислительной системе “Tertius”, построенной на базе четы-рёх программируемых логических интегральных схем Kintex UltraScale XCKU 095 производ-ства фирмы Xilinx. Применение данной реконфигурируемой вычислительной системы обеспечивает сокращение времени выполнения процедуры формирования контигов задачи ассемблирования ДНК в 24 и более раз по сравнению с существующими аналогами. Всё это позволяет сделать вывод о том, что реконфигурируемые вычислительные системы являются перспективным средством для решения задачи ассемблирования ДНК, требующим проведения дальнейших научно-технических исследований.

Литература

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, pp. 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. Romanenko K.V., Sal'nikov A.H., Alekseevskiy A.V. Parallel'nyy metod ob"edineniya rezul'tatov raboty programm po sborke genoma [Parallel method of combining the results of genome assembly programs], Vestnik YuUrGU. Seriya: Vychislitel'naya matematika i informatika [Vestnik SUSU. Series: Computational Mathematics and Computer Science], 2016, Vol. 5, No. 1, pp. 24-34. DIO: 10.14529/cmse160103.
6. Sychev A.A. Analiz genomnykh dannykh s ispol'zovaniem graficheskikh uskoriteley: magisterskaya dissertatsiya, po spetsial'nosti 09.04.01.01 «Vysokoproizvoditel'nye vychislitel'nye sistemy». Nauchnyy rukovoditel' Kuz'min D.A [Analysis of genomic data using graphics accelerators: master's thesis: Мaster thesis specialty 09.04.01.01 “High-performance computing systems”. Scientific advisor Kuzmin D.А.]. Krasnoyarsk, 2016, 42 p. Available at: http://elib.sfu-kras.ru/bitstream/handle/2311/29230/sychev_zashifrovan.pdf?sequence= 2&isAllowed=y (accessed 15 November 2018).
7. Kirilova A.A. Razrabotka algoritma netochnogo poiska chteniy v genome s primeneniem vychisleniy na videokartakh: magisterskaya dissertatsiya, po spetsial'nosti 01.03.02 «Prikladnaya matematika i informatika». Nauchnyy rukovoditel' Shalyto A.A [Development fuzzy string search algorithm of readings in the genome using computing on video cards: Mas-ter thesis, specialty 01.03.02 “Applied Mathematics and Computer Science”, scientific advisor Shalyto A.A.]. Sankt-Peterburg, 2014. pp. 45. Available at: http://is.ifmo.ru/diploma-theses/2015/master/kirillova/kirillova.pdf (accessed 15 November 2018).
8. Nazipova N.N., Isaev E.A., Kornilov V.V., Pervukhin D.V., Morozova A.A., Gorbunov A.A., Ustinin M.N. Bol'shie dannye v bioinformatike [Big data in bioinformatics], Matematicheskaya biologiya i bioinformatika [Mathematical biology and bioinformatics], 2017, No. 12:1, pp. 102-119.
9. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturno-protsedurnoy organizatsiey vychisleniy [Modular-scalable multiprocessor system with structural-procedural organization of computing]. Moscow: Yanus-K, 2003, 380 p.
10. Sorokin D.A., Dordopulo A.I. Metodika sokrashcheniya apparatnykh zatrat v slozhnykh sistemakh pri reshenii zadach s sushchestvenno-peremennoy intensivnost'yu potokov dannykh [Technique of reducing hardware costs in complex systems in solution with greatly-varying in-tensity of data flows], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 4 (129), pp. 213-219.
11. Levin I.I., Sorokin D.A., Mel'nikov A.K., Dordopulo A.I. Reshenie zadach s sushchestvenno-peremennoy intensivnost'yu potokov dannykh na rekonfiguriruemykh vy-chislitel'nykh sistemakh [Solving problems with essentially variable intensity of data flows on reconfigura-ble computing systems], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of computer and information technologies], 2012, No. 2, pp. 49-56.
12. Kalyaev A.V., Levin I.I., Semernikov E.A., Shmoylov V.I. Rekonfiguriruemye mul'tikonveyrnye vychislitel'nye struktury [Multicompany reconfigurable computing structures]. 2nd ed., by general ed. of I.A. Kalyaeva. Rostov-on-Don: Izd-vo YUNTS RAN, 2009, 344 p. ISBNN 978-5-902982-61-6.
13. Dordopulo A.I. Kalyaev I.A., Levin I.I., Semernikov E.A. Semeystvo mnogoprotsessornykh vychislitel'nykh sistem s dinamicheski perestraivaemoy arkhitekturoy [Family of multiproces-sor computer systems with dynamically reconfigurable architecture], Mnogoprotsessornye vychislitel'nye i upravlyayushchie sistemy: Materialy nauchno-tekhnicheskoy konferentsii [Multiprocessor computing and control systems. Materials of scientific and technical conference]. Taganrog, 2007, pp. 11-17.
14. Kalyaev I.A., Levin I.I., Semernikov E.A., Dordopulo A.I. Rekonfiguriruemye vychislitel'nye sistemy na osnove PLIS semeystva VERTEX-6 [Reconfigurable computing system based on FPGA family of VERTEX-6], Parallel'nye vychislitel'nye tekhnologii (PAVT’2011): Trudy mezhdunarodnoy nauchnoy konferentsii [Parallel computational technologies (PCT ' ’2011). Proceedings of the international scientific conference], 2011, pp. 203-211.
15. Raskladkin M.K. Biblioteka masshtabiruemykh interfeysov dlya rekonfiguriruemykh vychislitel'nykh sistem na osnove PLIS [Library of scalable interfaces for reconfigurable com-puting systems based on FPGA], Vysokoproizvoditel'nye parallel'nye vychisleniya na klasternykh sistemakh. Materialy devyatoy mezhdunarodnoy konferentsii-seminara [High-performance parallel computing on cluster systems: Proceedings of the ninth international con-ference seminar]. Vladimir, 2009, 438 p. ISBN 978-5-89368-958-7.
16. Dasgupta S., Papadimitriu Kh., Vazirani U. Algoritmy [Algorithms]: transl. from engl., ed. by A. Shenya. Moscow: MTSNMO, 2014, 320 p. 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. Available at: https://www.ncbi.nlm.nih.gov/ sra/SRR022823 (accessed 10 November 2018).
18. Boyko V.A. Razrabotka algoritma sborki i analiza bol'shikh genomov [Development algorithm for the assembly and analysis of big genomes], Molodoy uchenyy [Young Scientist], 2017, No. 3, pp. 27-28. Available at: https://moluch.ru/archive/137/38530/ (accessed 10 November 2018).
19. Zerbino D.R., McEwen G.K., Margulies E.H., Birney E. Pebble and rock band: heuristic reso-lution of repeats and scaffolding in the velvet short-read de novo assembler, PLoS One, 2009, No. 4 (12): e8407.
20. Alekseeva A.E., Brusnigina N.F. Vozmozhnosti i perspektivy primeneniya metodov massivnogo parallel'nogo sekvenirovaniya v diagnostike i epidemiologicheskom nadzore za infektsionnymi zabolevaniyami [Opportunities and prospects of application of methods of massive parallel sequencing in diagnostics and epidemiological surveillance of infectious dis-eases], MediAl' [Medial], 2014, No. 2 (12).
21. Levina A.I. Apparatnaya realizatsii sborki genoma iz korotkikh chteniy na osnove grafa de Bryuyna [Hardware implementation of genome Assembly from short readings based on de Bruijn graph], ХIV ezhegodnaya molodezhnaya nauchnaya konferentsiya studentov, aspirantov i molodykh uchenykh «Dostizheniya i perspektivy molodykh uchenykh v interesakh razvitiya Yuga Rossii» [XIV annual youth scientific conference of students, postgraduates and young scientists "Achievements and prospects of young scientists in the interests of development of the South of Russia"]. Rostov-on-Don, 2018, pp. 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, pp. 74-89.
Опубликован
2019-04-04
Выпуск
Раздел
РАЗДЕЛ IV. РЕКОНФИГУРИРУЕМЫЕ И НЕЙРОСЕТЕВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ