Выравнивание последовательности: избегайте невероятных выравниваний
Я использую алгоритм, эквивалентный алгоритму Нидлмана-Вунша, для нечеткого сопоставления последовательностей с использованием матрицы подобия.
Некоторые результаты близки к оптимальным:
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 - -
который, очевидно, должен быть просто еще одним -
)?
Редактировать: Для тех из вас, кто не знаком с Алгоритмом: Когда подсчитываются баллы, неизвестно, какой путь будет взят, потому что путь зависит от того, что: Баллы.
Это означает, что при подсчете баллов я не могу учесть соседние выравнивания, потому что они неизвестны. Но если выравнивание достаточно хорошее или нет, зависит от соседей: если пара плохо подходит (помните: я использую матрицу подобия, заполненную вероятностями) и окруженную пропусками, она должна получить очень плохой результат (см. Второй пример), Если он окружен другими, более подходящими парами, он должен получить хороший результат (см. Первый пример).
Поэтому при подсчете баллов у меня возникла небольшая проблема с курицей и яйцом.