. Proof, Let D be the input set of 2-intervals and let T (D), T ? and T ?? be the trapezoid families as described in the above description of Unl-{<

D. Also, {. Op-t-the-maximum, . ?}-comparable, D. Subset, |. T. We-have et al., Let ?(G T ?? ) denote the size of the maximal independent set of G T ?? . Since G T ?? is a forest

|. T. ??, Thus, the maximum independent set of G T ?? is at least of size 1 6 |OP T |, and the promised approximation factor holds, Accumulating all these inequalities together we get

A. Unl-{< and . ?}-approx, D) Data : A set of 2-intervals D. Result : A {<, ?}-comparable subset of D. begin 1, Construct T (D), the corresponding trapezoid set of D

T. Compute and . ??, a strongly proper subset of T ? , such that |T ??

G. Compute, T. ??, . Maximum, G. Set, and . ??, return the set of 2-intervals corresponding to the maximum independent set of G T ?? . end Fig. 6. A schematic description of algorithm Unl-{<

T. Complexity and . Let, Steps 1-2 in Unl-{<, ?}-Approx can be computed in O(n lg n) time by a similar analysis of the time complexity of {<

T. Akutsu, Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots, Discrete Applied Mathematics, vol.104, issue.1-3, pp.45-62, 2000.
DOI : 10.1016/S0166-218X(00)00186-4

R. Bar-yehuda, M. M. Halldorsson, J. Naor, H. Shachnai, and I. Shapira, Scheduling spit intervals, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.732-741, 2002.
DOI : 10.1137/s0097539703437843
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.3108

G. Blin, G. Fertin, and S. Vialette, New Results for the 2-Interval Pattern Problem, Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, pp.311-322, 2004.
DOI : 10.1007/978-3-540-27801-6_23
URL : https://hal.archives-ouvertes.fr/hal-00620366

I. Dagan, M. C. Golumbic, and R. Y. Pinter, Trapezoid graphs and their coloring, Discrete Applied Mathematics, vol.21, issue.1, pp.35-46, 1988.
DOI : 10.1016/0166-218X(88)90032-7
URL : http://doi.org/10.1016/0166-218x(88)90032-7

S. Felsner, R. Müller, and L. Wernisch, Trapezoid graphs and generalizations, geometry and algorithms, Discrete Applied Mathematics, vol.74, issue.1, pp.13-32, 1997.
DOI : 10.1016/S0166-218X(96)00013-3
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.5459

F. Gavril, Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph, SIAM Journal on Computing, vol.1, issue.2, pp.180-187, 1972.
DOI : 10.1137/0201013

M. C. Golumbic, Algorithmic graph theory and perfect graphs, 1980.

S. Ieong, M. Y. Kao, T. W. Lam, W. K. Sung, and S. M. Yiu, Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs, Proceedings 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering (BIBE 2001), pp.183-190, 2002.
DOI : 10.1109/BIBE.2001.974428

R. B. Lyngsø and C. N. Pedersen, RNA Pseudoknot Prediction in Energy-Based Models, Journal of Computational Biology, vol.7, issue.3-4, pp.409-428, 2000.
DOI : 10.1089/106652700750050862

T. A. Mckee and F. R. Mcmorris, Topics in intersection graph theory. SIAM monographs on discrete mathematics and applications, 1999.

S. Vialette, On the computational complexity of 2-interval pattern matching problems, Theoretical Computer Science, vol.312, issue.2-3, pp.335-379, 2004.
DOI : 10.1016/j.tcs.2003.08.010