Submit a preprint

Title *

MaxTiC: Fast ranking of a phylogenetic tree by Maximum Time Consistency with lateral gene transfersuse asterix (*) to get italics

Authors *

Cédric Chauve, Akbar Rafiey, Adrian A. Davin, Celine Scornavacca, Philippe Veber, Bastien Boussau, Gergely J Szöllosi, Vincent Daubin, and Eric TannierPlease use the format "First name initials family name" as in "Marie S. Curie, Niels H. D. Bohr, Albert Einstein, John R. R. Tolkien, Donna T. Strickland"

Year *

2017

Picture *

Abstract *

Lateral gene transfers (LGTs) between ancient species contain information about the relative timing of species diversification. Specifically, the ancestors of a donor species must have existed before the descendants of the recipient species. Hence, the detection of a LGT event can be translated into a time constraint between nodes of a phylogeny if donors and recipients can be identified. When a set of LGTs are detected by interpreting the phylogenetic discordance between gene trees and a species tree, the set of all deduced time constraints can be used to order totally the internal nodes and thus produce a ranked tree. Unfortunately LGT detection is still very challenging and current methods produce a significant proportion of false positives. As a result the set of time constraints is not always compatible with a ranked species tree. We propose an optimization method, which we call MaxTiC (Maximum Time Consistency), for obtaining a ranked species tree compatible with a maximum number of time constraints. The problem in general inherits NP-completeness from feedback arc sets. However we give an exact polynomial time method based on dynamic programming to compute an optimal ranked binary tree supposing that its two children are ranked. We turn this principle into a heuristic to solve the general problem and test it on simulated datasets. Under a wide range of conditions, which we compare to biological datasets, the obtained ranked tree is very close to the real one, confirming the theoretical possibility of dating in the history of life with transfers by maximizing time consistency. MaxTiC is available within the ALE package: https://github.com/ssolo/ALE/tree/master/misc.

Indicate the full web address (DOI or URL) giving public access to these data (if you have any problems with the deposit of your data, please contact contact@evolbiol.peercommunityin.org). In case all raw data are included in the preprint, indicate the DOI or URL of the preprint. *

You should fill this box only if you chose 'All or part of the results presented in this preprint are based on data'. URL must start with http:// or https://

Indicate the full web address (DOI or URL) giving public access to these scripts (if you have any problems with the deposit of your scripts, please contact contact@evolbiol.peercommunityin.org). In case all raw scripts are included in the preprint, indicate the DOI or URL of the preprint. *

You should fill this box only if you chose 'Scripts were used to obtain or analyze the results'. URL must start with http:// or https://

Indicate the full web address (DOI, SWHID or URL) giving public access to these codes (if you have any problems with the deposit of your codes, please contact contact@evolbiol.peercommunityin.org). In case all raw codes are included in the preprint, indicate the DOI or URL of the preprint. *

You should fill this box only if you chose 'Codes have been used in this study'. URL must start with http:// or https://

Keywords (optional)

dating; simulations; phylogeny; optimization; transfer; reconciliation; ultrametric tree; algorithmics;

Methods that require specific expertise (optional)

NonePlease indicate the methods that may require specialised expertise during the peer review process (use a comma to separate various required expertises).

Thematic fields *

Bioinformatics & Computational Biology, Evolutionary Dynamics, Genome Evolution, Life History, Molecular Evolution, Phylogenetics / Phylogenomics

Suggested reviewers - Suggest up to 10 reviewers (provide names and Email addresses). (Optional)

e.g. John Doe john@doe.com

No need for them to be recommenders of PCIEvolBiol. Please do not suggest reviewers for whom there might be a conflict of interest. Reviewers are not allowed to review preprints written by close colleagues (with whom they have published in the last four years, with whom they have received joint funding in the last four years, or with whom they are currently writing a manuscript, or submitting a grant proposal), or by family members, friends, or anyone for whom bias might affect the nature of the review - see the code of conduct

Opposed reviewers - Suggest up to 5 people not to invite as reviewers. (Optional)

e.g. John Doe john@doe.com

Submission date

2017-06-28 13:40:52

Recommender

Tatiana Giraud

Reviewers

or Register
Submit a preprint

MANAGING BOARD

Guillaume Achaz
Juan Arroyo
Trine Bilde
Dustin Brisson
Marianne Elias
Inês Fragata
Matteo Fumagalli
Tatiana Giraud
Frédéric Guillaume
Ruth Hufbauer
Sara Magalhaes
Caroline Nieberding
Michael David Pirie
Tanja Pyhäjärvi

Fernando Racimo
Tanja Schwander
Alejandro Gonzalez Voyer

RECOMMENDERS

MANAGING BOARD

MEMBER OF

INDEXED BY