On the computational complexity of 2-interval pattern matching problems

DOI10.1016/j.tcs.2003.08.010zbMath1070.68052MaRDI 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-completeness; RNA secondary structure; Pattern matching; 2-Interval

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D20: Protein sequences, DNA sequences

Related Items

On Recovering Syntenic Blocks from Comparative Maps, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Complexity issues in color-preserving graph embeddings, 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, On recovering syntenic blocks from comparative maps, Extracting constrained 2-interval subsets in 2-interval sets

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