| The median problems on linear multichromosomal genomes: graph representation and fast exact solutions. | |
| | |
MedLine Citation:
|
PMID: 20874404 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
In genome rearrangement, given a set of genomes G and a distance measure d, the median problem asks for another genome q that minimizes the total distance [Formula: see text]. This is a key problem in genome rearrangement based phylogenetic analysis. Although this problem is known to be NP-hard, we have shown in a previous article, on circular genomes and under the DCJ distance measure, that a family of patterns in the given genomes--represented by adequate subgraphs--allow us to rapidly find exact solutions to the median problem in a decomposition approach. In this article, we extend this result to the case of linear multichromosomal genomes, in order to solve more interesting problems on eukaryotic nuclear genomes. A multi-way capping problem in the linear multichromosomal case imposes an extra computational challenge on top of the difficulty in the circular case, and this difficulty has been underestimated in our previous study and is addressed in this article. We represent the median problem by the capped multiple breakpoint graph, extend the adequate subgraphs into the capped adequate subgraphs, and prove optimality-preserving decomposition theorems, which give us the tools to solve the median problem and the multi-way capping optimization problem together. We also develop an exact algorithm ASMedian-linear, which iteratively detects instances of (capped) adequate subgraphs and decomposes problems into subproblems. Tested on simulated data, ASMedian-linear can rapidly solve most problems with up to several thousand genes, and it also can provide optimal or near-optimal solutions to the median problem under the reversal/HP distance measures. ASMedian-linear is available at http://sites.google.com/site/andrewweixu . |
| | |
Authors:
|
Andrew Wei Xu |
Related Documents
:
|
8799854 - A developmental conceptualization of clinical problem solving. 20307134 - Social support, problem solving, and the longitudinal course of newlywed marriage. 17282784 - Mnr method with self-determined regularization parameters for solving inverse resistivi... 15967024 - Effective ambiguity checking in biosequence analysis. 9924524 - Community pharmacist perspectives on hiv/aids and interventions for injection drug user... 14626754 - Do community pharmacists influence prescribing? |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 17 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2010 Sep |
Date Detail:
|
Created Date: 2010-09-29 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 1195-211 Citation Subset: IM |
Affiliation:
|
School of Computer and Communication Sciences, Swiss Federal Institute of Technology, Lausanne, Switzerland. wei.xu@epfl.ch |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Finding nested common intervals efficiently.
Next Document: Rearrangement models and single-cut operations.