Sellers Pattern-matching algorithm

S S Sturrock sss at
Mon Mar 22 09:02:42 EST 1993

In article <1993Mar22.121811.2388 at> k-hatric at (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 mailing list