ДОПОЛНИТЕЛЬНАЯ Задача: найти ветку дерева, которая содержит корень.

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

Предполагается, что у корня дерева обе группы (права и левая) хорошо поддерживаются паттернами. Для других веток дерева паттернами будет поддержана только одна группа, а вторая группа - смешанная, для нее не будет (или будет мало) паттернов, отличающих ее от первой группы.

Для каждой ветки дерева
1. Составьте два списка последовательностей - правую и левую части дерева
2. Подготовьте выравнивания правой и левой части
```
notseq align.msf -exclude "name1;name2;..." -outseq left.fasta -osformat3 fasta -junkoutseq right.fasta -osformat fasta
```
  где "name1;name2;..." - список имен последовательностей из левой части дерева. Можно использовать символ *.
3. Из полученных файлов left.fasta и right.fasta удалите пустые колонки
```
как?
```
4. Создайте список профилей для правой и левой части
```
cp -l /home/export/samba/public/y10/Term_4/Block_3/task12/create_patt.py ./
./create_patt.py align.fasta > patterns
```
5. Для каждого паттерна, построенного по левой части дерева, запустите поиск по правой и левой частям при помощи fuzzpro
  1. Загрузите вывод скрипта create_patt.py в Excel.
  2. Для каждого паттерна создайте команду вызова fuzzpro
```
fuzzpro right.fasta -pattern
"[MP]-[VI]-[LQM]-[LV]-[DEC]-[NQE]-[F]-[ET]-[AT]-[VI]" -outfile temp
```
    и затем
```
grep "Reported_sequences" temp >> result.right
```
    И такой же поиск по правой части дерева. Такой скрипт легко создать в Excel - я поместил в A3 результат работы скрипта create_patt.py, а в C3 написал такую формулу
```
=СЦЕПИТЬ("fuzzpro left.fasta -pattern """,B3,""" -outfile temp<br>grep ""Reported_sequences"" temp >",ЕСЛИ(СТРОКА(A3)=3,"",">")," result.left")
```
    После чего сохранил колонку C в файле run.tmp и подготовил скрипт командами
```
sed "s/<br>/\n/g" run.tmp  > run
chmod +x run
```
  3. Результаты загрузите в Excel, определите число находок в правой и левой части для каждого паттерна.
  4. Вычислите для каждого паттерна число ложноположительных и ложноотрицательных находок
  5. Найдите паттерн, который лучше всех отличает левую часть дерева от правой Например, такой, который делает меньше всего ошибок (FP+FN).
f. Аналогично - найдите наилучший паттерн для правой части дерева
Для каждой ветки дерева у вас теперь имеется

Лучший паттерн для левой части Число ошибок, которые он допускает Лучший паттерн для левой части Число ошибок, которые он допускает

Выберете "самую главную ветку дерева"

Например, ту, для которой разность квадратов числа ошибок, допускаемых левым и правым паттернами, минимальна.

b. Сделайте заключение - есть ли в дереве такая ветка, обе части которой монофилетичны? Удалось ли при помощи паттернов найти корень дерева?

Что поощряется:

Творческий подход.

Это задание рассчитано на то, что вы самостоятельно придумаете какие-то интересные ходы для решения этой задачи. Что можно придумать?
1. Поменять параметры в скрипте create_patt.py - в самом начале есть константы, указывающие длину паттерна и некоторые другие параметры.
  
  b. Попробовать объединять хорошие перекрывающиеся паттерны в один - весьма вероятно, что они будут лучше.
  
  c. Использовать для распознавания не один паттерн, а несколько.
  
  d. Поменять алгоритм генерации паттернов. Например, можно задаться целью искать для составления паттерна наиболее длинную часть выравнивания, состоящую из позиций, отличающих одну группу от другой, и содержащую не более какого-то числа букв Х подряд.
Автоматизация. Вручную строить списки паттернов для всех веток дерева - в известной степени мартышкин труд. Хорошо бы как-то автоматизировать этот процесс.

Kodomo

Пользователь

ДОПОЛНИТЕЛЬНАЯ Задача: найти ветку дерева, которая содержит корень.

Что поощряется: