Near-linear time edit distance for indel channels

DOI10.4230/LIPICS.WABI.2020.17zbMath1518.92108MaRDI QIDQ6487652

Arun Ganesh, Aaron Sy

Publication date: 7 February 2023

zbMATH Keywords

dynamic programmingaverage-case analysissequence alignmentedit distance

Mathematics Subject Classification ID

Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Unnamed Item
• Global alignment of molecular sequences via ancestral state reconstruction
• A faster algorithm computing string edit distances
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• A sublinear algorithm for weakly approximating edit distance
• Oblivious string embeddings and edit distance approximations
• Incremental String Comparison
• Approximating Edit Distance in Near-Linear Time
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal sequence length requirements for phylogenetic tree reconstruction with indels
• Efficiently Approximating Edit Distance Between Pseudorandom Strings

This page was built for publication: Near-linear time edit distance for indel channels