A sum-over-paths extension of edit distances accounting for all sequence alignments

DOI10.1016/j.patcog.2010.11.020zbMath1209.68454OpenAlexW2058068872MaRDI QIDQ632613

Silvia García-Díez, Masashi Shimbo, Marco Saerens, François Fouss

Publication date: 25 March 2011

Published in: Pattern Recognition (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.patcog.2010.11.020

zbMATH Keywords

dynamic programmingshortest pathapproximate string matchingViterbi algorithmsequence comparisonedit distancelongest common subsequence

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10) Algorithms on strings (68W32)

Related Items

Graph-based point drift: graph centrality on the registration of point-sets ⋮ Design of biased random walks on a graph with application to collaborative recommendation ⋮ A bag-of-paths framework for network data analysis ⋮ Sparse randomized shortest paths routing with Tsallis divergence regularization

Uses Software

• LIBLINEAR
• CONTRAlign

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modern multidimensional scaling: theory and applications
• Entropy maximization for Markov and semi-Markov processes
• Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree
• Learning stochastic edit distance: application in handwritten character recognition
• Entropy Rate and Maximum Entropy Methods for Countable Semi-Markov Chains
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• CONTRAlign: Discriminative Training for Protein Sequence Alignment
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition
• Biological Sequence Analysis
• Algorithms on Strings, Trees and Sequences
• The entropy of Markov trajectories
• The String-to-String Correction Problem
• 10.1162/153244303322533197
• Fastest Mixing Markov Chain on a Graph
• Randomized Shortest-Path Problems: Two Related Models