Максимальная парсимония. Полный перебор (exhaustive search) и branch-and-bound

В последних статьях я рассказала о том, что такое самое экономное дерево и логику его поиска (1) Метод максимально парсимонии. Ручное построение деревьев. Часть 1. (2) Метод максимальной парсимонии. Ручное построение деревьев. Часть 2. (3). Метод максимальной парсимонии. Вагнеровские деревья.

Чтобы понять то, что написано в этой статье, рекомендую сначала изучить информацию по приведенным ссылкам.

Очевидно, что вручную самое экономное дерево искать не стоит, потому что если есть алгоритм поиска, то наверняка уже есть и программы, которые его успешно применяют. И это так и есть.

Проблема только в том, что во времена, когда такие алгоритмы создавались, полный перебор (exhaustive search) было осуществить невозможно для большинства матриц на имеющейся тогда технике. И даже сейчас, обсчет средней матрицы (50 видов) на обычном компьютере скорее всего будет невозможен, поскольку компьютеру надо будет сравнить длины примерно 27 X 10^75 деревьев. То есть это 77-значное число. Добавление даже одного таксона значительно увеличивает количество возможных деревьев, и если у вас 100 таксонов, то это уже будет 33 X 10^183 деревьев. (А нужно же еще экономно развесить признаки на каждое и сравнить количество шагов!).

Эти цифры я взяла из книги Baum & Smith (2012) Tree Thinking. Авторы их привели для укорененных деревьев, но программы ищут неукорененные деревья, так что в реальности их будет чуть меньше, но не сильно. Там же написано, что на современных компьютерах полным перебором можно найти самое короткое дерево у матриц до 10 таксонов. Но не понятно, откуда они взяли эту цифру и какие временные рамки имеются в виду. Но в любом случае обсчитывать большие матрицы будет очень непростой задачей с точки зрения компьютерных мощностей.

Кто-то может сказать, что сейчас есть супер-компьютеры и сервера, так что можно загрузить всю матрицу туда и найти самое короткое дерево. Но давайте почувствуем размах проблемы. Количество живых деревьев на Земле примерно 3 X 10^12, примерное количество песчинок на Земле 75 X 10^17, примерное количество звезд по Вселенной 1 X 10^24, примерное количество электронов в мире 1 X 10^80. Так что да, идею с полным перебором для большинства случаев, похоже, нам придется отбросить.

Для того, чтобы облегчить задачу с полным перебором был придуман алгоритм, который называется Branch-and-bound (другое его название implicit enumiration). Для этого нам могут пригодиться Вагнеровские деревья. В этот раз мы по очереди добавляем таксоны к растущему дереву, и после каждого присоединения, выбираем самое короткое (это также еще называется sequential addition). Таким образом, у нас очень быстро получается какое-то субоптимальное дерево - это дерево, которое короче большинства, но не самое короткое. Есть вероятность, таким способом мы найдем и одно из самых коротких деревьев, но понять это без дополнительных действий мы не сможем.

Итак, допустим, у нас 15 таксонов, и субоптимальное дерево с у нас длиной 152. Понятно, что количество шагов у самых экономных деревьев не может быть больше этого, то есть их длина меньше или равна 152, и это объявляется верхней границей.

Далее используется факт того, что добавление таксона к растущему дереву не может уменьшить его длину. Добавление таксона может оставить длину дерева прежней, но уменьшить ее не может никогда. После этого, программа начинает уже полный перебор, и создает разные линии, в зависимости от того, куда присоединится 3ий, 4ый и последующие таксоны. Если в какой-то линии, где еще не все таксоны присоединены (например, пока только 12 присоединены), количество шагов достигает 153, то такая линия обрывается. Если в какой-то линии находится дерево с 15 таксонами, которое короче вагнеровского, например, его длина - 150, то это значение объявляется верхней границей. В последующих поисках все, что достигает 151 отметается. Таким образом, количество деревьев, которые надо перебрать, значительно уменьшается.

Я нашла две презентации в интернете, где этот алгоритм иллюстрируется в графической форме, номер 1 и номер 2.

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

Baum, D.A. & Smith, S.D. (2012) Tree Thinking. An Introduction to Phylogenetic Biology. Greenwood Village, Colorado: Robets and Company Publishers.