Научная литература
booksshare.net -> Добавить материал -> Биология -> Александров А.А. -> "Компьютерный анализ генетических текстов" -> 78

Компьютерный анализ генетических текстов - Александров А.А.

Александров А.А., Александров Н.Н., Бородовский М.Ю. Компьютерный анализ генетических текстов — М.:Наука , 1990. — 267 c.
ISBN 5-02-004691-4
Скачать (прямая ссылка): komputerniyanalizgeneticheskihtextov1990.djv
Предыдущая << 1 .. 72 73 74 75 76 77 < 78 > 79 80 81 82 83 84 .. 119 >> Следующая

1) представительный рс-подграф G порождает кольцевую физическую карту тогда и только тогда, когда коциклический оператор на его вершинах определяет сдвиги и согласованности на его ребрах;
2) подграф графа G порождает линейную физическую карту тогда и только тогда, когда он является представительным.
Для поиска представительных подграфов можно использовать декомпозицию G, связанную с перебором вариантов, начиная с рестриктаз, имеющих небольшое число различных положений фрагментов (им соответствуют доли G с небольшим числом вершин).
Пример построения множественной карты. Для графа G (рис.5.12) возможны наборы расстановок SD-фрагментов: Н,=(А1( В,, С,),
Н2=(А,, В2, С,). Для подграфа Н, потенциалы и вращения р(А,)=0,
р(В,)=98, р(С,)-0, с(А,)=с(В,)=с(С,)=1 порождают сдвиги и согласованности:
s(А, В)=р(В)-р(А)=98, s(B,C)-p(C)-p(B)-40, s(C,А)=р(А)-р(С)=70, v(A,B)=v(B,C)=v(C,A)=l.
Так как эти значения совпадают с значениями на рис.5.12, то.расстановки A^Bj.C, порождают физическую карту (рис.5.13). Убедимся,
что подграф Н2 не порождает физической карты. Действительно, если бы такая карта была, то она приводила бы к равенствам:
c(A1)*c(B2)=v(A1,B2)=1, с(В2)*с(С, )=v(B2,C, )=1, с(С,)*с(A,)=v(C,,А,)=1,
откуда следует, что или с(А,)=с(В2)=с(С,)=+1, или с(А,)=с(В2)=с(С,)=-1.
В первом случае (второй случай рассматривается аналогично) разност;' потенциалов должны удовлетворять условиям (5.1):
р( А,, В2) =р(В2)-р(А, )-s(A,,B2)=98, р(В2, С, )=р(С, )-р(В2 )=s(B2,C, )=88, p(Ct, А, )=р(А,)-р(С,)=s(C,, А.)=70.
Из условия: сумма разностей потенциалов на замкнутом контуре равна
О, получаем
0=р(А,, В2)+р(В2, С,)+р(С,, A,)=256=48[raod 104].
А
Р и с.5.13. Множественная физическая карта рестрикций А, В и С
Полученное противоречие показывает, что нельзя восстановить потенциалы на графе Н2, и поэтому набор расстановок Н2 не порождает физическую карту.
Поэтапное построение физических карт. Важно отметить, что в настоящее время до проведения биологического эксперимента, как правило, бывает неизвестно, какие рестриктазы предпочтительно использовать для картирования, сколько нужно провести одиночных и совместных расщеплений, какие дополнительные биохимические методы следует прив-
лечь. Метод потенциалов предоставляет возможности для рационального планирования эксперимента, а также для поэтапного построения физических карт (Певзнер,Миронсв,1987а). Так, типична ситуация, когда построено несколько допустимых карт, однако для однозначной идентификации реальной карты экспериментального материала еще недостаточно. В этом случае на основании анализа построенных карт можно указать, какими опытами следует дополнить эксперимент, для того чтобы установить реальную физическую карту. Данные дополнительных экспериментов могут быть введены в ЭВМ для завершения расчетов. Возможности поэтапного построения физических карт особенно важны при расчете карт с большим числом сайтов, так как в этом случае перед началом расчета трудно оценить, позволят ли экспериментальные данные однозначно идентифицировать физическую карту.
5.5.ФИЗИЧЕСКОЕ КАРТИРОВАНИЕ И МЕТОДЫ ДИСКРЕТНОЙ МАТЕМАТИКИ.
УТОЧНЕНИЕ ФИЗИЧЕСКИХ КАРТ
Физическое картирование как задача дискретной оптимизации. Несмотря на то, что мы подробно обсудили алгоритмы построения физических карт, математическая постановка задачи физического картирования еще не приводилась. Эта парадоксальная ситуация связана с тем, что физическое картирование - сложная комбинаторная проблема, формулировка которой не укладывается в схемы классических задач дискретной оптимизации (в большинстве работ по физическому картированию авторы избегают четкой математической постановки этой задачи). Видимо, отсутствие четких постановок привело к тому, что основные усилия в области физического картирования направлены на совершенствование переборных схем (типа метода ветвей и границ) и различных эвристических процедур, в то время как мощный аппарат дискретной оптимизации при этом практически не используется. Несмотря на обилие алгоритмов, предложенных для физического картирования, первые теоретические оценки сложности этой задачи (в рамках теории сложности Кука-Кар-па(Гэри,Джонсон,1982)) появились лишь в 1987 г.(Goldstein, Waterman,
1987). Мы приведем одну из возможных постановок задачи физического картирования (Goldstein,Waterman,1987), надеясь, что она привлечет специалистов-математиков и позволит уяснить место физического картирования в рамках задач современной дискретной оптимизации. Постановка является упрощенной - она применима только для линейных молекул ДНК, двух рестриктаз А и В и отсутствия ошибок в измерении длин фрагментов(более общая постановка приводится Певзнером(1987)).
Исходной информацией для физического картирования являются упорядоченные множества положительных чисел:
A={as: i«l,n},
B={bf: i=l,m},
Предыдущая << 1 .. 72 73 74 75 76 77 < 78 > 79 80 81 82 83 84 .. 119 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed