On the computational complexity of 2-interval pattern matching problems

DOI10.1016/j.tcs.2003.08.010zbMath1070.68052OpenAlexW2043274817MaRDI QIDQ1884946

Stéphane Vialette

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.08.010

zbMATH Keywords

NP-completenessRNA secondary structurePattern matching2-Interval

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20)

Related Items

Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ Complexity issues in color-preserving graph embeddings ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Fast arc-annotated subsequence matching in linear space ⋮ Winner determination in geometrical combinatorial auctions ⋮ On recognising words that are squares for the shuffle product ⋮ Finding common RNA pseudoknot structures in polynomial time ⋮ Approximation of RNA multiple structural alignment ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ DARN! A weighted constraint solver for RNA motif localization ⋮ Finding common structured patterns in linear graphs ⋮ A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem ⋮ Improved algorithms for largest cardinality 2-interval pattern problem ⋮ On two open problems of 2-interval patterns ⋮ Parameterized complexity of two-interval pattern problem ⋮ On recovering syntenic blocks from comparative maps ⋮ On Recovering Syntenic Blocks from Comparative Maps

Uses Software

• Palingol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Recognizing graphs with fixed interval number is NP-complete
• RNA secondary structures and their prediction
• Trapezoid graphs and their coloring
• New clique and independent set algorithms for circle graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Topics in Intersection Graph Theory
• Ordered and Unordered Tree Inclusion
• Branch-and-Bound Methods: A Survey
• Algorithms for a maximum clique and a maximum independent set of a circle graph