Near-linear time edit distance for indel channels

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

Authors: 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 (4)

• The smoothed complexity of edit distance
• Using Hirschberg's algorithm to generate random alignments of strings
• A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
• 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)