允許多個不匹配的模式搜索

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