Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
biochemistry, genetics and molecular biology
A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions
BMC Bioinformatics, Volume 9, Article 516, Year 2008
Notification
URL copied to clipboard!
Description
Background: Due to recent progress in genome sequencing, more and more data for phylogenetic reconstruction based on rearrangement distances between genomes become available. However, this phylogenetic reconstruction is a very challenging task. For the most simple distance measures (the breakpoint distance and the reversal distance), the problem is NP-hard even if one considers only three genomes. Results: In this paper, we present a new heuristic algorithm that directly constructs a phylogenetic tree w.r.t. the weighted reversal and transposition distance. Experimental results on previously published datasets show that constructing phylogenetic trees in this way results in better trees than constructing the trees w.r.t. the reversal distance, and recalculating the weight of the trees with the weighted reversal and transposition distance. An implementation of the algorithm can be obtained from the authors. Conclusion: The possibility of creating phylogenetic trees directly w.r.t. the weighted reversal and transposition distance results in biologically more realistic scenarios. Our algorithm can solve today's most challenging biological datasets in a reasonable amount of time. © 2008 Bader et al; licensee BioMed Central Ltd.
Authors & Co-Authors
Bader, Martin
Germany, Ulm
Universität Ulm
Abouelhoda, Mohamed Ibrahim
Egypt, Cairo
Faculty of Engineering
Egypt, 6th October
Nile University
Ohlebusch, Enno
Germany, Ulm
Universität Ulm
Statistics
Citations: 21
Authors: 3
Affiliations: 3
Identifiers
Doi:
10.1186/1471-2105-9-516
e-ISSN:
14712105