Вывод наименьших квадратов в филогении

Вывод наименьших квадратов в филогении генерирует филогенетическое древо, основанное нанаблюдаемая матрица парных генетических расстояний иопционально весматрица. Цель состоит в том, чтобы найти дерево, которое удовлетворяет ограничениям на расстояние каккак можно лучше.

Обычные и взвешенные наименьшие квадраты

Расхождение между наблюдаемыми попарными расстояниями $D_{ij}$и расстояния $T_{ij}$ над филогенетическим деревом (т.е. суммадлин ветвей на пути от листа $i$ листать $j$) измеряется

$S=\sum _{ij}w_{ij}(D_{ij}-T_{ij})^{2}$

где веса $w_{ij}$ зависит от используемого метода наименьших квадратов.Наименьшие квадратыПостроение дерева расстояний направлено на поиск дерева (топология и длина ветвей)с минимальным S. Это нетривиальная задача. Он предполагает поискдискретное пространство некорневых топологий двоичного дерева, размер которых экспоненциален поколичество листьев. Для n листьев существует1 • 3 • 5 • ... • (2н-3)разные топологии. Перечислить их невозможно уже для небольшогоколичество листьев. Эвристические методы поиска используются для нахождения разумногохорошая топология. Оценка S для данной топологии (которая включает в себявычисление длин ветвей) представляет собой линейную задачу наименьших квадратов .Существует несколько способов взвешивания квадратов ошибок. $(D_{ij}-T_{ij})^{2}$,в зависимости от знаний и предположений об дисперсиях наблюдаемыхрасстояния. Когда об ошибках ничего не известно или предполагается, что онинезависимо распределены и равны для всех наблюдаемых расстояний, то всегири $w_{ij}$ установлены на единицу. Это приводит к обычному наименьшемуоценка квадратов.В случае взвешенного метода наименьших квадратов ошибки предполагаются независимыми.(или их корреляции неизвестны). Учитывая независимые ошибки, конкретныйВ идеале вес должен быть установлен на величину, обратную отклонению соответствующего расстояния.оценивать. Иногда отклонения могут быть неизвестны, но ониможет быть смоделировано как функция оценок расстояния. В рейтинге Fitch иМетод Марголиаша например, предполагается, что дисперсии пропорциональны квадратурасстояния.

Обобщенные наименьшие квадраты

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

$\sum _{ij,kl}w_{ij,kl}(D_{ij}-T_{ij})(D_{kl}-T_{kl})$

где $w_{ij,kl}$ являются элементами обратной ковариационной матрицы оценок расстояния.

Вычислительная сложность

Нахождение длин дерева и ветвей, минимизирующих невязку по методу наименьших квадратов, является NP-полной задачей. Однако для данного дерева оптимальная длина ветвей может быть определена в $O(n^{2})$ время для обычных наименьших квадратов, $O(n^{3})$ время для взвешенных наименьших квадратов и $O(n^{4})$ время для обобщенного метода наименьших квадратов (с учетом обратной ковариационной матрицы ).

Внешние ссылки

• PHYLIP , свободно распространяемый пакет филогенетического анализа, содержащий реализацию взвешенного метода наименьших квадратов.
• PAUP , аналогичный пакет доступен для покупки
• Darwin — среда программирования с библиотекой функций для статистики, числовых вычислений, анализа последовательностей и филогенетического анализа.