Kodomo

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

Поиск цепочек ортологов

План реализации

Автор задачи
Спирин С. А.
Крайний срок сдачи
20 апреля 2010

Приблизительная постановка задачи

Дано: набор названий организмов, для каждого организма набор белков.

Входные даные: список организмов (текстовый файл), список белков (fasta-файл) (или таблица расстояний – текстовый файл)

Задача: найти все цепочки ортологов белков заданных организмов.

  1. Для каждого белка XA в каждом организме A и каждого организма B найти наилучший ортолог YB для белка XA

  2. Построить (неориентированный) граф взаимно наилучших ортологов – т.е. таких белков XA и YB, что XA – наилучший ортолог для YB, а YB – налилучший ортолог для XA

  3. Цепочкой ортологов называется клика в этом графе, которая покрывает все организмы

Ещё одна приблизительная постановка задачи

Написать программу по поиску ортологов между данными последовательностями белков.

Данные на вход: последовательности белков в fasta-формате, координаты домена, позиционные параметры: длина выравненного участка, минимальный допустимый %id.

Программа

  1. Вырезает по заданным координатам домены, сторит все возможные попарные выравнивания, для каждой пары из выравнивания считает эволюционные расстояния, %id, проверяет, что длина выравнивания и %id удовлетворяют заданным при запуске порогам.
  2. На следующем этапе строится 2 таблицы. В одну для каждой пары выравниванивания заносится %id, в другую - величина эволюционного расстояния.
  3. По данным таблицы ищутся BET'ы (BET'ом будем называть такую пару доменов, у которых максимальный %id для представителей РАЗНЫХ геномов в своей строчке в таблице1 оказывается максимальным в своём столбике).
  4. Каждая пара BET образует ребро графа. Программа ищет клики данного графа.
  5. Для каждой вершины каждой найденной клики программа "анализирует" длину каждого ребра, выходящего из этой вершины (эволюционное расстояние) и добавляет коортологов (Если длина ребра Organism1_domain4--Organizm2_domain7 больше, чем длина Organism1_domain"i"--Organizm2_domain7, то домен "i" объявляется коортологом этой клики).
  6. На выходе получаем список клик - список ортологов и список коортологов для каждой клики.