[Bioperl-l] Fuzzy Pattern Matching Algorithm

[Aaron J. Mackey]

On Dec 10, 2004, at 6:04 AM, demerphq wrote:

> I suspect that one of the few places this code may actually prove
> useful is in the context of Bioperl. Im curious as to what solutions
> and scenarios such algorithms would be used in. For those who
> participated I believe most were purely interested as a Comp Sci
> problem and not actually for the utility of the solution itself so we
> really have no idea.

Typically, we need to do "fuzzy" matching by sequence motif or profile 
(i.e. position-specific, weighted matching), not this kind of 
k-mismatch, which are sometimes used as fast "seed"-finding steps in 
larger sequence search/alignment algorithms (you guys should check out 
the BLAT algorithm for kicks and giggles in approximate string 
matching).  There is also an extensive literature on these subjects, 
including the use of indexed trie's.

-Aaron

--
Aaron J. Mackey, Ph.D.
Dept. of Biology, Goddard 212
University of Pennsylvania       email:  amackey at pcbi.upenn.edu
415 S. University Avenue         office: 215-898-1205
Philadelphia, PA  19104-6017     fax:    215-746-6697