CODEWITHSUNDEEP
algorithm
aman_41907
aman_41907

Reputation: 199

string matching(DNA) with 1 mismatch allowed

I need a very fast efficient algorithm for string matching of DNA pattern with atmost 1 mismatch allowed.I have tried boyer-moore-horspool algorithm,but it exceeds the required time. The length of Text and pattern can be atmost 100000.Please suggest me a very fast alorithm on which i can start working to get this problem resolved.

Upvotes: 0

Views: 435

Answers (1)

Hdash
Hdash

Reputation: 51

You could try a Hamming distance algorithm, with distance = 1

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

Upvotes: 1

Related Questions