Regular language constrained sequence alignment revisited

DOI10.1007/978-3-642-19222-7_39MaRDI QIDQ3000526zbMATH OpenOpenAlexWikidataFDO

Authors Gregory Kucherov, Tamar Pinhas, Michal Ziv-Ukelson

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

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

Recommendations

• Regular expression constrained sequence alignment
• Efficient Algorithms for Regular Expression Constrained Sequence Alignment
• Efficient algorithms for regular expression constrained sequence alignment
• Combinatorial Pattern Matching
• Practical regular expression constrained sequence alignment

Cites work

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

Cited in

(10)

• Algorithms for path-constrained sequence alignment
• Combinatorial Pattern Matching
• Regular expression constrained sequence alignment
• Efficient Algorithms for Regular Expression Constrained Sequence Alignment
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Efficient algorithms for regular expression constrained sequence alignment
• Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics
• Relational Sequence Alignments and Logos
• Practical regular expression constrained sequence alignment
• \textsc{AStarix}: fast and optimal sequence-to-graph alignment

This page was built for publication: Regular language constrained sequence alignment revisited

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