One of the combinatorial models for the biological problem of inferring gene regulation networks is the Maximum Gene Regulatory Network Problem, shortly MGRN, proposed by Skiena et al. The problem is NP-hard, consequently the attention has shifted towards approximation algorithms, leading to a polynomial-time 1/2-approximation algorithm, while no upper bound on the possible approximation ratio was previously known. In this paper we make a first step towards closing the gap between the best known and the best possible approximation factors, by showing that no polynomial-time approximation algorithm can have a factor better than 1-1/(8(1+e^2)) unless RP=NP.

Pozzi, S., DELLA VEDOVA, G., Mauri, G. (2005). An Explicit Upper Bound for the Approximation Ratio of the Maximum Gene Regulatory Network Problem. In Computational Methods in Systems Biology, International Conference CMSB 2004 (pp.1-8). Springer Verlag [10.1007/978-3-540-25974-9_1].

An Explicit Upper Bound for the Approximation Ratio of the Maximum Gene Regulatory Network Problem

DELLA VEDOVA, GIANLUCA;MAURI, GIANCARLO
2005

Abstract

One of the combinatorial models for the biological problem of inferring gene regulation networks is the Maximum Gene Regulatory Network Problem, shortly MGRN, proposed by Skiena et al. The problem is NP-hard, consequently the attention has shifted towards approximation algorithms, leading to a polynomial-time 1/2-approximation algorithm, while no upper bound on the possible approximation ratio was previously known. In this paper we make a first step towards closing the gap between the best known and the best possible approximation factors, by showing that no polynomial-time approximation algorithm can have a factor better than 1-1/(8(1+e^2)) unless RP=NP.
paper
Gene regulatory network problem; inapproximability
English
International Conference on Computational Methods in Systems Biology, CMSB 2004
2004
Computational Methods in Systems Biology, International Conference CMSB 2004
3-540-25375-0
2005
3082
1
8
none
Pozzi, S., DELLA VEDOVA, G., Mauri, G. (2005). An Explicit Upper Bound for the Approximation Ratio of the Maximum Gene Regulatory Network Problem. In Computational Methods in Systems Biology, International Conference CMSB 2004 (pp.1-8). Springer Verlag [10.1007/978-3-540-25974-9_1].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/1595
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
Social impact