Sellers Pattern-matching algorithm
S S Sturrock
sss at castle.ed.ac.uk
Mon Mar 22 09:02:42 EST 1993
In article <1993Mar22.121811.2388 at crc.ac.uk> k-hatric at nimr.mrc.ac.uk (Kerr Hatrick) writes:
> the sequence is "puzzledPhDstudent" and the pattern is
> "student" the distance is 0. When the sequence and pattern
Yeah, zero changes to fit student into puzzledPhDstudent.
> are switched, the distance is 10 (using Identity Distance
10 changes to fit puzzledPhDstudent into student. ie delete puzzledPhD.
> Matrix, gap penalty = insertion penalty = 1). The increased
> distance is due to the cost of inserting "puzzledPhD".
or deleting it.
> Can anyone suggest a way of modifying the algorithm so that
> d(a,b) = d(b,a)?
No, not really. Maybe you should consider a local similarity algorithm
where the two sequences are not require to be virtually the same size.
Shane Sturrock, Biocomputing Research Unit, Darwin Building, Mayfield Road,
University of Edinburgh, Scotland, Commonwealth of Independent Kingdoms. :-)
Civilisation is a Haggis Supper with salt and sauce and a bottle of Irn Bru.
More information about the Bio-soft