Математические модели в естественнонаучном образовании. Том II. Денис Владимирович Соломатин

Чтение книги онлайн.

      Рисунок 5.12. FM-алгоритм; шаг 3.

      Теперь заменяем группы на этой последней диаграмме шаблонами ветвления, которые уже нашли ранее. Это дает рисунок 5.13.

      Последним шагом является заполнение оставшихся длин

      Рисунок 5.13. FM-алгоритм; завершение.

      Обратите внимание, что одно ребро оказалось отрицательной длины. Поскольку этого не может быть, многие на практике предпочли бы просто переопределить длину в 0. Однако, если это произойдет, то должны будем по крайней мере проверить, что отрицательная длина была близка к 0, иначе придётся беспокоиться о качестве используемых данных.

      Хотя на первый взгляд это может показаться странным, но как алгоритм Фитча-Марголиаша, так и UPGMA будут создавать точно такое же топологическое дерево при применении к набору данных. Причина этого заключается в следующем: при принятии решения о том, к каким таксонам или группам присоединиться на каждом шаге, оба метода учитывают точно такую же свернутую таблицу данных и оба выбирают пару, соответствующую наименьшей записи в таблице. Отличаться будут только метрические характеристики результирующих деревьев. Это немного подрывает надежду на то, что FM-алгоритм лучше, чем UPGMA. Хотя это может привести к лучшему метрическому дереву, но топологически оно никогда не отличается.

      Фитч и Марголиаш в 1967 году фактически предложили свой алгоритм не как самоцель, а скорее, как эвристический метод получения дерева, которое, вероятно, будет иметь определенное свойство оптимальности, о чем еще поговорим в ходе решения связанных с этим задач. Рассматриваем его здесь, как и UPGMA, в качестве шага на пути к изложению алгоритма из следующего раздела. Знакомство с UPGMA и FM-алгоритмом поможет понять более сложный метод.

      Конечно, и UPGMA, и FM-алгоритм лучше выполнять компьютерными программами, чем вручную. Тем не менее, несколько ручных расчетов необходимо выполнить, чтобы полностью понять, как функционируют методы и какие предположения в них входят.

      Хотя алгоритм Фитча-Марголиаша позволил получить неравные длины ветвей в деревьях, за это заплатили высокую цену – построенные деревья оказываются некорневыми. Однако, поскольку поиск корня часто желателен, возникает необходимость обойти этот недостаток.

      При применении любого метода филогенетического дерева, который дает некорневое дерево, может быть включен дополнительный таксон. Этот дополнительный таксон выбран так, чтобы было известно, что он более отдаленно связан с каждым из представляющих интерес таксонов, чем они связаны друг с другом, и присоединяется как внешняя группа. Например, если пытаемся связать разные виды уток СКАЧАТЬ