Consequences of Faster Alignment of Sequences

2014/01/01 by Amir Abboud, Virginia Vassilevska Williams, Oren Weimann · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Clique #Combinatorics #Computer science #Data structure #Discrete mathematics #Edit distance #Function (biology) #Genomics and Phylogenetic Studies #Longest common subsequence problem #Longest increasing subsequence #Mathematics #RNA and protein synthesis mechanisms #String (physics) #Subsequence #Substring #Upper and lower bounds

paper · doi:10.1007/978-3-662-43948-7_4

crossref issued 2014/01/01 · crossref published 2014/01/01 · crossref published-print 2014/01/01 · openalex publication_date 2014/01/01 · crossref created 2014/06/11 · crossref deposited 2025/05/03 · openalex created_date 2025/10/10 · crossref indexed 2026/06/10 · openalex updated_date 2026/08/04

Citations

• Algorithms on Strings, Trees and Sequences
• Space-Efficient Las Vegas Algorithms for K-SUM
• A faster algorithm computing string edit distances
• An improved exponential-time algorithm for k -SAT
• Subquadratic Algorithms for 3SUM
• Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
• Basic local alignment search tool
• Finding, minimizing, and counting weighted subgraphs
• Identification of common molecular subsequences
• Towards polynomial lower bounds for dynamic problems
• A probabilistic algorithm for k-SAT and constraint satisfaction problems
• On Problems as Hard as CNF-SAT
• On a class of O(n2) problems in computational geometry

Cited by

• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
• Linear Time Subsequence and Supersequence Regex Matching
• Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
• Computational hardness assumption [wikipedia]