Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Если физическая карта рестрикций А и В известна, то построить по ней граф G(A,В) очень просто. При анализе совместимости вложений приходится решать обратную задачу: по графу G(A,B) восстановить физическую карту. Ватерман и Григе(Waterman,Griggs,1986) приводят теорему:
двудольный граф G(A,B) является графом рестрикционной карты тогда
и только тогда, когда он является интервальным двудольным графом
без изолированных вершин, и сводят задачу проверки совместимости вложений к известной задаче распознавания интервального графа и нахождения его интервального представления(Booth,Leuker,1976; Миркин,Родин,1977). Нужно отметить, что поиск совместимых вложений не является лимитирующим этапом при построении парных карт и подход Ватермана - Григса следует рассматривать лишь как один из многих возможных.
При проверке совместимости вместо порождения всех перестановок внутри вилки (1! вариантов, где 1- число элементов вилки) перебираются только пары крайних элементов вилок (1(1-1) вариант),так как порядок средних элементов не восстанавливается. Проверка совместимости значительно упрощается, если известно расположение фрагментов одного SD-расщепления. Эти данные могут быть получены из решения задачи о парной карте для других пар рестриктаз, скажем А и С. Следует отметить, что проверку совместимости вложений можно вести уже на этапе поиска вложений - такой подход позволяет избавиться от анализа неперспективных вложений.
О числе решений задачи физического картирования. Информации о размерах фрагментов двух SD- и одной ББ-рестрикции,как правило, недостаточно для однозначной идентификации физической карты (при реальных уровнях ошибок в определении размеров фрагментов), так как число вложений и допустимых парных физических карт резко возрастает при увеличении числа DD-фрагментов. Гольдстейн и Ватерман (Goldstein,Waterman,1987), используя субаддитивную эргодическую теорему Кингмана, показали, что число решений задачи физического картирования растет как экспонента от длины картируемой молекулы. Таким образом, для однозначной идентификации физических карт необходим еще один этап - сцепление парных карт и построение множественной физической карты.
5.4.МЕТОД ПОТЕНЦИАЛОВ ДЛЯ ПОСТРОЕНИЯ МНОЖЕСТВЕННОЙ ФИЗИЧЕСКОЙ КАРТЫ
Схема эксперимента. Представьте себе, что при построении парной физической карты получено 100 различных вариантов расположения сайтов рестриктаз А и В. Как отбросить 99 из них и выбрать единственно правильное? При множественном картировании на помощь приходит информация о парных картах АС и ВС - учет этой информации отсекает варианты, которые не согласуются с информацией о расположении сайтов А и В, полученной на основе анализа карт АС и ВС. Таким образом, при построении карты по рестриктазам А,В,С возникает задача: среди множества парных карт АВ,ВС и СА выбрать три "согласованных" и "склеить" их на одной множественной карте. В зтом разделе описываются методы проверки "согласованности” и алгоритмы "склейки" парных физических карт.
Пусть в результате эксперимента получены данные о длинах фрагментов 1 одиночных рестрикций и некоторые данные о длинах фрагментов совместных рестрикций. Сопоставим этому эксперименту схему с 1 вершинами: каждому одиночному расщеплению соответствует вершина схемы, каждому совместному расщеплению - ребро схемы, соединяющее соответствующие вершины. На рис.5.10 схема G, отвечает варианту, рассмотренному в работе Нолана и др.( Nolan et al.,1984), схема G2 - варианту из работы Полнера и др. (Polner et al.,1984), а схемы G3 и G4 - экспериментам с пятью рестриктазами. Как уже отмечалось, для однозначной идентификации физической карты необходимо достаточно большое число совместных расщеплений или, иными словами, достаточная насыщенность схемы эксперимента ребрами. Опыт решения задачи построения множественных карт показывает, что важную роль играет также вид схемы эксперимента; так, например, двусвязная схема G4 предпочтительнее односвязной схемы G3, хотя они имеют одинаковое число ребер и эксперименты по схемам G3 и G4 одинаково трудоемки.
/
G G G
1 2 3
P и с.5.10.Примеры схем экспериментов
А=1‘/Ч, 41, 18,+ 1)
№.в]=М, и/»,В}”/
А = [ЧЧ, 42, W, +1)
В = (Ч7.,ЗВ,18.в, + 1! S(Kt)=SB,
В=(Ч2,38,К,Я,+Г)
С = (5Б,Чв+1) 5(В,ЕМ8 К|В,С)=/
в=(чг,зе,в,т,*и С = 15В,Чв,+П SI В,!П = ''0, 1г(В,и) = 1
д*1Ч2,16.МЛ+’)
С* [56, 48, *1) У!В.С)=50, ir[a,i;)=l
С^15В,ЧЙ,*1) А=(ЧЧ, 47., №, + 1; «С,А).70,
Р и с.5.11.Парные физические карты, полученные по методу ветвей и границ, - для разбиений А и В (а),для разбиений В и С(б), для разбиений С и А(в)
Это замечание может быть полезным при рациональном планировании экспериментов по картированию.
Потенциалы и вращения вершин в схеме эксперимента*0. Рассмотрим эксперимент по схеме "треугольник" с тремя рестриктазами А, В, С (табл. 5.2) и кольцевой молекулой ДНК. Метод потенциалов предполагает построение на предварительном этапе всех допустимых парных физических карт (т.е. парных карт, лежащих в пределах ошибки эксперимента). Предполагается, что после построения парных физических карт (любым из известных методов) на каждом ребре схемы G построено некоторое множество парных физических карт (рис.5.11), и возникает задача их сцепления на одной множественной карте.
