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

редактировать

Генерация филогенетических деревьев на основе наблюдаемой матрицы попарных генетических дистанций

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

Содержание

1 Обычный и взвешенный метод наименьших квадратов
2 Обобщенный метод наименьших квадратов
3 Вычислительная сложность
4 Внешние ссылки
5 Ссылки

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

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

S = ∑ ijwij (D ij - T ij) 2 {\ displaystyle S = \ sum _ {ij} w_ {ij} (D_ {ij} -T_ {ij}) ^ {2}}

S = \ sum _ {{ij }} w _ {{ij}} (D _ {{ij}} - T _ {{ij}}) ^ {2}

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

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

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

∑ ij, klwij, kl (D ij - T ij) (D kl ​​- T kl) {\ displaystyle \ sum _ {ij, kl} w_ {ij, kl} (D_ {ij} -T_ {ij}) (D_ {kl} -T_ {kl})}

\ sum _ {{ij, kl}} w _ {{ ij, kl}} (D _ {{ij}} - T _ {{ij}}) (D _ {{kl}} - T _ {{kl}})

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

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

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

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

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

Ссылки