UNSPECIFIED (1999) The complexity of gene placement. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms, BALTIMORE, MD, JAN 17-19, 1999. Published in: PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS pp. 386-395.

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 genetic sequence of git en species for potential gene positions. The simultaneous analysis of gene intervals in related species, e.g., man 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 (synteny) regions among the species. We first show that the gene ordering problem is hard: there is no polynomial-time approximation scheme unless P = SP, even under the restrictions that: (1) the order of genes in one of the 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. me also prove the tractability of the general problem when there is a single conserved region.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Journal or Publication Title:	PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
Publisher:	SIAM
ISBN:	0-89871-434-6
Date:	1999
Number of Pages:	10
Page Range:	pp. 386-395
Publication Status:	Published
Title of Event:	10th Annual ACM-SIAM Symposium on Discrete Algorithms
Location of Event:	BALTIMORE, MD
Date(s) of Event:	JAN 17-19, 1999
URI:	http://wrap.warwick.ac.uk/id/eprint/13864

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item