Проблема построения филогенетического дерева по матрице расстояний

Рассмотрим n таксонов. Расстояние между таксоном i и j есть действительное положительное число dij которое может быть определено некоторым биостатистическим методом. Получаем действительную симметрическую матрицу

2015-02-04amoeba176x

Определение 1. Матрица D представляет метрику если

2015-02-04amoeba177x

2015-02-04amoeba178x

2015-02-04amoeba179x

Критерий того, что некоторая симметрическая матрица D является метрической матрицей можно сформуировать на языке тропической алгебраической геометрии.

Утверждение 1. Матрица D представляет метрику тогда и только тогда, когда D D = D.

Доказательство. Покажем что если выполняется D D = D, то матрица D является метрической. Тропическое умножение матриц происходит так же как и классическое, но с тропическими операциями сложения и умножения.

Пусть n = 3. Тогда D D =

2015-02-04amoeba180x

В результате умножения получаем матрицу:

2015-02-04amoeba181x

Выясним, при каких условиях D D = D. Рассмотрим элементы главной диагонали матрицы D D

2015-02-04amoeba182x

2015-02-04amoeba183x

2015-02-04amoeba184x

Это значит, что все не диагональные элементы матрицы D положительны.

Рассмотрим не диагональный элемент матрицы D D:

2015-02-04amoeba185x

2015-02-04amoeba186x

2015-02-04amoeba187x

Это значит, что для любого элемента dik, ik из матрицы D выполняется неравенство dik dij + djk, j. По определению 14 получаем что матрица D – метрическая.

Аналогичные рассуждения проводятся для матриц любой размерности n.

Определение. Матрица D есть метрика дерева если существует дерево T с n листьями помеченными, положительными длинами всех граней и расстояние от листа i до листа j равно dij для всех i,j.

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