Near-linear time edit distance for indel channels

DOI10.4230/LIPICS.WABI.2020.17zbMATH Open1518.92108MaRDI QIDQ6487652FDOQ6487652

Arun Ganesh, Aaron Sy

Publication date: 7 February 2023

Recommendations

• The Smoothed Complexity of Edit Distance
• The smoothed complexity of edit distance
• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• scientific article; zbMATH DE number 3845091

zbMATH Keywords

dynamic programmingaverage-case analysisedit distancesequence alignment

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A faster algorithm computing string edit distances
• Incremental String Comparison
• 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
• Approximating Edit Distance in Near-Linear Time
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• Global alignment of molecular sequences via ancestral state reconstruction
• Efficiently Approximating Edit Distance Between Pseudorandom Strings
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal sequence length requirements for phylogenetic tree reconstruction with indels

Cited In (2)

• Using Hirschberg's algorithm to generate random alignments of strings
• The Smoothed Complexity of Edit Distance

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

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