| A 1.375-approximation algorithm for sorting by transpositions. | |
| | |
MedLine Citation:
|
PMID: 17085846 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations. |
| | |
Authors:
|
Isaac Elias; Tzvika Hartman |
Related Documents
:
|
1101396 - Practical aspects of a cholera surveillance programme. 8664226 - Prk in patients with a keratoconic topography picture. the concept of a physiological '... 8635296 - Vaginal ultrasound for the practicing clinician. equipment selection. 18694586 - Enhancement of filterability in mbr achieved by improvement of supernatant and floc cha... 10870186 - 3-acetylaltholactone and related styryl-lactones, mitochondrial respiratory chain inhib... 17186146 - Bacterial community structure of biofilms on artificial surfaces in an estuary. |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 3 ISSN: 1545-5963 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2006 Oct-Dec |
Date Detail:
|
Created Date: 2006-11-06 Completed Date: 2007-01-04 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 369-79 Citation Subset: IM |
Affiliation:
|
Department of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden. isaac@nada.kth.se |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Chromosome Mapping / methods* DNA Mutational Analysis / methods* DNA Transposable Elements / genetics* Evolution, Molecular* Linkage Disequilibrium / genetics* Sequence Analysis, DNA / methods* |
| Chemical | |
Reg. No./Substance:
|
0/DNA Transposable Elements |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Motif search in graphs: application to metabolic networks.
Next Document: New bounds and tractable instances for the transposition distance.