Regular Language Constrained Sequence Alignment Revisited

DOI10.1007/978-3-642-19222-7_39zbMath1326.68373OpenAlexW2134478093WikidataQ58064496 ScholiaQ58064496MaRDI QIDQ3000526

Gregory Kucherov, Michal Ziv-Ukelson, Tamar Pinhas

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_39

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items

A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Algorithms for path-constrained sequence alignment ⋮ Practical regular expression constrained sequence alignment

Cites Work

• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Regular expression constrained sequence alignment
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem
• The Steiner problem with edge lengths 1 and 2
• The Steiner problem in phylogeny is NP-complete
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
• Efficient algorithms for regular expression constrained sequence alignment
• An Algorithm for the Computation of Linear Forms
• Regular Expressions and NFAs Without ε-Transitions
• Implementation and Application of Automata
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Multicast algorithms for hypercube multiprocessors
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata