A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem

DOI10.1007/s10878-006-9024-6zbMath1123.68146OpenAlexW1974900495MaRDI QIDQ996823

Ming-Hui Jiang

Publication date: 19 July 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-006-9024-6

zbMATH Keywords

Approximation algorithmsRNA secondary structure prediction2-Interval

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

Related Items

Parameterized complexity of two-interval pattern problem ⋮ On recovering syntenic blocks from comparative maps ⋮ On Recovering Syntenic Blocks from Comparative Maps

Cites Work

• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• On the computational complexity of 2-interval pattern matching problems
• Combinatorial Pattern Matching
• Algorithms – ESA 2005
• Algorithms and Computation