Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Friday, September 30, 2011 - 4:01:41 PM
Last modification on : Wednesday, April 27, 2022 - 3:49:03 AM
Long-term archiving on: : 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