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

Биологи занимаются поиском данных биомолекулярных последовательностей для последующего сравнения с другими геномами, а также потому, что их структура определяет их функцию и ведет к пониманию биохимических реакций, предотвращению и лечению болезней и, в конечном итоге, познанию механизмов жизни. На помощь вычислительной биологии приходят недавние достижения в сфере технологий и алгоритмов; результатом становится, например, возможность секвенирования коротких перекрывающихся последовательностей ДНК и реконструкции на их основе полного генома, а также распространение высокоскоростных микрочипов, генных и белковых чипов, позволяющих исследовать экспрессию генов и определять их функции. Такие технологии с высокой пропускной способностью способствовали экспоненциальному росту доступных данных о геноме.

Алгоритмы для решения задач вычислительной биологии нередко требуют применения техник параллельной обработки в силу огромных объемов данных и вычислений. Многие задачи используют алгоритмы с полиномиальным временем выполнения (например, сравнение «всех со всеми»), однако работают очень долго из-за большого количества элементов входных данных; примерами таких задач могут служить сборка полного генома или сравнение всех данных нуклеотидной последовательности гена со всеми. Другие задачи требуют высокой вычислительной мощности из-за присущей алгоритмам сложности; к ним можно отнести укладку белка и реконструкцию истории эволюции на основе молекулярных данных; эти задачи являются NP-трудными или еще более сложными и нередко нуждаются в аппроксимациях, которые также отличаются сложностью.

Реконструкция филогении: филогения представляет собой представление истории эволюции набора организмов или генов (называемых таксонами). Необходимым основанием для процесса филогенетической реконструкции является повторяющаяся дивергенция между видами или генами. Филогенетическая реконструкция обычно изображается в виде дерева, в котором современные таксоны представлены в виде листьев, а таксоны-предки – в виде внутренних вершин; ребра представляют эволюционные отношения между таксонами. Реконструкция филогении является важнейшим компонентом современных исследовательских программ в биологии и медицине (а также лингвистике). Разумеется, филогения интересует ученых и сама по себе, однако подобные техники анализа находят широкое применение в прикладных исследованиях и в коммерческой сфере. Существующие техники филогенетической реконструкции страдают высокой продолжительностью выполнения алгоритмов (а те, что работают быстро, не отличаются точностью). Проблема стоит особенно остро в случае больших наборов данных: даже наборы данных, представляющие одиночные гены, все еще вызывают трудности (в частности, в некоторых случаях анализ продолжается после двух тел вычислений на кластерах средней величины), не говоря уже о данных полного генома (таких, как состав гена и последовательность генов), порождающих еще более значительные проблемы в вычислениях – особенно на наборах данных с большим числом генов и значительной перекомпоновкой генома.