Применение теории графов в биологии и медицине

Картинка

Сети ДНК

В статье «APPLICATION OF GRAPH THEORY TO BIOLOGICAL PROBLEMS” (NAFISEH JAFARZADEHa AND ALI IRANMANESHa) предложен метод использования задачи «Гамильтонов путь» и найденных к настоящему времени подходов к ее решению для изучения ДНК.

С тех пор, как была предложена спиральная структура ДНК, были сформулированы многие проблемы, связанные с этой структурой. Одна из важных проблем заключается в том, как читать и распознать первичную структуру последовательности ДНК. Сбор фрагментов ДНК является недавно изученным методом определения того, является ли повторно собранная нить ДНК соответствующей исходной нити. Один конкретный способ реализации этого метода заключается в использовании понятий и концепций теории графов. Например, см. [1-4]. Чтобы начать теоретическую фазу применения теории графов, нужен ориентированный граф, который построен из некоторых k-длинных олигонуклеотидов. Фрагментная сборка – это восстановление строки с использованием имеющегося подмножества ее строк. В этом методе данный фрагмент ДНК (или, скорее, много его идентичных копий) разбит на несколько меньших фрагментов. Цель состоит в том, чтобы восстановить исходную строку ДНК на основе ее фрагментов. Поэтому мы имеем следующую задачу:

Для данного мультимножества фрагментов, построить наилучшую строку, содержащую каждую строку в этом мультимножестве. Строка с этим свойством называется суперстрокой мультимножества. Здесь мы хотим найти суперстроку минимальной длины, называемую кратчайшей общей суперстрокой. Математическим инструментом для моделирования проблемы является граф, отображающий перекрытия между строками в множестве F.

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