Using Hirschberg's algorithm to generate random alignments of strings

DOI10.1016/0020-0190(94)90004-3MaRDI QIDQ1336757zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

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

Recommendations

• General space-efficient sampling algorithm for suboptimal alignment
• A randomized algorithm for approximate string matching
• scientific article; zbMATH DE number 434724
• A versatile divide and conquer technique for optimal string alignment
• Near-linear time edit distance for indel channels

Cites work

• scientific article; zbMATH DE number 3845091 (Why is no real title available?)
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A linear space algorithm for computing maximal common subsequences
• An algorithm for the distance between two finite sequences
• Monte Carlo sampling methods using Markov chains and their applications

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336757)