Как найти ВСЕ оптимальные локальные выравнивания с помощью Smith-Waterman?

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

Пример:

XGTCXXGTCX 
 |||
AGTCA

XGTCXXGTCX 
      |||
     AGTCA

text-alignment bioinformatics
person tenacious    schedule 21.01.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Не существует такого понятия, как ВСЕ оптимальные выравнивания. Должно быть только одно оптимальное выравнивание. Я предполагаю, что может быть несколько путей для одного и того же выравнивания, но у них будет одинаковая общая оценка, и не похоже, что вы задаете такой вопрос.

То, что показывает ваша диаграмма в вашем посте, - это несколько (праймер?) хитов. В таком случае, что я делаю, так это запускаю smith-waterman один раз, получаю оптимальное выравнивание. Затем я генерирую новое выравнивание, в котором последовательность объекта была обрезана, чтобы включить только последовательность, расположенную ниже по течению. Преимущество этого способа в том, что мне не нужно изменять какой-либо программный код или копаться во внутренностях стороннего кода.

Так это будет выглядеть так:

Выравнивание 1

XGTCXXGTCX 
 |||
AGTCA

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

XGTCXXGTCX => XGTCX

Выравнивание 2

 XGTCX 
  |||
 AGTCA

Единственная сложность заключается в том, что вам нужно отслеживать, сколько баз было удалено из выравнивания, чтобы вы могли правильно настроить координаты совпадения.

person dkatzel    schedule 22.01.2015
comment
There is no such thing as ALL optimal alignments. There should only be one optimal alignment. Как вы пришли к такому выводу? Звучит неправильно для меня. - person cel; 23.01.2015
comment
С юго-западной точки зрения существует только 1 оптимальное выравнивание. Если несколько выравниваний имеют одинаковую лучшую оценку, то выбирается только 1 (какое из них выбирается зависит от реализации), поэтому может быть выбрано только одно выравнивание. - person dkatzel; 23.01.2015
comment
Таким образом, вы в основном говорите, что SW-Alignment для каждого определения выводит только одно выравнивание? Хм, тогда я думаю, что OP запрашивает модификацию SW - алгоритма, который выводит все оптимальные локальные выравнивания. - person cel; 23.01.2015
comment
Да, S-W всегда выводит только 1 выравнивание. ОП хочет знать, как получить все остальные столь же хорошие локальные выравнивания, поэтому я предложил повторно выровнять подстроку вместо того, чтобы изменять какой-либо код SW - person dkatzel; 23.01.2015
comment
И почему бы просто не переписать трассировку так, чтобы она начиналась со всех максимумов в матрице динамического программирования? Честно говоря, я был очень удивлен вашим ответом, потому что адаптация трассировки кажется такой простой, и ОП также предложил это в своем вопросе. - person cel; 23.01.2015
comment
Потому что тогда это был бы не S-W. Но вы правы, если у вас есть доступ к матрице трассировки, вы можете искать другие лучшие результаты. - person dkatzel; 23.01.2015
comment
@dkatzel, это неправда. Вполне возможно, что SW может иметь несколько выравниваний с одним и тем же баллом. На самом деле, существуют реализации ПО, которые сообщают обо всех оптимальных выравниваниях. Реализация биопитона: biopython.org/DIST/docs/api/ - person mortonjt; 11.08.2020

arrow_upward
0
arrow_downward

Я знаю, что этот пост в настоящее время довольно старый, но с тех пор, как я его обнаружил, другие люди также могут найти его, ища помощи, и, на мой взгляд, правильный ответ еще не дан. Итак: ясно, что может быть НЕСКОЛЬКО оптимальных локальных выравниваний. Вы только что показали такой пример. Тем не менее, существует ТОЛЬКО ОДИН БАЛЛ оптимального локального выравнивания. Глядя на исходную статью, в которой представлен алгоритм Смита-Уотермана, Смит и Уотерман уже указывают, как найти второе наилучшее выравнивание, третье наилучшее выравнивание...

вот перепечатка, чтобы прочитать этот материал (для вашей проблемы, проверьте страницу 196): .semanticscholar.org/40c5/441aad96b366996e6af163ca9473a19bb9ad.pdf

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

person Karroch    schedule 15.12.2017