Объяснение алгоритма FASTA

Question

Я пытаюсь понять основные шаги алгоритма FASTA при поиске похожих последовательностей последовательности запросов в базе данных.Вот шаги алгоритма:

1. Определить общие k-слова между I и J
2. Оценить диагонали с соответствием k-словам, определить 10 лучших диагоналей
3. Восстановить начальные регионы с помощью матрицы оценок замещения
4. Соединить начальные регионы, используя пробелы, штрафовать за пробелы
5. Выполнить динамическое программирование, чтобы найти окончательные выравнивания

Я запутался с3-й и 4-й этапы использования матрицы оценок PAM250 и как «соединиться, используя пробелы».

Может кто-нибудь объяснить мне эти два шага «как можно точнее».Спасибо

Answer 1

Так работает FASTA:

1. Найдите все тождества k-длины, затем найдите локально схожие регионы, выбрав эти плотные с тождествами k-слов (то есть много k-слов, без слишком большого промежутка между ними). Используются лучшие десять начальных областей .
2. Начальные области пересчитываются по их длине путем применения матрицы замещения обычным способом. Оптимально оцениваются субрегионы.
3. Создание выравнивания обрезанных начальных областей с использованием динамического программирования с штрафом за пробел 20. Области со слишком низким показателем не включены.
4. Оптимизация выравнивания из 3) с использованием «полосного» динамического программирования (Смит-Уотерман). Это динамическое программирование, ограниченное полосой шириной 32 остатка вокруг исходного выравнивания, что экономит пространство и время по сравнению с полным динамическим программированием.

Если исходных областей недостаточно для формирования выравнивания в 3), лучший результат из 2) можно использовать для ранжирования последовательностей по сходству. Для этой цели также могут использоваться оценки из 3) и 4).

К сожалению, мое учреждение не имеет доступа к оригинальной бумаге FASTA, поэтому я не могу предоставить исходные значения различных параметров, упомянутых выше.

Answer 2

Объяснение по существу правильное, но окончательная оптимизация полосы сосредоточена на одном наилучшем выравнивании без разрывов, найденном на шаге 2. Шаг 3 используется просто для улучшения чувствительности при выборе последовательностей, которые получают шаг 4.

Оригинал статьи можно посмотреть здесь: http://faculty.virginia.edu/wrpearson/papers/pearson_lipman_pnas88.pdf