Про точные методы в парсимонии я написала в прошлый раз, и также объяснила, почему нам нужны эвристические методы. .
Эвристические методы - это методы, которые не гарантируют точного ответа, но являются достаточными для поставленной цели. Такие методы часто используются в науке.
Когда я впервые читала лекцию про парсимонию студентам, мне надо было рассказать все за 55 минут. И сделать это так, чтобы они не отключились примерно через 10 минут, когда я, собственно, дойду до эвристических методов. И я придумала такую аналогию. Двоим путешественникам надо найти самую высокую вершину горы.
Что им можно для этого сделать? Первое, что приходит на ум - это взойти на все вершины и измерить их высоту относительно других пиков. Разумеется, это займет очень много времени.
Второе, что можно сделать - это воспользоваться помощью каких-то летающих существ, к примеру, орлов, которые будут их перебрасывать с вершины на вершину. Таким образом, задача наших двух путешественников будет выполнена гораздо быстрее.
То же самое эвристические методы делают и при поиске самых экономных деревьев. Они не Нвыстраивают их все с нуля, а строят какое-то количество деревьев (например, с помощью stepwide addition), и потом путем перестроек в этих деревьях, скачут с дерево на дерево, записывая при этом их длины. Логика в том, что если мы нашли субоптимальное дерево, то, скорее всего, все деревья с похожей топологией, будут также похожей длины. И очень вероятно, что некоторые из них будут обладать еще меньшей длиной. Если в какой-то момент программа находит дерево с самой меньшей длиной на данный период анализа, то начинает искать уже более прицельно рядом. Потом (или параллельно) делает опять большой скачек, и ищет уже в другом месте.
Как такие скачки делаются? Алгоритмов довольно много, и обычно они все не описываются в учебниках. Стоит ли их все знать? Думаю, что стоит знать суть, но не надо их заучивать наизусть. Я вкратце опишу то, что знаю и дам ссылки на статьи и книги для желающих изучить материал подробнее.
В целом все эти алгоритмы основаны на обмене ветвями или branch swapping. Производится перестановка ветвей разной величины, иногда даже обмен идет половинами деревьев.
Самый простой анализ - это Nearest Neighbour Interchange (NNI). В этом случае в дереве меняются местами ближайшие ветви.
На картинке изначально B и C формируют кладу. После применения NNI, таксоны A и С поменялись местами, и теперь A и B формируют кладу.
Более масштабные "прыжки" совершаются с помощью Subtree Pruning and Regrafting (SPR) и Tree Bisection and reconnection (TBR). В алгоритме SPR одна часть дерева отрывается, и присоединяется в другом месте.
В этом примере, после применения алгоритма SPR клада (A+B+C) была оторвана, и присоединена как сестринская к кладе (F+G).
В TBR все примерно также, но при этом присоединяющая часть еще и иначе укореняется.
Как видите, корнем в кладе (C+B+A) теперь выступает С, а не A, как в начале.
На некоторых ресурсах я читала, что в алгоритме TBR дерево разделяется на более или менее равные части, однако в учебнике Kitching (1998), который обычно рекомендуется для изучения парсимонии, такой информации нет.
Следующие методы новые, и они описаны в книге Schuh & Brower (2009), а также в статьях Goloboff (1999) и Nixon (2005).
В алгоритме Tree-fusing все происходит примерно также, как и в TBR, но ветви с одинаковым составом таксонов обмениваются между двумя разными деревьями.
Sectorial search - выделяет сектор в дереве, и делает изменения уже в нем с уменьшенной матрицей. Поиск в секторах может быть произведен довольно быстро и даже с помощью branch-and-bound.
Tree-drifting - по сути тоже самое, что SPR или TBR, но при этом также могут оставляться и субоптимальные варианты, если в них мало гомоплазий (об этом подробнее позже, когда я буду обсуждать результаты анализа).
И еще есть довольно популярный алгоритм Ratchet (Island hop). Суть у него тот же - обмен ветвей. Сначала строят субоптимальное дерево с помощью вагнеровского алгоритма и начинают обмен ветвями. После этого придают больше веса некоторому количеству признаков (до 25% матрицы), и выбирают самые экономные деревья. Потом возвращают все веса признаков в прежнее состояние. И повторяют все тоже самое, но с равными весами. Потом повторяют все заново много раз. Таким образом "прыжки" совершаются на большее количество разных "островов". Автор этого метода (Nixon 2005), пишет, что с помощью такого подхода большие матрицы обсчитываются гораздо быстрее.
Взвешивание подробнее я обсужу чуть позже, это тоже может быть рутинной частью анализа. Вкратце это означает, что некоторым признакам в анализе придается больше важности, чем другим.
Обычно выбранный алгоритм (или алгоритмы) применяются много раз (для финального обсчета не менее 10 000 раз). При этом вагнеровское дерево строится каждый раз с разных таксонов, чтобы каждый раз анализ начинался с другого субоптимального дерева. После анализа, хорошая идея - повторить обсчет с теми же настройками, и убедиться, что у вас получается та же топология. Логика в том, что если хотя бы один раз не были найдены все или почти все оптимальные деревья, то результаты после двух анализов будут отличаться. Также рекомендуется повторить анализ с другими алгоритмами.
Какие алгоритмы использовать? По моему опыту 10 000 итераций с TBR обычно достаточно для обсчета относительно большой матрицы (70-80 таксонов на 80-100 признаков), анализ заканчивается за несколько минут в TNT. Tree-fusing, tree drifting, sectorial search и ratchet тоже используются часто и иногда в комбинации (например, в TNT), они позволяют быстрее закончить анализ. Как я уже написала, имеет смысл попробовать разные методы, и убедиться, что результат у вас получается одинаковый. Я обычно использую TBR в TNT, и Ratchet в Nona и результаты обычно показывают идентичные по топологии.
Goloboff, P. A. (1999). Analyzing large data sets in reasonable times: solutions for composite optima. Cladistics, 15(4), 415-428.
Kitching, I. J., Forey, P., Humphries, C., & Williams, D. (1998). Cladistics: the theory and practice of parsimony analysis (No. 11). Oxford University Press, USA.
Nixon, K. C. (1999). The parsimony ratchet, a new method for rapid parsimony analysis. Cladistics, 15(4), 407-414.
Schuh, R. T., & Brower, A. V. (2009). Biological Systematics: Principles and Applications. Comstock Pub. Associates (USA): Cornell University Press.