Про встроенный
солвер проблемы Штейнера.
Из программ
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_allDescription MP-unprocessed median network;
nwlinktbl_mp_1Description MP-processed median network; attr.=MST; cost=2342; mincost=2342; ST options: eps=0, opt=12544, cnt=1;
nwlinktbl_mp_allDescription MP-processed median network; attr.=UNION,MST; mincost=2342; ST options: eps=0, opt=12544, cnt=1;
mincost - это глобальный минимум который нашла программа,
cost - стоимость дерева находящегося в данном файле (в файле где объединение нескольких деревьев это поле очевидно не нужно). Эти поля могут быть интересны при использовании автоматической системы, которая сама запускает мурку и сохраняет результаты в sql-базе. Но есть один случай когда это может заинтересовать и пользователя, а именно, это случай запуска со штейнеровским параметром TASKAPPROX для генерации приближенного решения.
nwlinktbl_mp_1Description 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. Сниповые элайнменты, должен отметить, существенно проще.
Тема: Мурка - программа построения кладограмм, (Valery Z. и Ко) (Прочитано 68293 раз)