Using Hirschberg's algorithm to generate random alignments of strings

DOI10.1016/0020-0190(94)90004-3zbMath0803.92021DBLPjournals/ipl/Allison94OpenAlexW2054578869WikidataQ62654282 ScholiaQ62654282MaRDI QIDQ1336757

Lloyd Allison

Publication date: 3 January 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90004-3

zbMATH Keywords

Gibbs samplingedit distancelongest common subsequence problemLCSalignment algorithmDNA stringsLCSSrandom alignmentsstatistical estimation of evolutionary distancesstring alignments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Discrete mathematics in relation to computer science (68R99)

Cites Work

• An algorithm for the distance between two finite sequences
• A linear space algorithm for computing maximal common subsequences
• Monte Carlo sampling methods using Markov chains and their applications
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using Hirschberg's algorithm to generate random alignments of strings