|Perl: the Markov chain saw|
Re^3: Mismatch Positions of Ambiguous Stringby hv (Parson)
|on Apr 27, 2006 at 10:16 UTC||Need Help??|
But doesn't work. Where did I go wrong?
It isn't as simple as that: my original approach relied on treating each ambiguous [ACGT] in the source string as a regexp, but to do that it needs to know a) which is the fixed string and which the regexp, and b) that they are not both regexps.
The simplest extension is as below, but this suffers further on speed - it will probably be too slow if you're dealing with strings a few thousand base pairs long:
This says: if source is not ambiguous, treat the corresponding fragment of the target as a regexp; else if the target is not ambiguous, treat the source fragment as a regexp; else check a full intersection of the two.
If your strings only include ACGT, a more efficient approach would be to transform each string into a bit vector that sets a bit for each base that may be present:
Once the strings are transformed into this bitwise representation, checking for mismatches is very fast even with long strings.