MURKA. Мануал для дилетанта. ОБСУЖДЕНИЕ

[Daemon2017]

А возможно ли как-то запретить такую топологию графа, при котором один образец отображается как потомок второго? Например, вместо связи предок-потомок создавать промежуточный узел и от него связь брат-брат.


Делаю вот так:

Код: [Выделить]

murka ^
-T "MJ" ^
-S "VB|RSW|EM|THR2" ^
-V "VP|VL|VR" ^
-I 1 ^
-F 20.0 ^
-H "N" ^
-P "1;1.4;2.25;5000;1;1.4;2.25;5000;0;0.75;500;50;33;" ^
-C "0;50;0;" ^
-M "0; 0; 0; 0; RESCHECK|FASTUNION|MORETREES; 1; 0; 0; SEP1|NTT|NT1|NT2|NTD|LEUC|PS|SL|NV|LE|PT|PTE|DA|NTDX|EXTV|EXTVDA|EXTVDAP|ASCPRN|EXPV|CUTRDA|EXTEEDA; 0; LBDA|UBRSPH|KEEPBND|BNDREPEATS3|BNDPERC2|EXTTEST2|EXTTESTP2|PRUNE3|REDREP3|PROCMSG1|NWPERFMON|REDPMLEV2|COMPLTRAVERSAL|KEEPTREE|OOO1|DEFERPW3; " ^
-J 0 ^
-X 0 ^
-Y 0 ^
-U 0 ^
-W 0 ^
-Z 0 ^
-s "BCACHE|DCACHE|THASH" ^
-j "CONSTSPLITS|EQSPLITS|PSHELLING|POSTPROC|CONTRACTNT2|ROOTING|ALLOWTERMROOT|MIDPOINTROOT|MSNCACHE|NWGRCACHE|FASTMJ|WPHEUR|MPSTAT|CONSTREE|NWAGE" ^
-e 0 ^
-x 0 ^
-b 100 ^
-f "NOFU|NS3|STAPPR|FH" ^
-m 0.6 ^
-n 100 ^
-l 10 ^
-t "RDF" ^
-i "y.rdf" ^
-r "data\metric\states_str0050ineq_2_2" ^
-d 0.8 ^
-o "SEQTABLE|TAXATABLE|CHARTABLE|CHARCHNGTABLE|NW|NWEXT|STAT|STP|MPCOMPTABLE|MPRFTDMATRIX|MPPARTTABLE|MPTOPOTABLE|CHARSTTABLE|DMATRIX" ^
-c "inn_" ^
-p "nw" ^
-q "stat" ^
-u "nwlinktbl#" ^
-O "seq.rdf" ^
-w "distmx" ^
-D "charsttbl" ^
-z "taxatbl#" ^
-a "chartbl#" ^
-k "charchngtbl#" ^
-Q "wtdistmx" ^
-K "rftdistmx" ^
-R "tcmptbl" ^
-B "parttbl" ^
-L "topotbl" ^
-G "GraphViz; 1; ROOTPREFERRED|CHNAMES|CHCHNG|TXNAMES|TXFR|TXFRSZ|TXCD|ROOTONLY|TREEONLY|NOPOOL|AGE|MPPART|CALL; 1.8; 1.1; 0.1; 2.0; 86.0; png; C:\gv\bin\dot.exe; C:\gv\bin\circo.exe; viz\nw#.dot; viz\nw#.png; viz\tpl\nwtpl.txt; ; "


[Valery]

подобные фичи есть в других "принтерах" внутри мурки, да тот же ньюик например
в других версиях мурки (не в том дистре) есть принтер в xlsl (только для линукса правда) там как раз то что вы имеете в виду.

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

ПС. Я не поддерживаю сейчас мурку как "универсальную" филогенетическую программу. В этом году надеюсь будет законченная версия, но она позиционируется как 1) "штейнеровский солвер для биологических приложений" (метаболические сети например, через эмуляцию нод-вейтид штейнера классическим 2) классический бранч-эн-баунд солвер для хэмминга, но с фичами облегчающими сравнение со штейнером.

Вообще я давно считаю парсимонию вредной для биологии, хотя и необходимой достаточно часто. Мурка теперь специально так задумана, что если юзер не понимает зачем ему нужна именно эта программа, он ее не запустит. "Мне нужны парсимонные спектры ребер" или "я занимаюсь комбинаторной статистикой для филогенетики, хочу посчитать размер некоторых графов" - ок, милости просим, спс что выбрали мурку (ха, больше ничего и нет по узкому сабжу). "Я хочу построить дерево" - нет, не по адресу, вы должны четко понимать нафига вам парсимонное дерево и как вы выберете из миллиона парсимонных деревьев которые может вам сделать мурка, нужное, если бутстрэпа в ней нет? Юзер может выбрать, но он должен знать как это сделать. Я не считаю, что тем замысловатым способом, которым этот выбор делается в парсимонии, юзеру надо засерать мозги. Это лишняя информация для всех, кроме профессиональных филогенистов с математическим бэкграундом.

Есть стопицот программ, которые делают дело лучше чем парсимония.

[Valery]

-T "MJ"

по параметрам я так понимаю это старый муркин эвристический MJ. В новых версиях чистый MJ я оставил на эвристический уже заменен на топологический поиск довольно классического вида (SPR+ratchet+SCM). Он мощнее чем MJ-heur и значительно быстрее. В старой мурке ядро не поддерживало топологии, там по сути довольно тормозная эмуляции. В новой библиотеке совершенно новое ядро, оно прекрасно дружит с топологиями, работает с ними нативно.

[Valery]

Версия "out of the box"  на самом деле планировалась, но как вызов из другого моего пакета, который больше скорее всего поддерживаться не будет.

Это коллер и реэлайнер ngs, настраиваемый, с обственным скриптовым языком и множеством фич. У него есть даже небольшой интерфейс на qt. Там есть экспорт в мурку и возможность генерить деревья в xlsx ровно такого вида как вы имеете в виду (ну ньюик есть еще ессно). Но даже в ней я планировал приделать еще экспорт и в другие филопрограммы, чтобы был выбор.

Там вот пайплайн дозволяет скормить программе сырой пайлап с бама и на выходе получить множественное выравнивание и деревья. Если у вас есть пайплайн, подходящий для данной платформы ngs, данного набора таргетов, ессно. Этот пакет действительно для биологов разрабатывался, а не для математиков.

Проект вообще не слишком ориентирован был на филогенетику, это в первую очередь именно коллер и фильтр, с обилием фич, например множественный реэлайнер на основе seqan. Вообще и аутосомы понимает тоже, но больше заточен для Y. Поддерживаться не будет, сил к сожалению мало на все, не могу,

[Daemon2017]

подобные фичи есть в других "принтерах" внутри мурки, да тот же ньюик например
в других версиях мурки (не в том дистре) есть принтер в xlsl (только для линукса правда) там как раз то что вы имеете в виду.

Ааа, т.е. это можно решить только на уровне вывода, а не на уровне самого построителя графа?

-T "MJ"

по параметрам я так понимаю это старый муркин эвристический MJ.

Да, использую murka-1.4.1 под Виндой и вот собрал murka-1.5.1 под Линем

[Valery]

Ааа, т.е. это можно решить только на уровне вывода, а не на уровне самого построителя графа?

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

Бранч-эн-баунд программы, как и эвристики, обычно ищут бинарное дерево, а потом по желанию юзера коллабируют его. Наиболее популярный коллапс - частичный: оставить последний линк, ведущий к листу. Получится ровно то что вы имели в виду. В старой мурке, которую вы запустили, было иначе, там строилось дерево в метрическом пространстве и потом при желании как-то украшалось.

[Valery]

Да, использую murka-1.4.1 под Виндой и вот собрал murka-1.5.1 под Линем

в 1.5 уже есть топологии но они еще не выведены в интерфейс )))

[Daemon2017]

Ааа, т.е. это можно решить только на уровне вывода, а не на уровне самого построителя графа?

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

Бранч-эн-баунд программы, как и эвристики, обычно ищут бинарное дерево, а потом по желанию юзера коллабируют его. Наиболее популярный коллапс - частичный: оставить последний линк, ведущий к листу. Получится ровно то что вы имели в виду. В старой мурке, которую вы запустили, было иначе, там строилось дерево в метрическом пространстве и потом при желании как-то украшалось.

Т.е. в будущих версиях все будет так, как мне и нужно? Круто!

[Daemon2017]

-T "MJ"

по параметрам я так понимаю это старый муркин эвристический MJ. В новых версиях чистый MJ я оставил на эвристический уже заменен на топологический поиск довольно классического вида (SPR+ratchet+SCM). Он мощнее чем MJ-heur и значительно быстрее. В старой мурке ядро не поддерживало топологии, там по сути довольно тормозная эмуляции. В новой библиотеке совершенно новое ядро, оно прекрасно дружит с топологиями, работает с ними нативно.

Выходит, что MJ из 1.4.1 это самый-самый ущербный вариант построения графа, проигрывающий остальным вариантам (в т.ч. FN, TP и ST) буквально во всем?

[Valery]

ST это чистый Штейнер на графах, любых, безотносительно филогенетики. В предельном (полиномиальном) случае, когда все вершины - терминалы, это просто MST, на орграфе - арборесенс (уже не такая простая штука хотя все еще и полиномиальная).

FN это полная квазимедианная сеть на которую в норме должен натравливаться штейнер для извлечения дерева (деревьев). Чем квазимедианы примечательны. Если

1) метрика является метрикой Фитча (расстояние между аллелями всегда константно, скажем 1 - типичная метрика для снипов)
2) матрица с данными не содержит константных и эквивалентных колонок

то есть скажем нет

Код: [Выделить]

C
C
C
C
и

Код: [Выделить]

TG
AC
TG
AC
то тогда внутри квазимедианной сети содержатся все штейнеровские деревья. Понятно, что в общем случае такая сеть очень велика ввиду гомоплазии. Одна при малой гомоплазии есть некое окно параметров исходной матрицы, когда извлечь штейнера из квазимедианной сети выйдет дешевле, чем искать оптимальную топологию. Вот для этого и нужна FN. Это единственная хоть сколько-то полезная фича в старых вариантах Мурки. Для матриц с эквивалентными признаками есть некоторое расширение, уже менее эффективное. Для нефитчевых метрик, скажем метрики Вагнера (это метрика STR) FN строит граф, гарантированно содержащий по кр мере 1 оптимальное дерево (которое можно найти потом штейнером), то есть уже не все. Для совсем общего вида метрик, например асимметрических (квазиметрики, с односторонним нерав. треугольника) - вообще ни о чем, может и ни одного оптимального дерева не содержать.


Наконец, чистый MJ это эвристика с двумя параметрами эпсилон которые при своем увеличении позволяют достичь полной квазимедианной сети (только в метрике Фитча разумеется). MJ в вычислительном плане неудачная штука. Как и эвристики, которые я от нее произвел.

Классического типа филогенетика в Мурке вызывается через TP но в том дистре еще очень слабая версия была выведена в интерфейс и не документирована.

[Valery]

Т.е. в будущих версиях все будет так, как мне и нужно? Круто!

да
новая версия для linux и macosx
в 00е и 10е гг были еще версии для ia64 linux и ppc64 aix/linux, но их использовали только для vlsi, там нужен штейнер. Местный народ с молгена, 2 или 3 человека использовавшие мурку, предпочитали windows последняя версия под нее была в 2015.

[Daemon2017]

ST это чистый Штейнер на графах, любых, безотносительно филогенетики. В предельном (полиномиальном) случае, когда все вершины - терминалы, это просто MST, на орграфе - арборесенс (уже не такая простая штука хотя все еще и полиномиальная).

FN это полная квазимедианная сеть на которую в норме должен натравливаться штейнер для извлечения дерева (деревьев). Чем квазимедианы примечательны. Если

Наконец, чистый MJ это эвристика с двумя параметрами эпсилон которые при своем увеличении позволяют достичь полной квазимедианной сети (только в метрике Фитча разумеется). MJ в вычислительном плане неудачная штука. Как и эвристики, которые я от нее произвел.

Классического типа филогенетика в Мурке вызывается через TP но в том дистре еще очень слабая версия была выведена в интерфейс и не документирована.

Спасибо за ответы! Т.е. MJ не хуже, а прожорливее. Но это не страшно: в вычислительном плане сейчас можно ничем не ограничиваться, т.к. каждому доступна суточная аренда в облаке машинки на сотню ядер и с сотней Гб ОЗУ под любые прихоти

[Valery]

Спасибо за ответы! Т.е. MJ не хуже, а прожорливее. Но это не страшно: в вычислительном плане сейчас можно ничем не ограничиваться, т.к. каждому доступна суточная аренда в облаке машинки на сотню ядер и с сотней Гб ОЗУ под любые прихоти

ну зачем пускать лишний CO2 в атмосферу, когда можно не пускать ))

[Daemon2017]

Спасибо за ответы! Т.е. MJ не хуже, а прожорливее. Но это не страшно: в вычислительном плане сейчас можно ничем не ограничиваться, т.к. каждому доступна суточная аренда в облаке машинки на сотню ядер и с сотней Гб ОЗУ под любые прихоти

ну зачем пускать лишний CO2 в атмосферу, когда можно не пускать ))

Справделиво

[Farroukh]

Вопрос к мэтрам. Реально ли сделать для MURKA нормальночеловекоадаптированный интерфейс для построения древа по Y12, Y17, Y23, Y25, Y27, Y37, Y67 и Y111?

Взал эксельку с гаплотипами, закинул в синее море, получил древо.