title: Optimization strategies for fast detection of positive selection on phylogenetic trees.
abstract: The detection of positive selection is widely used to study gene and genome evolution, but its application remains limited by the high computational cost of existing implementations. We present a series of computational optimizations for more efficient estimation of the likelihood function on large-scale phylogenetic problems. We illustrate our approach using the branch-site model of codon evolution.
  
  
  
  We introduce novel optimization techniques that substantially outperform both CodeML from the PAML package and our previously optimized sequential version SlimCodeML. These techniques can also be applied to other likelihood-based phylogeny software. Our implementation scales well for large numbers of codons and/or species. It can therefore analyse substantially larger datasets than CodeML. We evaluated FastCodeML on different platforms and measured average sequential speedups of FastCodeML (single-threaded) versus CodeML of up to 5.8, average speedups of FastCodeML (multi-threaded) versus CodeML on a single node (shared memory) of up to 36.9 for 12 CPU cores, and average speedups of the distributed FastCodeML versus CodeML of up to 170.9 on eight nodes (96 CPU cores in total).
  
  
  
  ftp://ftp.vital-it.ch/tools/FastCodeML/ CONTACT: selectome@unil.ch or nicolas.salamin@unil.ch.
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Mario
authors.initials: M
authors.lastname: Valle
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Hannes
authors.initials: H
authors.lastname: Schabauer
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Christoph
authors.initials: C
authors.lastname: Pacher
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Heinz
authors.initials: H
authors.lastname: Stockinger
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Alexandros
authors.initials: A
authors.lastname: Stamatakis
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Marc
authors.initials: M
authors.lastname: Robinson-Rechavi
authors.affiliation: Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany Swiss National Supercomputing Centre, Scientific Computing Group, Lugano, Switzerland, Department of Ecology and Evolution, University of Lausanne, Lausanne, Switzerland, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, AIT Austrian Institute of Technology, Safety & Security Department, Vienna, Austria, Vital-IT Group, SIB Swiss Institute of Bioinformatics, Lausanne, Switzerland, Heidelberg Institute for Theoretical Studies, Scientific Computing Group and Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
authors.forename: Nicolas
authors.initials: N
authors.lastname: Salamin
mesh_terms: D000465:Algorithms; D003062:Codon; D019295:Computational Biology; D019143:Evolution, Molecular; D016013:Likelihood Functions; D010802:Phylogeny; D012641:Selection, Genetic; D012984:Software
chemical_list: D003062:Codon