允许多个不匹配的模式搜索

Question

我在用特定条件搜索模式搜索：我们必须找到起始位置。 也允许不止一个不匹配，即。它应该运行1或2或3不匹配。 即对于1个不匹配，图案的一个字符可能匹配或不匹配，而匹配 与序列。与2个不匹配相同，在将 与序列匹配时，模式的两个字符可能匹配或可能不匹配。等等。

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

一般来说，这是最长的常见子序列问题。对“Smith-Waterman”算法做一些研究 - 你应该实现这一点。

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

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