| Sorting by reversals, generalized transpositions, and translocations using permutation groups. | |
| | |
MedLine Citation:
|
PMID: 20500022 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
In this article, we consider the problem of sorting a linear/circular, multi-chromosomal genome by reversals, block-interchanges (i.e., generalized transpositions), and translocations (including fusions and fissions) where the used operations can be weighted differently, which aims to find a sequence of reversal, block-interchange, and translocation operations such that the sum of these operation weights in the sequence is minimum. It is known that this sorting problem can be solved in polynomial time on the basis of breakpoint graphs, when block-interchanges are weighted 2 (or >or=3) and the others are weighted 1. In this study, we design a novel and easily implemented algorithm for this problem by utilizing the permutation group theory in algebra. |
| | |
Authors:
|
Yen-Lin Huang; Chin Lung Lu |
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 May |
Date Detail:
|
Created Date: 2010-05-26 Completed Date: 2010-08-30 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 685-705 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Gene Rearrangement* Genome* Mathematics Models, Genetic Sequence Analysis, DNA Translocation, Genetic* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Protein-protein interaction network evaluation for identifying potential drug targets.
Next Document: Evaluation of the Interaction of Cyclin-Dependent Kinase 5 with Activator p25 and with p25-Derived I...