UNSPECIFIED. (2001) The complexity of gene placement. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 41 (2). pp. 225-243. ISSN 0196-6774

Full text not available from this repository.

Abstract

We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on the DNA sequence of given species for potential gene positions. The simultaneous analysis of gene intervals in related species, e.g., human and mouse, may eliminate some of the ambiguities and lead to better estimates of gene locations. We address the problem of eliminating the ambiguities in gene orders by means of minimizing the number of conserved regions among the species. This is equivalent to the problem of choosing gene coordinates (gene placement) that satisfy the genetic mapping constraints minimize the breakpoint distance between genomes. We first show that the gene ordering problem is hard: there is no polynomial-time approximation scheme unless P = NP, even under the restrictions that: (1) the order of genes in one of species is known, or (2) at most two intervals overlap at any location on the map of any of the species. Then we provide two polynomial-time algorithms under restriction (1) above; the first approximates the problem within a factor of 3, and the second exactly solves the problem under the additional restriction that (3) no more than O((log n)/(log log n)) intervals overlap at a location on the map of any of the species. We also prove the tractability of the general problem when ther is a single conserved region (i.e., when there exists a gene placement resulting in identical gene orders). (C) 2001 Elsevier Science.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Journal or Publication Title:	JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
Publisher:	ACADEMIC PRESS INC
ISSN:	0196-6774
Date:	November 2001
Volume:	41
Number:	2
Number of Pages:	19
Page Range:	pp. 225-243
Identification Number:	10.1006/jagm.2001.1172
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/11474

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item