Разработка алгоритмов для вычислительной биологии
Ключевые слова и синонимы
Высокоэффективные подходы в вычислительной биологии
Постановка задачи
За 50 лет после открытия структуры ДНК, благодаря разработке новых техник секвенирования полного генома организмов, биология стремительно развивается в направлении вычислительной науки, подразумевающей переработку больших объемов данных. Для многих вновь возникающих задач требуются высокопроизводительные вычисления – либо для организации массового параллелизма, необходимого для решения задачи, либо для решения сложных задач оптимизации, нередко оказывающихся комбинаторными и NP-трудными. В отличие от традиционного использования суперкомьютеров для обычных численных вычислений, многие биологические задачи являются нерегулярными по своей природе, значительно более сложными для распараллеливания, а также целочисленными с использованием абстрактных структур данных.
Биологи занимаются поиском данных биомолекулярных последовательностей для последующего сравнения с другими геномами, а также потому, что их структура определяет их функцию и ведет к пониманию биохимических реакций, предотвращению и лечению болезней и, в конечном итоге, познанию механизмов жизни. На помощь вычислительной биологии приходят недавние достижения в сфере технологий и алгоритмов; результатом становится, например, возможность секвенирования коротких перекрывающихся последовательностей ДНК и реконструкции на их основе полного генома, а также распространение высокоскоростных микрочипов, генных и белковых чипов, позволяющих исследовать экспрессию генов и определять их функции. Такие технологии с высокой пропускной способностью способствовали экспоненциальному росту доступных данных о геноме.
Алгоритмы для решения задач вычислительной биологии нередко требуют применения техник параллельной обработки в силу огромных объемов данных и вычислений. Многие задачи используют алгоритмы с полиномиальным временем выполнения (например, сравнение «всех со всеми»), однако работают очень долго из-за большого количества элементов входных данных; примерами таких задач могут служить сборка полного генома или сравнение всех данных нуклеотидной последовательности гена со всеми. Другие задачи требуют высокой вычислительной мощности из-за присущей алгоритмам сложности; к ним можно отнести укладку белка и реконструкцию истории эволюции на основе молекулярных данных; эти задачи являются NP-трудными или еще более сложными и нередко нуждаются в аппроксимациях, которые также отличаются сложностью.
Применение
Реконструкция филогении: филогения представляет собой представление истории эволюции набора организмов или генов (называемых таксонами). Необходимым основанием для процесса филогенетической реконструкции является повторяющаяся дивергенция между видами или генами. Филогенетическая реконструкция обычно изображается в виде дерева, в котором современные таксоны представлены в виде листьев, а таксоны-предки – в виде внутренних вершин; ребра представляют эволюционные отношения между таксонами. Реконструкция филогении является важнейшим компонентом современных исследовательских программ в биологии и медицине (а также лингвистике). Разумеется, филогения интересует ученых и сама по себе, однако подобные техники анализа находят широкое применение в прикладных исследованиях и в коммерческой сфере. Существующие техники филогенетической реконструкции страдают высокой продолжительностью выполнения алгоритмов (а те, что работают быстро, не отличаются точностью). Проблема стоит особенно остро в случае больших наборов данных: даже наборы данных, представляющие одиночные гены, все еще вызывают трудности (в частности, в некоторых случаях анализ продолжается после двух тел вычислений на кластерах средней величины), не говоря уже о данных полного генома (таких, как состав гена и последовательность генов), порождающих еще более значительные проблемы в вычислениях – особенно на наборах данных с большим числом генов и значительной перекомпоновкой генома.
На данный момент практически любая модель видообразования и геномной эволюции, применяемая в филогенетической реконструкции, требует решения NP-трудных задач оптимизации. Наиболее широко применяются три основных класса методов. Эвристические методы (естественное следствие NP-трудности задачи) работают быстро, но не могут обеспечить гарантий качества и могут даже не обладать точно определенными критериями оптимизации – примером может служить популярный эвристический метод связывания ближайших соседей [9]. Методы оптимизации на основе критерия максимальной экономичности (maximum parsimony, MP) [4] стремятся обнаружить филогению с минимальным совокупным количеством изменений, необходимых для объяснения современных данных. И, наконец, методы оптимизации на основе критерия максимального правдоподобия (maximum likelihood, ML) [5] стремятся обнаружить филогению, которая с наибольшей вероятностью послужила основой для современных данных.
Эвристические методы работают быстро и нередко могут поспорить с оптимизационными по точности – по крайней мере, на наборах данных среднего размера. Алгоритмы на основе подхода максимальной экономичности могут потребовать экспоненциального времени, но, по крайней мере, при исследовании данных ДНК и аминокислот нередко доходят до успешного завершения на наборах данных среднего размера. Алгоритмы на основе подхода максимального правдоподобия работают очень медленно (задача точечной оценки сама по себе является трудноразрешимой), в силу чего их использование ограничивается очень малыми экземплярами, а также требуют намного больше предположений, чем алгоритмы на основе максимальной экономичности – зато они превосходят другие подходы по качеству решения при удовлетворении вышеупомянутых предположений. И MP-, и ML-анализ нередко выполняется с привлечением различных эвристик, что обеспечивает своевременное завершение вычисления и компенсацию влияния большинства неквантифицируемых эффектов на качество ответа.
В этой области разрабатывается и применяется множество высокоэффективных алгоритмов. Как и во всех других областях научных вычислений, биологи стремятся изучить конкретный набор данных и готовы потратить на это месяцы, а то и годы, а их главной целью является точное прогнозирование ветвления. Однако, поскольку сложность всех точных алгоритмов экспоненциально (или еще хуже в случае ML) растет с ростом количества таксонов, скорость вычисления остается важнейшим параметром; в противном случае наборы данных, включающие больше нескольких десятков таксонов, вообще не поддавались бы анализу.
