A sum-over-paths extension of edit distances accounting for all sequence alignments
(2011) Pattern Recognition — Vol. 44, n° 6, p. 1172-1182 (2011)
Files
1-s20-S0031320310005650-main.pdf
Restricted Access - Adobe PDF
- 558.1 KB
ASumoverPathsExtensionofEditDistancesAccountingforAllSequenceAlignments.pdf
Restricted Access - Adobe PDF
- 323.87 KB
Details
- Authors
- Abstract
- This paper introduces a simple Sum-over-Paths (SoP) formulation of string editdistancesaccounting for all possible alignments between two sequences, and extends related previous work from bioinformatics to the case of graphs with cycles. Each alignment℘, with a total cost C(℘), is assigned a probability of occurrence P(℘)=exp[−θC(℘)]/Z where Z is a normalization factor. Therefore, good alignments (having a low cost) are favored over bad alignments (having a high cost). The expected cost ∑℘∈PC(℘)exp[−θC(℘)]/Z computed over all possible alignments℘∈P defines the SoP editdistance. When θ→∞, only the best alignments matter and the measure reduces to the standard editdistance. The rationale behind this definition is the following: for some applications, two sequences sharing many good alignments should be considered as more similar than two sequences having only one single good, optimal, alignment in common. In other words, sub-optimal alignments could also be taken into account. Forward/backward recurrences allowing to efficiently compute the expected cost are developed. Virtually any Viterbi-like sequence comparison algorithm computed on a lattice can be generalized in the same way; for instance, a SoP longest common subsequence is also developed. Pattern classification tasks performed on five data sets show that the new measures usually outperform the standard ones and, in any case, never perform significantly worse, at the expense of tuning the parameter θ.
- Affiliations
Citations
Garcia Diez, S., Fouss, F., Shimbo, M., & Saerens, M. (2011). A sum-over-paths extension of edit distances accounting for all sequence alignments. Pattern Recognition, 44(6), 1172-1182. https://doi.org/10.1016/j.patcog.2010.11.020 (Original work published 2011)