Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.cmm.msu.ru/~Solnishko/t2_files/Protocol.doc Дата изменения: Fri May 20 18:51:32 2005 Дата индексирования: Tue Oct 2 13:11:26 2012 Кодировка: koi8-r

Построение матрицы попарных расстояний.
Программой eprotdist построил матрицу попарных расстояний ортологов
моего белка. Выходной файл назвал ortho.dist; на вопрос о методе
ответил по умолчанию.

Реконcтрукция неукоренённого дерева методом Neighbor-Joining.

Программой eneighbor реконструироавал филогенетическое дерево исходных
последовательностей. В качестве входного файла ("Distance matrix")
использовал ortho.dist. Выходные файлы назвал ortho.nj ("Output file")
и ortho_nj.tre ("Tree file"). На остальные вопросы ответил по
умолчанию (нажатием "Enter").
+------------------RHO_TREPA
!
--9---------------------RHO_BORBU
!
! +---------RHO_ECOLI
! +--2
! ! +-----------RHO_NEIGO
! +--4
! ! ! +--------RHO_RHOSH
! ! +----1
+--8 +----------RHO_RICPR
!
! +---------------------RHO_HELPJ
! !
+--7 +------------------RHO_AQUAE
! +--5
! ! ! +-------------------RHO_BACSU
+--6 +--3
! +-----------------------------------RHO_STRLI
!
+--------------------RHO_THEMA

Реконcтрукция укоренённого ультраметрического дерева методом UPGMA.

Ещё раз запустил программу eneighbor с теми же входными данными, что в
предыдущий раз, но на вопрос "Neighbor-joining" ответил "N" (то есть
"нет"; при таком ответе программа использует метод UPGMA).
+----------RHO_ECOLI
+--2
! +----------RHO_NEIGO
+--3
! ! +---------RHO_RHOSH
+--4 +---1
! ! +---------RHO_RICPR
+--5 !
! ! +----------------RHO_TREPA
+--6 !
! ! +------------------RHO_AQUAE
+--7 !
! ! +-------------------RHO_BORBU
! !
+-------9 +-------------------RHO_HELPJ
! !
! ! +--------------------RHO_THEMA
-10 +--8
! +--------------------RHO_BACSU
!
+----------------------------RHO_STRLI




Нахождение предположительного корня неукоренённого дерева.

Методом UPGMA корень выделяется между ветвями RHO_STRLI и всеми
остальными последовательносями и назван он программой 10-ым узлом. В
неукоренённом дереве, если мы поставим соответствующий корень, то он
будет находиться на одной из двух ветвей, отходящих от третьего узла,
а конкретнее, эта ветвь будет делить листья на два подмножества:
{RHO_STRLI} и {все остальные}.

Деревья неукоренённое и укоренённое, соответственно:
[pic]




Реализация алгоритма UPGMA "вручную".

| |1 |2 |3 |4 |5 |
|1 RHO_ECOLI |0.00000 |0.37576 |0.39642 |0.42160 |0.54061 |
|2 RHO_NEIGO |0.37576 |0.00000 |0.49377 |0.48740 |0.59197 |
|3 RHO_RHOSH |0.39642 |0.49377 |0.00000 |0.33211 |0.55847 |
|4 RHO_RICPR |0.42160 |0.48740 |0.33211 |0.00000 |0.61597 |
|5 RHO_TREPA |0.54061 |0.59197 |0.55847 |0.61597 |0.00000 |

По диагонали стоят нули - они соответствуют тому, что
последовательность гомологична сама себе. Если мы будем брать разные
последовательности из горизонтального и вертикального ряда и смотреть,
насколько они схожи, в ячейке пересечения, то число, которое мы там увидим,
будет отлично от нуля, что говорит о том, что последовательности не
идентичны полностью, как в первом случае. Итак, выберем из этих чисел
наименьшее (здесь надо заметить, что числа располагаются симметрично
относительно диагонали). Наименьшее число будет означать наибольшее
сходство двух гомологов. В таблице находим его, оно равно 0.33211 -
настолько вот близки между собой 3-ий и 4-ый гомологи. Ну а если они
настолько близки, то было бы разумно объединить их, вывести от одной,
неизвестной нам предковой последовательности, которую назовём k. Таким
образом, мы образовали наш первый кластер. Подсчитаем длины ветвей в нём. В
соответствии с гипотезой молекулярных часов L.Pauling, они должны быть
равны между собой, поэтому данное в матрице расстояние просто делим на два:

d(4,k)=d(3,k)=d(3,4)/2=0.33211/2=0.166055.

Тогда исходная матрица преобразуется в таковую следующего вида:

| |1 |2 |3,4 |5 |
|1 RHO_ECOLI |0.00000 |0.37576 |0.40901 |0.54061 |
|2 RHO_NEIGO |0.37576 |0.00000 |0.490585 |0.59197 |
|3 RHO_RHOSH, |0.40901 |0.490585 |0.00000 |0.58722 |
|4 RHO_RICPR | | | | |
|5 RHO_TREPA |0.54061 |0.59197 |0.58722 |0.00000 |

Здесь мы уже видим кластер. Но! Нужно подсчитать расстояния от этого
кластера до последовательностей 1,2 и 5. Это не очень сложно, но трудоёмко:
нужно искать среднее арифметическое каждого из 1,2 и 5 с двумя гомологами
из кластера:

d(1,3or4)=[d(1,3)+d(1,4)]/2=[0.39642+0.42160]/2=0.40901,
d(2,3or4)=[d(2,3)+d(2,4)]/2=[0.49377+0.48740]/2=0.490585,
d(5,3or4)=[d(5,3)+d(5,4)]/2=[0.55847+0.61597]/2=0.58722.

Полученные значения вносим в матрицу вместо старых в соответствующих
элементах, соблюдая симметричность относительно диагонали. А теперь
повторяем операцию сначала, но на этот раз я буду короче описывать
действия. Ищем новый кластер, т.е. ищем наименьшее число в получившейся
матрице - это 0.37576, которое соответствует 1-ому и 2-ому гомологам.
Вычисляем:

d(2,m)=d(1,m)=d(1,2)/2=0.37576/2=0.18788.

Заметим только, что на сей раз предковая форма была обозвана нами m, тем
самым мы не отождествляем её с k. Тогда получаем следующую такую матрицу:

| |1,2 |3,4 |5 |
|1 RHO_ECOLI |0.00000 |0.4497975 |0.56629 |
|2 RHO_NEIGO | | | |
|3 RHO_RHOSH, |0.4497975 |0.00000 |0.58722 |
|4 RHO_RICPR | | | |
|5 RHO_TREPA |0.56629 |0.58722 |0.00000 |

На этот раз работы остаётся поменьше: надо вычислить расстояния от
кластера {1,2} до кластера {3,4} и последовательности 5 (последовательности
обозначены цифрами только для краткости):

d(1or2,3or4)=[d(1,3)+d(1,4)+d(2,3)+d(2,4)]/4=[0.39642+0.42160+0.49377+0.4874
0]/4=
=0.4497975,
d(1or2,5)=[d(1,5)+d(2,5)]/2=[0.54061+0.59197]/2=0.56629.

Эти результаты уже внесены в матрицу, расположенную выше. Не забываем,
конечно, соблюдать симметричность при заполнении. Мы видим, что теперь уже
нам известно расстояние между двумя кластерами {1,2} и {3,4}, равное
0.4497975. Т.е. мы получили уже большой кластер {1,2,3,4} и одиноко стоящую
последовательность 5. Нехорошо! Надо и её включить в дерево. Для этого
вычислим длины ветвей в объединении 5 и этого самого:

d(5,1 or 2 or 3 or 4) =
[d(5,1)+d(5,2)+d(5,3)+d(5,4)]/4=[0.54061+0.59197+0.55847+0.61597]/4=0.576755


Исходя из последних данных, «перекраиваем» матрицу и получаем вот это:

| |1,2,3,4 |5 |
|1 RHO_ECOLI |0.00000 |0.576755 |
|2 RHO_NEIGO | | |
|3 RHO_RHOSH, | | |
|4 RHO_RICPR | | |
|5 RHO_TREPA |0.576755 |0.00000 |

Всё, на этом наши действия завершены и можно строить дерево! В
топологическом виде получаем: (((3,4),(1,2)),5). Теперь мы здесь цифры
заменим на настоящие названия: (((RHO_RHOSH, RHO_RICPR),( RHO_ECOLI,
RHO_NEIGO)), RHO_TREPA). Остаётся только написать цифры - длины ветвей. В
традициях графов - это длина ребра висячей вершины. Обязательно нужно
учесть, что мы вычисляли в нашем дереве, или графе расстояние между
висячими точками, т.е. полный путь. Поэтому при построении ветвей дерева
нужно вычитать. Итак, напишем:
(((RHO_RHOSH:0.166055,RHO_RICPR:0.166055):0.05884375,(RHO_ECOLI:0.18788,RHO_
NEIGO:0.18788):0.03701875):0.06347875,RHO_TREPA:0.2883775);. Хотите
визуально увидеть дерево? Пожалуйста:

[pic]
Дерево неукоренённое, но корень находится где-то между 3-им узлом и
RHO_TREPA.