Please download to get full document.

View again

of 37
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Применение методов решения задачи о выполнимости булевой формулы для построения минимальной филогенетической сети

Category:

Industry

Publish on:

Views: 14 | Pages: 37

Extension: PDF | Download: 0

Share
Related documents
Description
Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики Факультет информационных технологий и программирования Кафедра компьютерных технологий Мельник
Transcript
Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики Факультет информационных технологий и программирования Кафедра компьютерных технологий Мельник Михаил Валерьевич Применение методов решения задачи о выполнимости булевой формулы для построения минимальной филогенетической сети Научный руководитель: аспирант кафедры КТ В. И. Ульянцев Санкт-Петербург 2015 Содержание Введение Глава 1. Обзор предметной области Основные определения Филогенетика Выполнимость булевой формулы Постановка задачи Обзор существующих методов PIRN C PIRN CH MURPAR Глава 2. Описание алгоритма Препроцессинг Перебор гибридизационного числа Кодирование булевой формулы Кодирование структуры сети Кодирование отображения вершин деревьев на вершины сети Кодирование трансляции связей «предок ребенок» деревьев в сеть Решение булевой формулы и постпроцессинг Альтернативный способ кодирования структуры сети Глава 3. Тестирование и результаты Описание экспериментов Результаты Точный алгоритм 3.2.2 Неточный алгоритм Заключение Источники Приложения Введение Построение минимальной филогенетической сети является важной задачей филогенетики. Филогенетическая сеть используется для представления эволюционных взаимосвязей между различными биологическими видами в ретикулярной модели эволюции. В ретикулярной (сетчатой) модели эволюции, в отличие от классической (древовидной) модели, присутствует горизонтальный перенос генов, а также гибридизация между видами, что не позволяет использовать более простые структуры, такие как филогенетические деревья. Филогенетические сети активно исследуются в настоящее время [1 3]. Хотя существует несколько формальных определений филогенетических сетей, в данной работе рассматриваются только гибридизационные сети [4, 5]. Исходными данными для построения гибридизационной сети является набор из нескольких филогенетических деревьев, построенных на одном и том же множестве таксонов. Каждое филогенетическое дерево представляет собой эволюционную историю какого-то гена. Деревья могут иметь различную топологию из-за наличия ретикуляций. Задача состоит в том, чтобы построить гибридизационную сеть с минимальным количеством вершин, содержащую в себе каждое из исходных деревьев как подграф. Большинство алгоритмов для построения гибридизационных сетей основаны на эвристиках и не гарантируют точный результат [6, 7]. Кроме того, многие алгоритмы не могут работать более чем с двумя деревьями. Недавно был представлен точный алгоритм, работающий с многими деревьями [8]. С точной и эвристической версией этого алгоритма, как с наиболее производительной на текущий момент, будет производиться сравнение. В данной работе представлен новый способ построения минималь- 6 ной гибридизационной сети, основанный на сведении к задаче о выполнимости булевой формулы (SAT), гарантирующий точный результат. На основе представленного алгоритма была разработана утилита PhyloSAT, решающая поставленную задачу. Исходный код утилиты доступен на GitHub (https://github.com/ctlab/phylosat). Подходы, основывающиеся на сведении к задаче SAT, успешно применяются для решения различных задач, в том числе для задач филогенетики [9], построения конечных автоматов [10] и верификации [11]. Это обусловлено тем, что современные SAT-солверы хорошо оптимизированы, и способны успешно справляться с формулами из десятков тысяч переменных за несколько минут. В ходе работы над исследованием была написана статья для международной конференции AlCoB 2015 [12]. 7 Глава 1. Обзор предметной области В данной главе приводятся необходимые определения, постановка задачи, проводится обзор существующих алгоритмов решения поставленной задачи Основные определения Введем необходимые формальные определения, которые будут использоваться в дальнейшем Филогенетика Филогенетика область биологической систематики, которая занимается идентификацией и прояснением эволюционных взаимоотношений среди разных видов жизни на Земле [13]. Филогенетическим деревом называется дерево, отражающее эволюционные взаимосвязи между различными видами или другими сущностями, имеющими общего предка [14]. В данной работе будут рассматриваться подвешенные двоичные деревья. Листья филогенетического дерева отображают таксоны, а узлы представляют из себя эволюционные события: разделение предкового вида на два независимых. Примеры филогенетических деревьев показаны на Рис Гибридизационная сеть направленный ациклический граф с выделенным корнем. Гибридизационная сеть состоит из трех типов вершин - обычных вершин, ретикулярных вершин и листьев. Обычные вершины имеют одного предка и нескольких потомков. Ретикулярные вершины имеют более одного предка и нескольких потомков. Листья имеют одного предка и не имеют потомков. В данной работе, без потери общности, будет рассматриваться упрощенная модель гибридизационной сети, в которой обыч- 8 e d c a b e b c a d e a c b d Рис. 1.1: Три филогенетических дерева над множеством таксонов {a, b, c, d, e}. b d a c e c a d b e Рис. 1.2: Возможные гибридизационные сети, для деревьев из Рис. 1.1, с двумя и тремя ретикулярными событиями соответственно. Ретикулярные вершины обозначены квадратиками. ные вершины имеют ровно двух потомков, а ретикулярные вершины имеют ровно двух предков и ровно одного потомка. Заметим, что привести произвольную гибридизационную сеть к упрощенному виду не составляет труда [6]. Примеры гибридизационных сетей показаны на Рис Гибридизационную сеть можно свести к филогенетическому дереву следующим образом: У каждой ретикулярной вершины необходимо выбрать используемого предка, а ребро ведущее к другому предку удалить. Если у ретикулярной вершины удалено ребро, ведущее в ее единственного сына, то ретикулярную вершину также следует удалить. 9 Стянуть все ребра, имеющие ровно одного предка и ровно одного потомка. Гибридизационная сеть N отображает дерево T, если существует такой способ выбора удаляемых ребер, что после стягивания получится дерево T изоморфное дереву T. При этом, вершины сети, которые остались после стягивания ребер, будем называть вершинами используемыми для отображения дерева t. Гибридизационные сети на Рис. 1.2 содержат в себе все три дерева из Рис Гибридизационным числом сети N с корнем ρ называется величина h(n) = v ρ(d (v) 1), где за d (v) обозначена входящая степень вершины v. Аналогично обозначим за d + (v) исходящую степень вершины v. Заметим, что в нашей модели значение h(n) равно количеству ретикулярных вершин. Рассмотрим множество из k филогенетических деревьев T 1, T 2,..., T k, построенных над фиксированным множеством таксонов. Сеть N min называется минимальной гибридизационной сетью, если она принадлежит множеству сетей, содержащих в себе все k деревьев, и при этом имеет наименьшее возможное гибридизационное число. Множество таксонов A называется кластером на деревьях T 1, T 2,..., T k, если в каждом дереве T i существует вершина v i, такая, что множество листьев в поддереве v i совпадает с множеством A Выполнимость булевой формулы Задача о выполнимости булевой формулы (SAT) заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной [15]. Обычно рассматриваются формулы в конъюктивной нормальной форме. SAT-солвер программа предназначенная для решения задачи вы- 10 полнимости булевой формулы Постановка задачи Задача построения минимальной гибридизационной сети заключается в том, чтобы для множества филогенетических деревьев T 1, T 2,..., T k построить минимальную гибридизационную сеть. Было показано, что даже для случая двух деревьев эта задача NPполна [16] Обзор существующих методов Часто, для решения задачи используются различные ухищрения, например расматриваются сети с различными структурные допущениями, например «galled networks» [17] или k-уровневые сети [18]. Кроме того, часто допускается, что сеть строится только по двум деревьям [19, 20]. Алгоритмы с такими допущениями рассматриваться не будут. Рассмотрим только алгоритмы, решающие поставленную задачу без допущений PIRN C Единственный алгоритм, позволяющий гарантированно находить минимальную гибридизационную сеть для произвольного количества входных деревьев. Будет использоваться для сравнения с точной версией представленного алгоритма PIRN CH Эвристическая версия алгоритма PIRN C. Не гарантирует нахождение точного решения. Будет использоваться для сравнения с неточной версией представленного алгоритма. 11 MURPAR Быстрый эвристический алгоритм основанный на сведении к задаче линейного программирования. Не гарантирует нахождения точной минимальной сети, но позиционируется как очень быстрый алгоритм для нахождения точной верхней границы гибридизационного числа. 12 Глава 2. Описание алгоритма Основная идея заключается в составлении булевой формулы для набора входных деревьев и гибридизационного числа h, которая выполнима тогда и только тогда, когда существует гибридизационная сеть N h с гибридизационным числом h, отображающая все входные деревья. Определив диапазон возможных значений гибридизационного числа, можно перебрать их все и составить формулы для фиксированных значений гибридизационного числа. В итоге, ответом на задачу будет та из выполнимых формул, которая соответствует наименьшему гибридизационному числу Препроцессинг Перед тем как приступать к непосредственному кодированию булевой формулы, применяются несколько эвристик, позволяющих разбить задачу на подзадачи, и следовательно уменьшить ее сложность. Для разбиения применяются следующие правила [9]: 1. Сокращение поддерева. Если существует поддерево, содержащееся в каждом из исходных деревьев, значит в этой части эволюционной истории не наблюдалось ретикуляций, и для ее отображения достаточно древовидной структуры. Поэтому во всех исходных деревьях следует заменить это поддерево на лист с новой меткой. После решения задачи, в готовой сети, следует заменить этот лист на исходное поддерево. 2. Сокращение кластера. Если существует кластер A, содержащийся в каждом из исходных деревьев, его также следует заменить на лист с новой меткой, а задачу построения минимальной гибридизационной сети решать для этого кластера отдельно. После решения 13 _ a b a b Рис. 2.1: Добавление фиктивного корня к дереву. задачи, следует заменить этот лист в готовой сети на сеть, являющуюся решением задачи для кластера A. Предложенный далее алгоритм предполагает, что у всех входных деревьев общий корень, но это предположение не выполняется для построенных подзадач. Поэтому следует добавить фиктивный корень ко всем деревьям в каждой из подзадач. Чтобы сохранить структуру деревьев корень добавляется вместе с новым фиктивным листом. Этот процесс проиллюстрирован на Рис После решения задачи, фиктивный корень и фиктивный лист следует удалить Перебор гибридизационного числа Для решения задачи требуется найти такое минимальное h, что будет существовать гибридизационная сеть с гибридизационным числом равным h. Существует несколько методик перебора значения h: последовательный перебор от больших значений к маленьким, от маленьких значений к большим и двоичный поиск. В рамках данной работы были реализованы все три методики. Если минимальное гибридизационное число равно h min, то, как правило, наибольшее количество вычислений потребуется для решения формулы при h = h min 1. Это обусловлено тем фактом, что найти какое-нибудь решение для солвера проще, чем, перебрав все варианты, убе- 14 диться, что решения не существует. Экспериментальные результаты подтверждают это наблюдение, и поэтому перебор от маленьких значений к большим не представляет интереса, так как его производительность значительно ниже чем у остальных методов. Результаты двоичного поиска практически повторяют результаты перебора от больших значений к маленьким, кроме случаев, в которых выполняется значительное количество проверок для значений меньших чем h min. В данной работе используется перебор от больших значений к маленьким, как наиболее производительный метод. Кроме того, было экспериментально обнаружено, что у многих из получаемых подзадач гибридизационное число мало, и времени на решение таких подзадач тратится мало, поэтому используется следующая эвристика: перед началом перебора производится попытка быстрого решения со значениями h равными 0, 1, 2 и 3. В каждом из случаев солверу выделяется одна секунда на решение. Объем вычислений можно очевидным образом сократить, если подобрать более точные границы возможных значений гибридизационного числа. Существует несколько быстрых методов, основанных на различных эвристиках и методах линейного программирования, например PIRN CH [6], RIATA-HGT [21] и MURPAR [7] Кодирование булевой формулы Обозначим исходное множество деревьев за T, множество таксонов за A, размер A за n, а предполагаемое гибридизационное число за h. Требуется построить булеву формулу, которая выполнима тогда и только тогда, когда существует сеть, с гибридизационным номером h, которая отображает все деревья из T. Для начала, заметим, что исходные деревья содержат 2n 1 вершин, а искомая сеть состоит из 2(n+k)+1 вершин, т.к. добавляется фиктивный 15 корень и фиктивный лист. Среди этих вершин n + 1 лист, k ретикулярных вершин, и n + k обычных вершин. Введем нумерацию вершин по следующим правилам: 1. Листья будут иметь номера в диапазоне [0, n]. 2. Обычные вершины будут иметь номера в диапазоне [n + 1, 2n + k]. 3. Ретикулярные вершины будут иметь номера в диапазоне [2n + k + 1, 2(n + k)]. 4. Номер любого листа или обычной вершины меньше номера ее предка. 5. У обычной вершины номер левого сына меньше номера правого сына. 6. У ретикулярной вершины номер левого предка меньше номера правого предка. Кроме того, для каждой вершины v, введем следующие обозначения: PC(v) множество возможных детей вершины v PP(v) множество возможных предков вершины v PU(v) множество вершин, которые могут находиться выше вершины v в сети А также обозначим множество листьев за L, множество ретикулярных вершин за R, а множество обычных вершин за V Кодирование структуры сети Чтобы закодировать структуру сети потребуются следующие переменные: l v,u и r v,u, где v V, u P C(v). l v,u (r v,u ) истинно тогда и только тогда, когда вершина u является левым (правым) ребенком вершины v. 16 p v,u, где v L V \{ρ}, u P P (v). p v,u истинно тогда и только тогда, когда вершина u является предком вершины v. p l v,u и p r v,u, где v R, u P P (v). p l v,u (p r v,u) истинно тогда и только тогда, когда вершина u является левым (правым) предком ретикулярной вершины v. c v,u, где v R, u P C(v). c v,u истинно тогда и только тогда, когда вершина u является ребенком ретикулярной вершины v. Всего требуется O((n + k) 2 ) переменных. Заметив, что k n, получаем оценку на количество переменных O(n 2 ). Необходимо закодировать уникальность каждой переменной, т.е. что у каждой вершины есть ровно один предок и ровно один левый и правый ребенок, и аналогичные утверждения для остальных переменных. Для этого необходимо разбить утверждение вида «ровно один» на два утверждения «хотя бы один» и «не более чем один». В дальнейшем, для обозначения утверждения «хотя бы один» будет использоваться запись ALO, а для обозначения утверждения «не более чем один» будет использоваться запись AMO. Утверждение ALO кодируется очевидным способом (на примере предков вершины v): ALO p (v) = u P P (v) Это утверждение означает, что одна из переменных, отвечающих за возможного предка вершины v истинна. Для остальных переменных утверждения «хотя бы один» записываются аналогичным образом. Суммарно потребуется O(n) утверждений ALO для всех переменных, где каждое из утверждений будет состоять из O(n) переменных. Общий размер формулы будет равен O(n 2 ). 17 p v,u Утверждение AMO можно закодировать различными способами. Самый простой способ попарное исключение (на примере предков вершины v): AMO p (v) = (p v,i p v,j ) i,j P P (v) : i j Такой метод требует O(n 2 ) утверждений для каждой переменной. Существуют более оптимальные кодирования. В частности, в данной работе использовалось кодирование Bimander [22], которое для каждой переменной требует O(log 2 n) дополнительных переменных, но позволяет сократить количество утверждений до O(nlog 2 n). Общий размер утверждений для кодирования AMO составит O(n 2 log 2 n). Утверждения ALO и AMO для различных переменных указаны в секциях 1 4 Таблицы 2.1. Чтобы удовлетворить 5 и 6 правило нумерации вершин вводятся утверждения, запрещающие неправильную нумерацию детей обычных вершин и предков ретикулярных вершин. Эти утверждения приведены в секции 5 Таблицы 2.1. Кроме единственности переменных необходимо связать переменные отвечающие за предков с переменными отвечающими за детей. Это делается очевидным образом: если вершина u является сыном вершины v, то вершина v должна быть предком вершины u, и наоборот. Утверждения, связывающие детей и предков разных типов вершин указаны в секциях 6 9 Таблицы 2.1. Чтобы удовлетворить 4 правило нумерации вершин, необходимо добавить утверждения, упорядочивающие ребенка ретикулярной вершины относительно предков ретикулярной вершины. Эти утверждения указаны в секции 10 Таблицы 2.1. Наиболее затратные утверждения утверждения упорядочивающие детей и предков. Эти утверждения состоят из O(n 2 ) переменных для 18 Таблица 2.1: Утверждения для кодирования структуры сети. Утверждение Диапазон 1.1 AMO p (v) ALO p (v) 1.2 v V ; P P (v) AMO l (v) 2.1 ALO l (v) 2.2 v V ; P C(v) AMO r (v) 2.3 ALO r (v) 2.4 v V ; P C(v) AMO c (v) 3.1 ALO c (v) 3.2 v R; P C(v) p ALO p r(v) 4.1 ALO l(v) 4.2 v R; P P (v) 4.3 AMO p l(v) 4.4 AMO p r(v) v R; P P (v) 5.1 l v,u r v,w v V ; u, w P C(v) : u w 5.2 p l v,u p r v,w v R; u, w P P (v) : u w 6.2 r v,u p u,v v V ; u V P C(v) 6.1 l v,u p u,v 6.3 p u,v (l v,u r v,u ) 7.1 l v,u (p l u,v p r u,v) r v,u (p l u,v p r u,v) p l (l v,u r v,u ) u,v v V ; u R P C(v) 7.4 p r u,v (l v,u r v,u ) 8.1 c v,u p u,v 8.2 p u,v c v,u v R; u V P C(v) 9.1 c v,u (p l u,v p r u,v) 9.2 p l u,v c v,u v R; u R P C(v) 9.3 p r u,v c v,u c v,u p l v,w c v,u p r v,w v R; u P C(v); w P P (v) : u w каждой вершины. Суммарный размер всех введенных утверждений составляет O(n 3 ) Кодирование отображения вершин деревьев на вершины сети Осталось позаботиться о том, чтобы сеть отображала все исходные деревья. Для этого введем следующие переменные: x t,vt,v, где t T, v t V (t), v V. x t,vt,v истинно тогда и только тогда, когда вершина v соответствует вершине v t из дерева t, то есть переменные x для каждого дерева t являются инъективным отображением множества вершин этого де- 19 рева в множество вершин сети. Пример части такого отображения показан на Рис 2.2. Заметим, что листья всех деревьев биективно соответствуют листьям сети т.к. множество таксонов одинаково для всех деревьев и сети. Поэтому, переменные x для листьев не вводятся. d t,v, где t T, v R. d t,v истинно тогда и только тогда, когда для отображения дерева t требуется выбрать левого предка у ретикулярной вершины v. u r t,v, где t T, v R. u r t,v истинно тогда и только тогда, когда ребро в ребенка ретикулярной вершины v используется для отображения дерева t. Если ребенок ретикулярной вершины v тоже является ретикулярной вершиной, то у него может быть зафиксировано направление не совпадающее с направлением его предка v, и тогда, при отображении дерева t, вершина v, вместо стягивания в ребро, полностью удалится. u t,v, где t T, v V. u t,v истинно тогда и только тогда, когда вершина v используется для отображения дерева t. a t,v,u, где t T, v V, u P U(v). a t,v,u истинно тогда и только тогда, когда вершина u является первой вершиной на пути от вершины v к корню, которая используется для отображения дерева t. Другими словами, вершина u является предком для вершины v, при отображении дерева t. Заметим, что вершина v может не использоваться для отображения. На Рис. 2.2 вершина u является предком для всех вершин ниже нее, при отображении дерева t. 20 Рис. 2.2: Часть инъективного отображения вершин дерева (слева) на вершины сети (справа). Инъективное отображение изображено пунктирной линией. При отображении дерева, все ребра на пути от u до v стянутся в одно ребро,
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks