Группировка аминокислот и поиск диагностических позиций
Автор задачи: Спирин С. А.
Техническое задание
В дальнейшем под «позицией» всюду понимается «столбец выравнивания, в котором нет ни одного знака пробела (гэпа), то есть ‘—‘». Но я думаю, программу надо писать так, чтобы при желании этот самый пробел можно было обрабатывать как 21-ю букву, и всё перечисленное сделать для столбцов с пробелами тоже.
Задание 1
Сколько во всех входных выравниваниях позиций, содержащих ровно одну букву (то есть во всех 30 последовательностях одинаковая буква)? Позиций, содержащих две буквы? Три? и т.д.
Результат — табличка (гистограмма): столько-то однобуквенных позиций, столько-то двухбуквенных и т.д. до 20-буквенных.
Задание 2
Какие множества и как часто встречаются в позициях? (пояснение: множество, скажем, {A,T,S} встретилось в данной позиции, если во всех последовательностях в этой позиции стоит либо A, либо T, либо S и каждая из этих букв хотя бы в одной последовательности представлена).
Результат — для каждого числа k = 1, … ,10 (бо́льшие множества, рассматривать, мне кажется, смысла нет) — верхние 20 k-элементных множеств, и для каждого такого множества — число позиций, в которых оно встретилось, а также относительное число позиций (= доля таких позиций, делённая на произведение частот входящих в множество букв). В частности, при k = 1, для каждой буквы — число консервативных позиций из одной данной буквы и доля таких позиций, делённая на частоту буквы (частоту по всем последовательностям всех выравниваний).
По какому показателю отделять верхние 20 (по абсолютным числам или по относительным) — не знаю. Наверное, всё-таки по относительным. Ощущение такое, что всё интересное в верхние 20 войдёт при любой разумной сортировке.
Результат такой программы позволит, я надеюсь, выделять «группы аминокислотных остатков» по сколько-нибудь объективному критерию. Сейчас такие группы делаются либо по наитию, либо путём кластеризации матрицы BLOSUM62, что забавно, но (как мне кажется) не слишком научно.
Задание 3
Теперь к деревьям. Вот дерево последовательностей (общее для всех выравниваний, потому что все 103 — выравнивания ортологических рядов одного и того же набора бактерий):
(((((((RHIEC,AGRRK),BRAJA),RHOS4),CAUCR),
((PSEA8,(((YERPG,((ENT38,(ECOL5,SALA4)),
ERWT9)),PASMU),VIBCH)),((BURCA,
RALPJ),NEIG1))),((((((STRP1,STRPJ),
LACLM),((LISMH,(BACSU,BACAN)),STAAB)),
CLOBH),(STRAW,(CORDI,MYCTU))),(CAMC1,
HELPY))),MYXXD);
(разбиение на строки значения не имеет, только последовательность скобок, запятых и имён организмов).
Ветвь дерева — это разделение множества видов (они же организмы, они же, в данном случае, последовательности, они же «листья дерева») на две непересекающиеся части.
Ветви бывают тривиальные: в одной части один вид, в другой все остальные (таких ветвей в любом дереве ровно столько же, сколько листьев), и нетривиальные: в обеих частях больше одного вида. Каждой нетривиальной ветви отвечает пара соответственных скобок в формуле дерева (что такое соответственные скобки, объяснять, надеюсь, не надо): те виды, что оказались внутри скобок — одна часть разбиения, те, что снаружи — другая часть.
Четыре замечания:
- Самой внешней паре скобок никакая ветвь не соответствует.
- В формуле может присутствовать пара скобок (максимум одна), которой соответствует тривиальная ветвь, как в примере (A,(B,C)); в котором вообще нет нетривиальных ветвей (в нашем примере такое тоже есть).
- В формуле две пары скобок могут соответствовать одной и той же ветви (как в примере ((A,B),(C,D)); , где есть ровно одна нетривиальная ветвь). Но такая ветвь, которой соответствуют сразу две пары скобок, может быть только одна (или ни одной, как в нашем примере).
- Внешняя и внутренняя части нетривиального разбиения абсолютно равноправны (поскольку наше дерево неукоренённое).
Теперь наконец к задаче. Мы ищем в выравнивании «диагностические позиции» для ветвей дерева, то есть обладающие следующим свойством: множество букв по одну сторону ветви не пересекается с множеством по другую сторону.
Результат — отдельно для тривиальных и нетривиальных ветвей — какие это множества?
Точнее: сколько диагностических позиций (я пишу «позиция», но на самом деле имею в виду пару (позиция, ветвь), поскольку одна и та же позиция выравнивания может быть диагностической для нескольких ветвей) типа 1-1 (то есть по одну сторону только одна буква и по другую то же), 1-2, 1-3, …, 1-19, 2-3, 2-4, …, 10-10.
Ну и для каждого типа — список тех пар множеств, которые встретились больше одного раза (например, для типа 1-1: «{A}-{G} – четыре раза, {R} - {I} – три раза, …», для типа 1-3: «{G}-{AST} – пять раз, …»). При этом, как уже говорилось, для нетривиальных ветвей не надо различать внутреннюю и внешнюю часть, а вот для тривиальных (типа 1-1, для других и так ясно) – надо, то есть для тривиальных ветвей {R}-{K} (одно R в позиции и 29 K) не то же, что {K}-{R} (одно K и 29 R).
Задачу решают: Денисенко Елена, Пеков Юрий.