выравнивание последовательности

Question

У меня следующий вопрос о выравнивании последовательностей:

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

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

Answer 1

Пусть ∑ - алфавит (например, {A, C, G, T}). Пусть L ⊆ ∑ * - множество коротких библиотечных последовательностей. Вычислить минимальное состояние DFA (Q, ∑, ∂, q ₀ , F) для L *.

Мы просканируем длинную последовательность x ∈ ∑ * по одной букве за раз. Пусть x 'будет префиксом x, который был использован. Мы поддерживаем для каждого состояния q ∈ Q минимум c _q (x ') над [каждой последовательностью y ∈ ∑ * такой, что ∂ (q ₀ , y) = q] расстояния Левенштейна между х 'и у.

Для пустого префикса ε для каждого состояния q ∈ Q справедливо, что c _q (ε) = min {| y |: y ∈ ∑ *, ∂ (q _{0 *) 1014 *, y) = q}, поскольку расстояние между y и ε равно длине y. Вычислите начальную таблицу с поиском по ширине на графе переходов.}

Учитывая таблицу для x 'и букву s, мы вычисляем c _q (x) как минимум для нескольких возможностей для y, где x = x s.

1. Строки y = y's z, выравнивая s. Стоимость в этом случае составляет min _{q ', z: ∂ (q', sz) = q} (c _{q '} (x') + | z |), что может быть вычисляется с помощью | Q | поиск в ширину.

2. Строки y = y ', удаляя s в x. Стоимость в этом случае составляет c _q (x ') + 1.

3. Строки y = y 't, где t - буква, заменяющая s на t (или наоборот). Стоимость в этом случае составляет min _{q ', t: ∂ (q', t) = q} (c _{q '} (x') + 1).

В конце, оптимальная стоимость выравнивания равна min _{q ∈ F} c _q (x). Выравнивание может быть восстановлено обычным способом для динамических программ.

Answer 2

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