Выравнивание последовательности: избегайте невероятных выравниваний

Я использую алгоритм, эквивалентный алгоритму Нидлмана-Вунша, для нечеткого сопоставления последовательностей с использованием матрицы подобия.

Некоторые результаты близки к оптимальным:

SIL d   e:  n   SIL A+  r   t   i:  k   E+  l   SIL SIL A+  f   t   @   SIL b   u:  @   n   @   SIL aU  s
-   d   e:  n   -   -   @   t   e:  k   9   l   SIL "   A+  f   d   @   -   b   9   A+  n   @   SIL aU  s

Но некоторые не являются:

SIL d   E+  r   SIL I+  n   h   A+  l   t   SIL S+  t   e:  t   SIL u:
-   -   -   -   -   -   -   z   I+  -   k   -   -   -   -   f   -   - 

Проблема возникает вокруг удалений и вставок: алгоритм выравнивает отдельные буквы рядом с удалением, которые едва ли соответствуют отсутствующим частям.

Я уже пытался оштрафовать начало пробелов, чтобы алгоритм отдавал предпочтение большим пробелам, а не маленьким. Результаты были ужасными, потому что, как вы можете видеть выше, разрывы длины 1 и 2 очень часто встречаются в правильно выровненных частях.

Как изменить алгоритм, чтобы избежать неправильного выравнивания, состоящего из разбросанных букв с плохими оценками (таких как f в - - - - f - -который, очевидно, должен быть просто еще одним -)?

Редактировать: Для тех из вас, кто не знаком с Алгоритмом: Когда подсчитываются баллы, неизвестно, какой путь будет взят, потому что путь зависит от того, что: Баллы.

Это означает, что при подсчете баллов я не могу учесть соседние выравнивания, потому что они неизвестны. Но если выравнивание достаточно хорошее или нет, зависит от соседей: если пара плохо подходит (помните: я использую матрицу подобия, заполненную вероятностями) и окруженную пропусками, она должна получить очень плохой результат (см. Второй пример), Если он окружен другими, более подходящими парами, он должен получить хороший результат (см. Первый пример).

Поэтому при подсчете баллов у меня возникла небольшая проблема с курицей и яйцом.

0 ответов

Другие вопросы по тегам