Inapproximability results for the lateral gene transfer problem

Bhaskar Dasgupta (), Sergio Ferrarini (), Uthra Gopalakrishnan () and Nisha Raj Paryani ()
Additional contact information
Bhaskar Dasgupta: University of Illinois at Chicago
Sergio Ferrarini: Politecnico di Milano
Uthra Gopalakrishnan: University of Illinois at Chicago
Nisha Raj Paryani: University of Illinois at Chicago

Journal of Combinatorial Optimization, 2006, vol. 11, issue 4, No 3, 387-405

Abstract: Abstract This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following: (a) We show that it is not possible to approximate the problem in polynomial time within an approximation ratio of 1 + ε, for some constant ε > 0 unless P = NP. We also provide explicit values of ε for the above claim. (b) We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound.

Keywords: Lateral gene transfer; Phylogeny; Inapproximability (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-8212-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:11:y:2006:i:4:d:10.1007_s10878-006-8212-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-8212-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().