Список np-сложных задач биологии/биоинформатики

Я не эксперт в области вычислительной биологии, но мне очень интересно, и я провожу анализ больших данных с использованием R для своих собственных проектов, поэтому я постараюсь предоставить некоторую информацию.

Это ( http://www.ncbi.nlm.nih.gov/books/NBK25461/ ) отличная книга, рассказывающая обо всех грандиозных проблемах вычислительной биологии и новых областях, поэтому я определенно рекомендую просмотреть хотя бы список на страницу, если вы не хотите читать всю книгу. Для меня все это указывает на тот факт, что мы живем в эру больших данных, когда у нас есть масса данных, но понять их все, представить их в перспективе и проанализировать их таким образом, чтобы показать нам новое понимание проблем.

Вас также может заинтересовать BOINC, который реализует несколько сложных вычислительных проектов посредством краудсорсинга/сетевых вычислений ( http://boinc.berkeley.edu/projects.php ). В более теоретических аспектах, вот список нерешенных проблем ( http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics ), решение которых превзойдет наше понимание многих проблем моделирования, которые также просачиваются в биологические проблемы, хотя я Я совсем не специалист по моделированию биологических систем.

Надеюсь это поможет!

Сборка de novo

Чтобы построить геном из коротких прочтений, необходимо построить граф этих прочтений. Мы делаем это, разбивая чтения на k-меры и собирая их в граф.

В этом примере у нас есть k-мер, равный 3. Мы можем реконструировать геном, посетив каждый узел один раз, как показано на диаграмме. Это известно как гамильтонов путь.

К сожалению, построение такого пути NP-сложно. Невозможно вывести эффективный алгоритм ее решения. Вместо этого в биоинформатике мы строим эйлеров цикл, где ребро представляет собой перекрытие двух k-меров.

Это скорее длинный комментарий, чем ответ, но я подумал, что это может вас заинтересовать. Обычно нас волнует NP-трудность, потому что это означает, что мы не можем что-то сделать или решить какую-то проблему. Но это не единственный трудноразрешимый класс сложности, который должен быть важен для биологов.

Если мы переформулируем проблемы NP как проблемы оптимизации (вместо строгого определения как проблемы принятия решений), то NP-сложность обычно говорит о том, что мы не можем (в общем случае и в разумные сроки) найти глобальный оптимум. Однако во многих эволюционных условиях нас даже не волновал бы глобальный оптимум, мы были бы довольны локальным оптимумом.

Сложность поиска локальных оптимумов определяется классом сложности, известным как полиномиальный локальный поиск (PLS) . И здесь у нас также есть барьеры удивительной сложности. Например, NK-модель статических фитнес-ландшафтов Кауфмана (см. также этот пост в блоге и вопрос SE для обзора) является не только NP-трудной [Weinberger, E. (1996), "NP-completeness of Kauffman's Nk model, Tuneably Прочный фитнес-ландшафт», Рабочий документ Института Санта-Фе, 96-02-003], но также и PLS-жесткий ( Казначчеев, 2017 ; см. здесь для обзора или здесьдля итоговой работы). Это означает, что произвольная эволюционная динамика не только не может найти глобальные оптимумы, но в целом они даже не всегда могут найти локальные оптимумы на этих конечных (но экспоненциально больших) ландшафтах. Предположение, что локальная оптимальность может быть неразумным предположением даже для статических ландшафтов.