OK, Needleman-Wunsch (NW) - классический сквозной («глобальный») выравниватель из литературы по биоинформатике. Это было давно доступно как «align» и «align0» в пакете FASTA. Разница заключалась в том, что версия «0» не была столь же предубежденной в том, чтобы избегать конечного разрыва, что часто позволяло лучше поддерживать качественные внутренние матчи. Смит-Ватерман, я подозреваю, что вы знаете, является локальным выравнивателем и является исходной основой BLAST. У FASTA был собственный локатор, который немного отличался. Все это по существу эвристические методы оценки расстояния Левенштейна, относящиеся к метрике оценки отдельных пар персонажей (в биоинформатике, часто даваемой Dayhoff/«PAM», Henikoff & Henikoff или другими матрицами и обычно заменяются чем-то более простым и более разумным отражающим замен в лингвистической морфологии слов при применении к естественному языку).
Не будем ценными в отношении меток: расстояние Левенштейна, как указано на практике, по крайней мере, является расстоянием редактирования, и вы должны его оценить, потому что его невозможно вычислить в целом, и это дорого вычислять точно даже в интересных специальных случаи: там вода становится очень быстрой, и поэтому у нас есть эвристические методы долгой и хорошей репутацией.
Теперь о вашей собственной проблеме: несколько лет назад я должен был проверить точность коротких ДНВ, прочитанных с помощью эталонной последовательности, которая, как известно, является правильной, и я придумал то, что я назвал «привязанные выравнивания».
Идея состоит в том, чтобы взять ваш набор опорных строк и «переварить» его, найдя все местоположения, где встречается соответствующая подстрока N-символа. Выберите N, чтобы таблица, которую вы построили, была не слишком большой, а также чтобы подстроки длины N не были слишком обычными. Для небольших алфавитов, таких как базы ДНК, можно создать идеальный хеш на строках из N символов, а также составить таблицу и связать спички в связанном списке из каждого бина. Элементы списка должны идентифицировать последовательность и начальную позицию подстроки, которая отображается в ячейке, в списке которой они встречаются. Это «привязки» в списке строк для поиска, при которых может быть полезно выравнивание NW.
При обработке строки запроса вы берете N символов, начинающихся с некоторого смещения K в строке запроса, хешируйте их, просматриваете их корзину, и если список для этого бина не пуст, вы просматриваете все записи списка и выполнить выравнивание между строкой запроса и строкой поиска, на которую ссылается запись. При выполнении этих выравниваний вы выстраиваете строку запроса и строку поиска в привязкой и извлекаете подстроку строки поиска, которая имеет ту же длину, что и строка запроса, и которая содержит эту привязку с тем же смещением, K.
Если вы выберете длинную длину якоря N и разумный набор значений смещения K (они могут быть распределены по строке запроса или ограничены низкими смещениями), вы должны получить подмножество возможных выравниваний и часто будете получать более четкие победители. Как правило, вы захотите использовать менее ориентированный по высоте выравнивающий выравниватель NW.
Этот метод пытается немного увеличить NW, ограничив его вход, и это увеличивает производительность, потому что вы делаете меньше выравниваний, и чаще всего между подобными последовательностями. Еще одна хорошая вещь, связанная с вашим NW-выравнивателем, заключается в том, чтобы позволить ей отказаться от некоторой суммы или длины разрыва, чтобы сократить расходы, особенно если вы знаете, что не увидите или не будете заинтересованы в матчах среднего качества.
Наконец, этот метод использовался в системе с небольшими алфавитами, причем K ограничивался первыми 100 или около того позиций в строке запроса и с поисковыми строками, намного большими, чем запросы (чтение ДНК составляло около 1000 оснований, а строки поиска были порядка 10000, поэтому я искал приблизительные совпадения подстрок, оправданные оценкой расстояния редактирования). Адаптация этой методологии к естественному языку потребует некоторой тщательной мысли: вы теряете по размеру алфавита, но получаете, если строки запроса и строки поиска имеют одинаковую длину.
В любом случае, позволяя использовать более одного якоря из разных концов строки запроса, которые будут использоваться одновременно, может оказаться полезным при дальнейшей фильтрации данных, подаваемых в NW. Если вы это сделаете, будьте готовы к тому, что вы можете отправить перекрывающиеся строки, каждая из которых содержит один из двух якорей, в выравниватель, а затем согласовать выравнивания ... или, возможно, дополнительно изменить NW, чтобы подчеркнуть, что ваши привязки в основном не повреждены во время выравнивания, используя штрафную модификацию во время выполнение алгоритма.
Надеюсь, это полезно или, по крайней мере, интересно.
Вы соответствуете «реальным» строкам (т.е. английскому) или биоинформатике? Если реальные строки, что вы используете для своей матрицы замещения? – 2010-12-29 18:22:39
Похожие вопросы здесь http://stackoverflow.com/questions/31494/how-to-detect-duplicate-data и здесь http://stackoverflow.com/questions/42013/levenshtein-distance-based-methods-vs-soundex Другие можно найти через связанные теги и поисковые запросы. Однако вы точно не указали * почему * вам нужно сопоставить строки таким образом - проверяете ли вы дублирующиеся данные? – 2008-09-08 07:31:08