Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
AB={ab,: i=l,k>
(упорядоченность означает, что а,^ при i<j , аналогичные условия выполняются для множеств В и АВ).
Пусть р и q - перестановки элементов множеств А и В (пару lp,q) будем называть конфигурацией). Перестановки р и q задают множество: s t
R={r: г = 2 арП) или г= Е bq(1) , где 0<ssn, Ost<m>. i=l i=l
Упорядочим элементы R
R={r.: i=l,k и r\<r. при i<j)
и обозначим через AB(p,q) множество разрезов, получающихся при рассмотрении конфигурации (p,q)
AB(p,q)={ab,(p,q): ab,(p,q)=rJ-rJ_1 для некоторого l<j<k>
(мы предполагаем, что множество AB(p,q) упорядочено, т.е. abf(p,q)<abj(p,q) при i<j). Задача физического картирования состоит в отыскании конфигурации (p,q), такой, что AB=AB(p,q).
Голдстейн и Ватерман (Goldstein,Waterman,1987) показали, что даже в такой упрощенной постановке физическое картирование является NP-полной задачей (Гэри, Джонсон,1982). Таким образом, возможность построения эффективных(в смысле теории сложности Кука-Карпа) алгоритмов для физического картирования вызывает большие сомнения( известна гипотеза о том, что для NP-полных задач не существует полиномиального по сложности алгоритма решения) и основные усилия здесь следует сосредоточить на совершенствовании переборных схем.
Как уже отмечалось, при построении физических карт основными являются следующие две задачи:
1) оптимальная организация перебора гипотез о взаимном расположении сайтов;
2) Э1 фективная проверка и отбраковка гипотез о взаимном расположении се_йтов(уточнение физических карт).
©осуждавшиеся ранее проблемы отсутствия эффективных алгоритмов и относятся к задаче 1, в то время как для задачи 2 в настоящее время известны эффективные алгоритмы решения, опирающиеся, на глубокие теоретико-графовые результаты. В этом параграфе обсуждается связь проблемы физического картирования с двумя задачами дискретной оптимизации - поиском максимального потока в сети и оптимального контура в графе, для решения которых известны эффективные комбинаторные ал-
горитмы (недавно Эллисон и Йи (Al1ison,Yee,1988) предложили новый подход к уточнению физических карт, опирающийся на теорию отделения Шостака).
Гипотезы о расположении сайтов рестрикции и диаграммы. При решении задачи уточнения физических карт считается, что зафиксирована гипотеза о порядке расположения сайтов рестрикций и следовании фрагментов на молекуле ДНК. Каждой такой гипотезе соответствует диаграмма D (на рис.5.14 представлена диаграмма для линейной молекулы ДНК), на которой указаны порядок следования сайтов и соответствующие длины SD- и DD-фрагментов (при этом координаты сайтов не указываются). Физическая карта М (рис.5.14) дает информацию о порядке следования сайтов и о координатах - расстояниях каждого сайта от начальной точки. Всякая физическая карта М порождает некоторую диаграмму DM, в качестве длины фрагментов на этой диаграмме используются расстояния между между соответствующими сайтами. Однако обратное утверждение неверно: не по всякой диаграмме можно построить физическую карту, например, по диаграмме D нельзя построить физической карты, так как уже для первых двух фрагментов рестрикции В: 8+15^24. Поэтому возникает вопрос о построении физической карты, наилучшим образом приближающей диаграмму - это и есть задача уточнения физических карт.
В качестве меры расхождения между диаграммой и физической картой рассматривается равномерная норма, т.е. если длины фрагментов диаграммы представлены вектором D=(d,,..., dt), а длины фрагментов физической карты - вектором М=(ш,,... ,mt), то под отклонением физической карты М от диаграммы D понимается
шах |d -m | i=l, t
(в векторах D и М представлены в некотором порядке длины фрагментов SD- и DD-рестрикций). Задача уточнения физической карты состоит в отыскании по Диаграмме D физической карты М*. дающей решение следующей минимаксной задачи:
max |d.-m.*|=min шах Id.-m.l, i=l,t 1 1 M i=l,t 1 1
где минимум берется по всевозможным физическим картам М. Физическая карта М* называется оптимальным представлением диаграммы D (на рис.5.14 карта М - оптимальное представление диаграммы D).
Выбор равномерной нормы в большей степени соответствует реальной задаче картирования, чем, скажем, выбор евклидовой нормы I2:
( 2 (d^m,)2)1'2.
i=1,t 1 '
Дело в том, что использование евклидовой нормы не отбраковывает ва-
рианты со значительным отклонением от экспериментальных значений на одном-двух фрагментах. Эти варианты не должны рассматриваться, так как значительные отклонения хотя бы на одном фрагменте недопустимы при построении физических карт. В приведенной модели задачи уточнения физических карт ошибки в определении размеров фрагментов считаются равными. Различные уровни ошибок в определении размеров фрагментов легко учесть внесением в эту модель дополнительных весовых коэффициентов.
