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 mailing list