 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints
Abstract : In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally satisfies some secondary structure constraints, the so-called MRSO problem introduced in [3]. Since the MRSO problem is known to be APX-hard [8], Bongartz proposed in [8] to attack the problem using the concept of parameterized complexity. We prove in this paper that the MRSO problem is fixed-parameter tractable parameterized by the number of degree 3 vertices or by the number of crossing edges in the implied structure graph. This latter result answers an open problem posed in [8]. Aiming at precisely defining the complexity landscape of the problem, we refine the NP-hardness result of [3] and complement this result by showing that the MRSO problem is fixed-parameter tractable parameterized by an additional parameter. Finally, we present a fixed parameter algorithm parameterized by the similarity score in a restrictive model.
Cited literature [19 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00620363
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:00:09 PM
Last modification on : Wednesday, October 14, 2020 - 3:57:06 AM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:29 AM
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:00:09 PM
Last modification on : Wednesday, October 14, 2020 - 3:57:06 AM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:29 AM
File
hal.pdf
Files produced by the author(s)