Разработка алгоритмов для вычислительной биологии: различия между версиями

В качестве иллюстрации вкратце опишем высокопроизводительный пакет программ GRAPPA (анализ перестройки генома при помощи подхода на базе экономичности и других филогенетических алгоритмов, Genome Rearrangement Analysis through Parsimony and other Phylogenetic Algorithms), разработанный Бадером и коллегами. GRAPPA расширяет алгоритм поиска точек разрывов Санкоффа и Бланшетта [10] на более информативную с биологической точки зрения инверсионную филогению, а его оптимизированный код позволяет использовать параллельные системы с распределенной и совместно используемой памятью (подробнее см. в [1, 2, 6, 7, 8, 11]). В работе [3] Бадер и коллеги предложили первый алгоритм с линейным временем выполнения и быструю реализацию для вычисления расстояния инверсии между двумя перестановками со знаками. При выполнении на кластере IBM Linux с 512 процессорами в среде Myrinet алгоритм GRAPPA обеспечил ускорение в 512 раз (линейное ускорение относительно числа процессоров). Полный анализ точек разрывов (использующий более требовательный алгоритм поиска расстояния инверсии вместо расстояния между точками разрывов) для 13 геномов из набора данных о семействе колокольчиковых (Campanulaceae) в октябре 2000 года был выполнен менее чем за 1,5 часа – '''в миллион раз''' быстрее по сравнению с первоначальной реализацией. Новая версия характеризуется значительно улучшенными границами и применением новых методов поправки на расстояние – и обеспечивает ускорение '''более чем в миллиард раз''' на том же наборе данных. Это ускорение достигается GRAPPA за счет сочетания параллелизма и высокоэффективных алгоритмов. На подобное грандиозное ускорение не всегда можно рассчитывать, однако многие алгоритмические подходы, используемые сегодня биологическими, фармацевтическими и медицинскими сообществами, могут получить значительные преимущества благодаря применению подобных высокопроизводительных техник и платформ.

* [[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)]]

* [[Сортировка перестановок со знаками при помощи обращений (последовательность обращений)]]

* [[Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5)]]