What Makes the Arc-Preserving Subsequence Problem Hard?

Abstract : 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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download

Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:01:41 PM
Last modification on : Wednesday, May 23, 2018 - 3:44:02 PM
Document(s) archivé(s) le : Saturday, December 31, 2011 - 2:21:16 AM


Files produced by the author(s)


  • HAL Id : hal-00620359, version 1


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⟩



Record views


Files downloads