Математические модели в естественнонаучном образовании. Том II - страница 20

Шрифт
Интервал

Задачи для самостоятельного решения:

5.3.1. Перед проработкой примера, в целях более глубокого понимания метода присоединения соседей, полезно вывести формулы используемые на шаге 2 и 3 изложенного алгоритма. Предположим, что решили объединить  и  на шаге 1.

а. Покажите, что на шаге 2 расстояния от

 и
 до внутренней вершины  могут быть найдены по следующим формулам:
,
.

Затем покажите, что вторая из этих формул может быть заменена на

.

б. Покажите, что на шаге 3 расстояния от

 до , для
, могут быть вычислены с помощью формулы
.

Таблица 5.11.  Расстояния между таксонами для задачи 5.3.2











           .83         .28         .41



                         .72         .97



                                        .48

5.3.2. Рассмотрим данные о расстояниях, приведенные в таблице 5.11. Используйте алгоритм присоединения соседей для построения дерева следующим образом:

а. Вычислите

,
,
 и
, а затем заполните таблицу значений  для таксонов , ,  и .  Для начала посчитаем
 и
, получим
.

б. Если правильно справились с частью (а), то должно получиться несколько пар, имеющих одинаковое наименьшее значение

. Одним из таких наименьших значений является
, поэтому попробуем сначала присоединиться к  и .

Для новой вершины , с соединяются  и

 , вычислите
 и
 по формулам из части (a) предыдущей задачи.

в. Вычислите

 и
 по формулам из части (б) предыдущей задачи.

Поместите свои ответы в новую версию таблицы расстояний 5.12.

г. Поскольку осталось только 3 таксона, используйте 3-точечные формулы, чтобы поместить ,  и  в дерево.

д. Нарисуйте последнее дерево, присоединив  и  к  с расстояниями, найденными в части (б).

Таблица 5.12.  Групповые расстояния для задачи 5.3.2









            ?             ?



                         .72

Таблица 5.13. Расстояния таксонов для задачи 5.3.3











           .3           .4           .5



                         .5           .4



                                        .7

5.3.3. Рассмотрим данные о расстояниях в таблице 5.13, которые точно соответствуют дереву с рисунка 5.15, при

 и
.

а. Используйте UPGMA для восстановления дерева на основе этих данных. Применим ли этот метод?

б. Используйте метод присоединения соседей, чтобы восстановить дерево из этих данных. Применим ли этот метод?

5.3.4. Выполните алгоритм присоединения соседей на данных о расстояниях, используемых в примерах из раздела 5.2. Чтобы использовать MATLAB для этого в первом примере, введите массив расстояний D=[0 .45 .27 .53; 0 0 .40 .50; 0 0 0 .62; 0 0 0 0] и названия таксонов Taxa={'S1','S2','S3','S4'}, затем запрограммируйте функцию nj, реализующую построение дерева методом присоединения соседей, чтобы можно было её использовать nj(D,Taxa{:}).

Следующая страница