АвторТема: Мурка - программа построения кладограмм, (Valery Z. и Ко)  (Прочитано 65661 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн CenturionАвтор темы

  • 100% Earth (Solar System) genofond
  • Администратор
  • *****
  • Сообщений: 9548
  • Страна: ru
  • Рейтинг +571/-2
Murka Package
by Valery Z.
RCMG, 2005-2006

По просьбе посетителей сайта МолГен Валерий привел описание (вопрос-ответ) своей программы и ее возможностей...

Вопросы:
Может ли Мурка использоваться при работе с Y-ДНК?
Какие основные функции Мурки? Каким образом и когда можно приобрести Мурку?


Ответы:

В принципе может но нужен модуль по конвертации в РДФ. Нужно ТЗ :)
Во-вторых, Мурка рисует с помощью Графвиза, причем только укорененные деревья. Общего вида сети Мурка конечно делает, она делает значительно больше чем нетворк, но не умеет отображать такие сети. Графвиз не способен рисовать неукорененные сети высокого качества без участия человека, или по кр мере я не умею его заставить. Сейчас я разыскиваю программу которая умела бы это делать эвристически, автоматом. Пока увы :)

По поводу "приобрести". В прошлом году была гуевая версия Мурки которая несколько устарела, я более ее не распространяю. Сейчас готова консольная для Линукса и Виндовза, x86 и Itanium. Я могу показать когда закончу тестить, где-то через недельку. В дальнейшем к ней предполагается некоторая гуя, но только для виндозного варианта. Дело в том что в пакете пять программ, они разумеется общеприменимы и не зависят от локуса - будь то маркеры У мтднк или формы ушей:

MJ (опций больше чем в нетворке, Мурка многократно быстрее)
RM (опций больше чем в нетворке, Мурка быстрее)
+MP (опций больше чем в нетворковском phylo.exe но алгоритм в Мурке пока значительно медленнее. Флюксус пользуется сторонней программой Полцина которая является мировым лидером и с которым я не могу тягаться. Но вменяемое количество данных Мурка пожет штейнеризовать)
Aligner with FASTA->RefSeq Conversion (то есть из AGTCCAGTTT в типа 082-240-...)
RefSeq->RDF (с множеством дополнительных опций)
mtdna Hg Predictor with integrated Reference Database

сначала выйдут только первые три в одном бинарнике. Остальные должны быть переделаны так как прежняя версия меня кое-чем не устраивает.
Итак, примерно через неделю будет бинарник murkaph (в виндовзе murkaph.exe) для обеих систем. По поводу не-x86 архитектур - ну обращайтесь :) Я даже в быту юзаю Итаниум2 поэтому нормально отношусь к пожеланиям иметь версию под Мак или Спарк. Скорее всего в конце года я выложу исходники, они кроссплатформенные. Программа тестировалась в течение двух лет на Линуксе (ia32, Itanium) и Виндовсе (ia32).

Мурка бесплатна, а когда выйдет код то лицензия позволит его изменять и распространять, сохранив копирайты включая код заимствованный и измененный мною там где имеется аналогичная лицензия. Из сторонних пакетов используется Графвиз который бесплатен но требует предварительной установки. Для всех трех платформ для которых поддерживается Мурка (Линукс ia32, Itanium, Виндовс ia32) Графвиз имеется как в бинарнике там и в исходнике.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Мурка доступна с августа 2008 по этому адресу:

http://sourceforge.net/projects/phylomurka

можно загрузить exe для Windows и тарбол для Linux

Доки:

http://sourceforge.net/docman/display_doc.php?docid=130863&group_id=236370

Текущая версия 1.1.9
« Последнее редактирование: 28 Апрель 2009, 02:50:22 от Valery »

Оффлайн CenturionАвтор темы

  • 100% Earth (Solar System) genofond
  • Администратор
  • *****
  • Сообщений: 9548
  • Страна: ru
  • Рейтинг +571/-2
Кто нибудь возьмется "прикрутить" к Мурке граф. интерфейс?

Это вообще можно сделать? Это даст возможность большему кол-ву людей освоить программу и пользоваться ею.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Как и обещано, буду частями давать практически ориентированное описание разных опций.

Оффлайн CenturionАвтор темы

  • 100% Earth (Solar System) genofond
  • Администратор
  • *****
  • Сообщений: 9548
  • Страна: ru
  • Рейтинг +571/-2
Как и обещано, буду частями давать практически ориентированное описание разных опций.
А можно сделать короткое руководство "для чайников" шаг за шагом на примере небольшой выборки Y-гаплотипов?

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Про встроенный солвер проблемы Штейнера.

Из программ MJ, FN и RM он запускается автоматически при наличии опции

-j POSTPROC
Эта опция означает, что из медианной сети (опции порождения которой задаются не штейнеровскими а чисто филогенетическими параметрами) будет выделены штейнеровские деревья. Как именно - указывается в самих штейнеровских опциях -M:


-M "0; 20; 0; 0; RESCHECK; 1; 0; 0; SEP1|NTT|NT1|NT2|NTD|LEUC|PS|SL|NV|LE|VR|NTDVR|PT|PTE|DA|SEPDA|NTDX|PTEX|EXTE|EXTV|EXTEE|EXTVDA|EXTEEDA|EXTVDAP|EXTEEDAP|ASCPRN|EXPV|CUTRDA; 0; LBDA|KEEPBND|BNDREPEATS2|BNDPERC2|EXTTEST2|EXTTESTP3|PRUNE2|PROCMSG1|NWPERFMON|REDPMLEV2|REDREP2|COMPLTRAVERSAL; "

Разбираем их подробнее. Для этого лучше вызвать хелп к самой штейнеровской программе ST:

./murka -h -T ST
Из всего вывалившегося хелпа отрезаем ненужное - так как солвер запускается самой Муркой из филогенетической программы, а хелп написан для отдельно запускаемого солвера ST. Но принципиально аргументы все равно те же самые. Не обращайте внимание на названия и буквы аргументов, так как для филогенетических целей все это запихивается в один аргумент -M.

Цитировать

 -e : Epsilon; an integer value
 -b : Boolean limit; an integer value
 -m : Memory limit; an integer value
 -q : Edges number limit; an integer value
 -o : Task options; any '|'-separated combination of the following:
      TASKUNION,TASKALL,MSNRESULT,NOTRUNCATE,
      ZEROCOSTFIXUP,TASKAPPROX,FASTUNION,SAFEONLY,SUSPEND,
      SMALLFIRST,LP,RESCHECK,MORETREES
 -n : Networks number; an integer value
 -c : Capacity limit; an integer value
 -L : LP capacity limit; an integer value
 -r : Reductions; any '|'-separated combination of the following:
      SEP1,NTT,NT1,NT2,
      NTD,NTDVR,NTDX,LEUC,SL,
      NV,CUTRDA,LE,PT,PTE,
      PTEX,PS,EXTV,EXTE,EXTEE,
      EXTVDA,EXTVDAP,EXTEEDA,EXTEEDAP,VR,
      LDA,DA,SEPDA,EXPV,ASCPRN
 -l : Red. iterations; an integer value
 -p : Performance options; any '|'-separated combination of the following:
      LBAUX,LBDALIM,LBDA,KEEPBND,
      BNDREPEATS1,BNDREPEATS2,BNDREPEATS3,BNDREPEATS4,BNDPERC1,
      BNDPERC2,BNDPERC3,BNDPERC4,NWPERFMON,REDPMLEV1,
      REDPMLEV2,REDPMLEV3,REDPMLEV4,NWSPEC,REDREP1,
      REDREP2,REDREP3,REDREP4,COMPLTRAVERSAL,EXTTEST1,
      EXTTEST2,EXTTEST3,EXTTEST4,EXTTESTP3,EXTTESTP4,
      PRUNE1,PRUNE2,PRUNE3,PRUNE4,CUTR,
      PROCMSG1,PROCMSG2,PROCMSG3,PROCMSG4


Аргументы -b, -m, -q, -c, -L, -l устанавливают пределы объема анализируемых данных и времени работы, они необходимы только для автоматического запуска Мурки с сервера, пользователь же всегда может сам прервать исполнение программы нажав Ctrl+C. Поэтому далее будем рассматривать только содержательные опции, хотя конечно если у кого-то из уважаемых участников будут вопросы по опущенным параметрам, я с радостью на них отвечу.


Самые главные опции - это тип задачи -o и ее логические параметры -e и -n. Ищем их в строке -M:

Цитировать
-M "0; 20; 0; 0; RESCHECK; 1; 0; 0; SEP1|NTT|NT1|NT2|NTD|LEUC|PS|SL|NV|LE|VR|NTDVR|PT|PTE|DA|SEPDA|NTDX|PTEX|EXTE|EXTV|EXTEE|EXTVDA|EXTEEDA|EXTVDAP|EXTEEDAP|ASCPRN|EXPV|CUTRDA; 0; LBDA|KEEPBND|BNDREPEATS2|BNDPERC2|EXTTEST2|EXTTESTP3|PRUNE2|PROCMSG1|NWPERFMON|REDPMLEV2|REDREP2|COMPLTRAVERSAL; "

Первая опция из выделенных синим это -e, затем -o и потом -n. Мурка может искать, по возрастанию алгоритмической сложности:

-- Приближенное штейнеровское дерево
-- Произвольное минимальное штейнеровское дерево
-- Объединение всех мин. штейнеровских деревьев
-- Объединение всех мин. штейнеровских деревьев с деревьями-примерами для каждого ребра
-- Произвольные n наборов мин. штейнеровских вершин
-- Все наборы мин. штейнеровских вершин
-- Все наборы штейнеровских вершин стоимостью превышающей оптимум не более чем на epsilon (не путать с опциями epsilon из Murka MJ!)

Полиномиальным является только первый вариант - нахождение приближенного дерева, остальные комбинаторны и решаются методом ветвей и границ с поддержкой редукций и ЛП. Последние 3 варианта чрезвычано трудоемки и возможны только для небольших наборов данных, введены они скорее для теоретического изучения небольших графов чем для практической работы. Я рекомендую работать с вариантами 1, 2 и 4, см ниже что для каждого из них рекомендуется пихать в командную строку:

(помним что вместо -e -o -n у нас одна строка -M где все через ";" см пример выше где места -e -o -n выделены синим; но здесь удобнее каждый штейнеровский параметр называть по его имени как если бы запускалась отдельно стоящая программа Мурка ST)

-- Приближенное штейнеровское дерево
-e 0 -o RESCHECK|TASKAPPROX -n 1

-- Произвольное минимальное штейнеровское дерево
-e 0 -o RESCHECK -n 1

-- Объединение всех мин. штейнеровских деревьев с деревьями-примерами для каждого ребра
-e 0 -o RESCHECK|FASTUNION -n 1
или если хочется ну очень много примеров-деревьев то
-e 0 -o RESCHECK|FASTUNION|MORETREES -n 1

RESCHECK вообще говоря нигде не обязательная опция я ее рекомендую для контроля ошибок - она заставляет Мурку проверять конечный граф на физибельность и бросать исключение если что не так.

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

Полный список типов выходных файлов которые сохраняются в директории по имени -p "..." можно найти в пособии к Мурке

https://sourceforge.net/docman/display_doc.php?docid=130863&group_id=236370

см. топик MURKA MJ/FN/RM: OUTPUT FILE FORMATS

Цитировать
- Taxa Table
 - Characters Table
 - Character Changes Table
 - Network Links Table

Например, если мы передадим параметр -z "taxatbl#" то вместо знака # для каждой результирующей сети подставится ее имя/номер:

taxatbl_all - сам результат исполнения филогенетической программы MJ/FN/RM, он подается на вход Штейнеровской программы

taxatbl_mp_1 - первое штейнеровское дерево
taxatbl_mp_2
[taxatbl_mp_3 итд

taxatbl_mp_all - объединение деревьев, генерится только если солвер вызывался с FASTUNION (или некоторыми другими опциями которые мы здесь не рассматриваем).

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

nwlinktbl_all
Цитировать
Description   MP-unprocessed median network;

nwlinktbl_mp_1
Цитировать
Description   MP-processed median network; attr.=MST; cost=2342; mincost=2342; ST options: eps=0, opt=12544, cnt=1;                           
                        
nwlinktbl_mp_all
Цитировать
Description   MP-processed median network; attr.=UNION,MST; mincost=2342; ST options: eps=0, opt=12544, cnt=1;      
                     

mincost - это глобальный минимум который нашла программа, cost - стоимость дерева находящегося в данном файле (в файле где объединение нескольких деревьев это поле очевидно не нужно). Эти поля могут быть интересны при использовании автоматической системы, которая сама запускает мурку и сохраняет результаты в sql-базе. Но есть один случай когда это может заинтересовать и пользователя, а именно, это случай запуска со штейнеровским параметром TASKAPPROX для генерации приближенного решения.

nwlinktbl_mp_1
Цитировать
Description   MP-processed median network; attr.=MST; cost=2060; lbound=2020; mincost=2060; ST options: eps=0, opt=8196, cnt=1;         

В поле cost по прежнему содержится стоимость полученной сети, но теперь появилось еще поле lbound для нижней границы. Подсчитаем зазор (gap) между границами решения: 1 - 2020/2060 = 0.02. Иными словами, стоимость приближенного решения не более чем на 2% хуже оптимума. Отметим, что априори неизвестно какая из приведенных границ ближе к истинному оптимуму - нижняя или верхняя. Чтобы это выяснить, нужно дождаться завершения работы солвера запущенного с опциями построения точного а не приближенного решения.

Также следует помнить, что исходная сеть, порожденная филогенетическими программами MJ/FN/RM, может потерять глобальный оптимум, то есть штейнеровский солвер ищет оптимум относительно того графа который ему передала филогенетическая программа.


NB! Весьма существенной опцией является -j CONTRACTNT2 которая лежит в наборе главных филогенетических опций -j так как понимается не процедурой солвера а по выходу из нее. Она определяет надо ли сокращать (контрагировать) цепи нетерминалов то есть путей состоящих из медианных вершин степени 2. Если цель запуска Мурки - практическая, то ответ - надо! Никакой реальной интерпретации такие цепи не имеют, если два гаплотипа отличаются кучей одновременных мутаций, то последовательность их возникновения не может быть реконструирована. Такие ветви отсутствуют в исходных графах MJ/FN но могут быть получены на выходе из солвера, который отсекает лишние ребра но не обязан заботиться о прилизывании решения - об этом нужно позаботиться отдельно. Пожалуйста, не забывайте про -j CONTRACTNT2.


Ну и в заключение пара слов про опции набора редукций и их оптимизации:

Цитировать
-M "0; 20; 0; 0; RESCHECK; 1; 0; 0; SEP1|NTT|NT1|NT2|NTD|LEUC|PS|SL|NV|LE|VR|NTDVR|PT|PTE|DA|SEPDA|NTDX|PTEX|EXTE|EXTV|EXTEE|EXTVDA|EXTEEDA|EXTVDAP|EXTEEDAP|ASCPRN|EXPV|CUTRDA; 0; LBDA|KEEPBND|BNDREPEATS2|BNDPERC2|EXTTEST2|EXTTESTP3|PRUNE2|PROCMSG1|NWPERFMON|REDPMLEV2|REDREP2|COMPLTRAVERSAL; "


Список полезных редукций можно уменьшить до:

SEP1|NTT|NT1|NT2|NTD|LEUC|PS|SL|NV|LE|PT|PTE|DA|NTDX|PTEX|EXTV|EXTVDA|EXTVDAP|ASCPRN|EXPV|CUTRDA


а опции оптимизации наоборот изменить в сторону усиления мощности редукций:

LBDA|KEEPBND|BNDREPEATS3|BNDPERC2|EXTTEST2|EXTTESTP3|PRUNE1|PROCMSG1|NWPERFMON|REDPMLEV2|REDREP2|COMPLTRAVERSAL


В ряде случаев такое изменение помогает. Однако я буду стремиться к достижению производительности, при которой пользователю будет достаточно менять только логические опции, не вдаваясь в вопросы тонкой настройки исполнения. Пока это проходит только на У-выборках небольшого и среднего объема, большие графы порожденные микросателлитными данными Мурка может решить в рутинном порядке только приближенно, с опцией TASKAPPROX. Сниповые элайнменты, должен отметить, существенно проще.
« Последнее редактирование: 06 Июнь 2009, 20:22:29 от Valery »

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Как и обещано, буду частями давать практически ориентированное описание разных опций.
А можно сделать короткое руководство "для чайников" шаг за шагом на примере небольшой выборки Y-гаплотипов?


Можно. Сейчас я разберу штейнеровские опции, потом расскажу про У. Там нужно еще разбирать утилиту prepare. Кстати, у Саши существенный прогресс с конвертацией данных, можно будет уже юзать его софт и писать хелп к нему.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Про регулярность обновления Мурки. Я делаю это более-менее постоянно, но релизы появляются 1-2 раза в месяц и часто приурочены к каким-либо новым мелким фичам. Обнаруженные мной баги и недочеты фиксятся сразу и без объявления. Ввиду отсутствия у меня регулярного доступа к Windows я могу компилировать вариант для этой операционной системы только несколько раз в неделю, в то время как тарбол для Linux обновляется регулярно.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Про опции Мурки общие для все подпрограмм MJ, FN, RM и ST.

Цитировать

 -S : Messages and interactions; choose one of the following:
      Y,N
 -V : Verbosity; any '|'-separated combination of the following:
      VP,VU,VS,VD,
      VL
 -I : Integer counter; an integer value
 -F : Percentage counter; a real value between 1.0 and 100.0

Если Вы выберете -S N то Мура будет работать практически молча, не досаждая выводом в консоль. Скажет когда запустилась и когда отработала, ну разве еще при наличии исключения будет выдано сообщение. Я все-таки предпочитаю -S Y чтобы читать информацию на экране. Опции вывода этой информации определяются параметром -V. Если из него выбросить VP то процентный счетчик циклов заменится целочисленным, Вы увидите каждую итерацию. Мне такой способ не слишком нравится, но если кому удобно - может изменить. Количество итераций через которое вылезает сообщение об их завершении определяется параметром -I а для % (если указано -V VP) есть параметр -F я себе ставлю 20.0. Но есть циклы, про которые неизвестно сколько в них будет итераций. По умолчанию Вы увидите все, но если добавить -V VU то и для таких итераций будет использован аргумент -I, как и для обычных циклов с заранее известным числом итераций. -V VD позволяет видеть совсем подробный вывод на экран, но он понимается в основном штейнеровским солвером. -V VS вываливает разную статистику нужную разве что для отладки и изучения производительности всяких кэшов и хэшей. Наконец, -V VL дублирует экранный вывод в файл murka.log который всегда лежит в той же папке где и исполняемый файл, используя его проверьте пожалуйста права на запись (например если Вы изменили директорию назначения при установки под Линуксом из тарбола). Этот параметр я ввел когда мне надоело делать вывод в лог командами вроде ./murka > log.txt - ведь иногда хочется видеть и экранный вывод и его запись в файл.


Оффлайн mouglley

  • ...
  • Сообщений: 7105
  • Страна: hr
  • Рейтинг +434/-7
  • Я знаю, что познаю всё.
    • Записки Маугли
  • Y-ДНК: N1c1-L1025
  • мтДНК: J1c3
Уважаемый Valery, Мурка наконец-то просчиталась с  -b 10 -f "" -m 0.2.
Но, пришлось сделать  -e 0 -x 0.
Древо значительно изменилось.
Каково Ваше мнение, лучше со Штейнером но без эпсилона, или наоборот?

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Ув. Mougley, может быть Вы имели в виду "с новой фичей WPHEUR и эпсилон 0 либо без новой фичи но эпсилон > 0"? На СТР таки первое лучше, так как с большим эпсилон можно состариться пока программа отработает.

А Штейнер (опция POSTPROC) нужен по-любому в обоих случаях.


Оффлайн mouglley

  • ...
  • Сообщений: 7105
  • Страна: hr
  • Рейтинг +434/-7
  • Я знаю, что познаю всё.
    • Записки Маугли
  • Y-ДНК: N1c1-L1025
  • мтДНК: J1c3
До спасибо, неправильно сформулировал вопрос.

А не подскажите, веса из ych, при WPHEUR всё равно учитываются?

Уж очень сильно меняется дерево. Хочется понять для себя, из-за чего.
 

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Веса учитываются, конечно. Просто при понижении стоимости (т.е. суммарной длины) дерева меняется и его топология. Считается, что это изменение к лучшему :)

А можно увидеть где-нибудь какие именно изменения произошли с Вашими деревьями, ув Mouglley?

Оффлайн mouglley

  • ...
  • Сообщений: 7105
  • Страна: hr
  • Рейтинг +434/-7
  • Я знаю, что познаю всё.
    • Записки Маугли
  • Y-ДНК: N1c1-L1025
  • мтДНК: J1c3
Безусловно, покажу на png на этой ветке в ближайшую пару дней, как только базы перелопачу.

Оффлайн Valery

  • Сообщений: 10107
  • Страна: 00
  • Рейтинг +1380/-7
  • Ultimate Matriarchy
Пожалуйста, покажите оба варианта, и если можно, с кратким обоснованием по каким причинам (историческим, ..) Вам кажется более правдоподобным предыдущий вариант. Теоретически возможна ситауция, когда минимальное дерево не является лучшим с биологической точки зрения.

 

© 2007 Молекулярная Генеалогия (МолГен)

Внимание! Все сообщения отражают только мнения их авторов.
Все права на материалы принадлежат их авторам (владельцам) и сетевым изданиям, с которых они взяты.