What Makes the Arc-Preserving Subsequence Problem Hard?

Guillaume Blin (1) , Guillaume Fertin (2) , Romeo Rizzi (3) , Stéphane Vialette (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LINA - Laboratoire d'Informatique de Nantes Atlantique
3 DIMI - Dipartimento di Matematica e Informatica - Universita Udine

Given two arc-annotated sequences (S, P ) and (T, Q) representing RNA structures, the Arc-Preserving Subsequence (APS) problem asks whether (T, Q) can be obtained from (S, P ) by deleting some of its bases (together with their incident arcs, if any). In previous studies [3, 6], this problem has been naturally divided into subproblems reflecting intrinsic complexity of arc structures. We show that APS(Crossing, Plain) is NP-complete, thereby answering an open problem [6]. Furthermore, to get more insight into where actual border of APS hardness is, we refine APS classical subproblems in much the same way as in [11] and give a complete categorization among various restrictions of APS problem complexity.

Domaines: Algorithme et structure de données [cs.DS]

Guillaume Blin, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette. What Makes the Arc-Preserving Subsequence Problem Hard?. 5th Int. Workshop on Bioinformatics Research and Applications (IWBRA'05), May 2005, Atlanta, GA, USA, United States. pp.860-868. ⟨hal-00620359⟩