Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Каждую расстановку из п фрагментов на кольцевой молекуле можно записать 2п способами в зависимости от того, какой фрагмент выбрать первым (п вариантов) и какое выбрать направление обхода (два варианта). Каждую такую расстановку будем записывать как набор из п+1 числа: первые п - размеры фрагментов, последнее число +1 или -1 в зависимости от направления обхода (+1 - по часовой стрелке, -1 - против часовой стрелки). Например, расстановку фрагментов рестрикции А на рис.5.7 можно записать различными способами: (44, 42,18, +1), (18, 44, 42, +1), (42, 44, 18, -1) и т.д. Канонической будем называть лексикографически максимальную из всех возможных записей (для карты на рис. 5.7 канонической записью для А будет (44,42,18,+1) ,а для В
- (42,38,8,16,+1)). Точка начала первого фрагмента в канонической
записи определяет начальную точку каждого ББ-расщепления(на рис.5.7 начальной точкой рестрикции А является граница фрагментов 44 и 18, а рестрикции В - граница фрагментов 42 и 16). Расстояние между начальными точками (при движении по часовой стрелке) определяет сдвиг s(A,B) между двумя SD-расшеплениями А и В, ориентации канонических записей рестрикций А и В определяют согласованность v(A,B):v(A,B)=+l, если канонические записи А и В одинаково ориентированы; в противном случае v(A,B)=-l (на рис.5.7 s(A,B)=98,v(A,B)=+l). Заметим, что величина s(A,B) задается с некоторым допуском, определяемым погрешностями определения размеров SD-и DD-фрагментов. Зафиксируем на молекуле некоторую точку "О" - начало отсчета (можно считать, что точка "О" является единственным участком расщепления для гипотетической рестриктазы R). Числа p(A)=s(R,A) и c(A)=v(R,A) будем называть потенциалом и вращением рестрикции А. Можно показать, что
где DL - длина молекулы (равенство в (5.1) записано с учетом ошибок, правая часть (5.1) рассматривается по модулю DL). Оператор, действу-
s(A,B)=(p(B)-p(A))’с(А) [mod DL], v(A,B)=c(A)-c(B),
(5.1)
(5.2)
В =(42 , 38 , 16 ,8 , +1)
В =(42,38,8,16,+1)
С
G =( 56 , 48 , +1)
G
G
Р и с.5.12.Преобразование графа G в мультиграф (ind(A)=l, ind(B)=2, ind(C)=l)
ющий на вершинах схемы эксперимента и определенный равенствами (5.1) и (5.2), называется коциклическим. Задача исследования аналогичных операторов часто возникает в теории графов (Lefschez,1975).
Построение множественной карты сводится к поиску представительных подграФов(,). Задачу построения множественной физической карты можно переформулировать как задачу поиска таких потенциалов р и вращений с на вершинах схемы эксперимента, которые порождают сдвиги и согласованности (по формулам (5.1) и (5.2)), совпадающие с данными, полученными на этапе поиска парных физических карт. Таким образом, при построении множественной физической карты нужно выбрать некоторые расстановки фрагментов рестрикций А, В и С и, используя формулы (5.1) и (5.2), попытаться "склеить" их на одной карте. При этом следует анализировать не все варианты расположения фрагментов: в частности, при расстановке сайтов рестрикции А можно рассматривать не все варианты, представленные в парных картах АВ , а только те, которые смогут в дальнейшем участвовать в некоторой "склейке". Для отбрасывания вариантов, которые не смогут участвовать в построении множественной физической карты, используется понятие индекса вершины.
Назовем индексом ind(A) расщепления А число канонических расстановок SD-фрагментов расщепления А, совместимых со всеми типами парных расщеплений, в которых участвует А. В примере на рис.5.И единственной допустимой расстановкой фрагментов расщепления А будет At=(44, 42, 18,+1)); следовательно, вершина А имеет индекс 1, вершина В - индекс 2, так как допустимыми являются расстановки В,=(42,38, 16, 8, +1), В2=(42, 38, 8, 16, +1), вершина С имеет
индекс 1 - расстановка С,=(56,48, *-1). Расстановка фрагментов рестрикции В (42,16,38,8,+1), присутствовавшая в парных картах ВС отбрасывается, так как она не присутствует в парных картах АВ.
Для построения множественной физической карты строится 1-дольный мультиграф G, получающийся из G размножением каждой вершины А на ind(A) вариантов. Размножим каждую вершину А схемы эксперимента на величину индекса ind(A) и в каждой из полученных вершин укажем одну расстановку SD-фрагментов расщепления А (рис.5.12). Вершины мультиграфа G соединяются дугой, если соответствующие SD-расстановки совместимы, т.е.образуют карту. Сдвиги и согласованности на этих дугах определяются сдвигами и согласованностями соответствующих парных карт.
Граф с определенными на вершинах потенциалами р и вращениями с будем называть рс-графом.Подграф Н называется представительным подграфом 1-дольного графа G, если он содержит ровно одну вершину в каждой доле G и его порожденный подграф совпадает с G. Можно показать, что существует взаимнооднозначное соответствие между кольцевыми фи-зическимим картами и представительными рс-подграфами G, у которых коциклические операторы на вершинах порождают сдвиги и согласованности на дугах (аналогичное утверждение верно для линейных карт). Следующие утверждения сводят проблему идентификации множественной карты к поиску представительных подграфов:
