Рестрикционные графы и физическое картирование молекул ДНК

Abstract

Построение физических карт ДНК по данным одиночных и совместных рестрикций приводит к анализу огромного числа гипотез о взаимном расположении сайтов рестрикции. При проверке и отбраковке таких гипотез возникает задача уточнения физических карт, для решения которой вводится понятие рестрикционного графа. Это позволяет применить для физического картирования методы дискретной оптимизации и перенести основные проблемы в область построения потоковых алгоритмов. Предложенный подход отбраковывает карты со значительными отклонениями от экспериментальных данных (такие отклонения на отдельных фрагментах возможны при решении задачи методом Шредера—Блаттнера).

Побудова фізичних карт ДНК за даними одиночних і спільних рестрикцій призводить до аналізу величезного числа гіпотез про взаємне розташування сайтів рестрикції. При перевірці та відбракуванні подібних гіпотез виникає завдання уточнення фізичних карт, для вирішення якого вводиться поняття рестрикційного графа. Це дозволяє застосувати для фізичного картування методи дискретної оптимізації та перенести основні проблеми в область побудови потокових алгоритмів. Запропонований підхід відбраковує карти зі значними відхиленнями від експериментальних даних (такі відхилення на окремих фрагментах можливі при вирішенні задачі методом Шредера-Блаттнера).

DNA physical mapping concluded from the single and double restrictions analysis leads to a great variety of hypotheses about order of the sites. The concept of graph of restrictions was introduced for examination and selection of such hypotheses. It allows applying methods of discrete optimization for physical mapping and solving the major problems by maximal flow-minimum cut algorithms. This approach throws away maps with significant deviations from experimental data (such deviations on individual fragments are allowed in the Schroeder-Blattner method).