Abstract | ||
---|---|---|
The wide adoption of Next-Generation Sequencing technologies in recent years has generated an avalanche of genetic data, which poses new challenges for large-scale maximum likelihood-based phylogenetic analyses. Improving the scalability of search algorithms and reducing the high memory requirements for computing the likelihood represent major computational challenges in this context. We have introduced methods for solving these key problems and provided respective proof-of-concept implementations. Moreover, we have developed a new tree search strategy that can reduce run times by more than 50% while yielding equally good trees (in the statistical sense). To reduce memory requirements, we explored the applicability of external memory (out of-core) algorithms as well as a concept that trades memory for additional computations in the likelihood function. The latter concept, only induces a surprisingly small increase in overall execution times. When trading 50% of the required RAM for additional computations, the average execution time increase --because of additional computations -- amounts to only 15%. All concepts presented here are sufficiently generic such that they can be applied to all programs that rely on the phylogenetic likelihood function. Thereby, the approaches we have developed will contribute to enable large-scale inferences of whole-genome phylogenies. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/IPDPSW.2012.309 | IPDPS Workshops |
Keywords | Field | DocType |
high memory requirement,large-scale inference,maximum likelihood,phylogenetic likelihood function,external memory,likelihood function,large-scale maximum,memory requirement,additional computation,latter concept,huge trees,average execution time increase,dna,algorithm design and analysis,maximum likelihood estimation,vegetation,vectors,memory management,ram,phylogeny | Search algorithm,Computer science,High memory,Theoretical computer science,Memory management,Artificial intelligence,Algorithm design,Likelihood function,Inference,Parallel computing,Machine learning,Scalability,Auxiliary memory | Conference |
ISSN | Citations | PageRank |
2164-7062 | 0 | 0.34 |
References | Authors | |
4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fernando Izquierdo-Carrasco | 1 | 39 | 5.31 |
Alexandros Stamatakis | 2 | 995 | 96.27 |