Поиск по шаблону, допускается более одного несоответствия

Question

Я пытаюсь найти шаблон поиска с определенным условием: мы должны найти стартовые позиции.Также допускается более одного несоответствия, т.е.это должно быть выполнено для 1 или 2 или 3 несоответствий.т.е. для 1 несоответствия один символ шаблона может совпадать или не совпадать при сопоставлении с последовательностью.Как и в случае двух несовпадений, два символа шаблона могут совпадать или не совпадать при сопоставлении с последовательностью.И т. Д.

output: should be written into a file in a table format:
e.g,  pattern may be TGCA and sequence may be ATCGATGCATATCGATC....]

finding TGCA  in sequence ATCGATGATATCGATC  will result in
S.no  position       the_matched_pattern
1      5                 TGCA

Совпадение и несовпадение могут иметь место в любой позиции (т. Е. В той же позиции или в другой позиции).Как я могу это реализовать?

Answer 1

В общем, это самая длинная общая проблема подпоследовательности. Проведите некоторое исследование алгоритма Смита-Уотермана - вам, вероятно, следует это реализовать.

http://en.wikipedia.org/wiki/Smith-Waterman_algorithm

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem