RAxML

RAxML (zkratka Randomized Axelerated Maximum Likelihood, volně přeloženo: Náhodně akcelerovaná metoda maximální věrohodnosti) je populární bioinformatický program určený k rekonstrukci fylogenetických stromů na základě molekulárních dat (např. DNA, RNA nebo proteinových sekvencí). Využívá metodu maximální věrohodnosti (Maximum Likelihood, ML), která hledá takovou topologii stromu a evoluční parametry, jež nejlépe vysvětlují pozorovaná data. Program vytvořil Alexandros Stamatakis kolem roku 2000 a první publikace o něm vyšla v roce 2005.

RAxML-NG

Vývojář	Alexey M. Kozlov, Diego Darriba, Tomáš Flouri, Benoit Morel, Alexandros Stamatakis
První vydání	2019
Aktuální verze	RAxML-NG 1.2.2
Operační systém	Linux / Unix macOS Windows

RAxML

Vývojář	Alexandros Stamatakis
První vydání	2005
Aktuální verze	RAxML version 8.2.13
Operační systém	Linux/Unix macOS Windows

Mezi hlavní výhody programu patří vysoká rychlost, díky níž je možné efektivně pracovat i s velmi rozsáhlými datovými soubory. Novější verze RAxML version 8.0.0 navíc vykazují nižší nároky na paměť. Nevýhodou je naopak citlivost na kvalitu vstupních dat a také absence časového odhadu diverzifikace.

Na původní RAxML navázal v roce 2019 modernější kód RAxML-NG (RAxML Next Generation). Ten vznikl jako snaha spojit výhody klasického RAxML a vysoce výkonného ExaML (Exascale Maximum Likelihood), který byl optimalizován pro práci na superpočítačích. RAxML-NG přináší nejen vylepšený algoritmus a rozšířené funkce, ale také vyšší efektivitu a škálovatelnost, díky čemuž se stal přirozeným nástupcem původní implementace.

Historie

Program RAxML vznikl jako reakce na rychlý nárůst genetických dat o různorodých organismech, která lze využít k sestavení tzv. fylogenetických stromů, které umožňují odvozovat evoluční vztahy mezi druhy. Ačkoli v té době již existovaly metody pro jejich výpočet (např. Metoda maximální věrohodnosti), nebyly tyto postupy navrženy pro velký počet taxonů. Při vyšším počtu druhů se totiž topologie stromu značně komplikuje, výpočetní náročnost prudce roste a snižuje se účinnost věrohodnostní funkce. Výsledkem bylo, že konstrukce stromů byla prakticky omezená na zhruba 150-230 taxonů.

RAxML vychází z původního programu PAxML (Parallel A(x)ccelerated Maximum Likelihood), který byl sám o sobě velkým zlepšením a vykazoval zkrácení doby výpočtu o 25% - 65% ve srovnání se starším programem (paralelní fastDNAml) přičemž získané výsledky zůstaly zcela totožné. Cílem zavedení první verze programu RAxML-III bylo tedy získat stejně dobré nebo lepší hodnoty věrohodnosti než v PAxML, a to za ještě kratší dobu díky využití vylepšených heuristik pro prohledávání topologií.

Další generace programu vyšla už v roce 2006 pod názvem RAxML-VI-HPC (v2.0.1) určená pro výpočty na výkonných počítačových systémech. Tato verze byla výrazně rychlejší než předchozí díky jednoduchým, ale účinným technickým optimalizacím a mírně upravenému algoritmu prohledávání. Navíc umožňovala paralelní bootstrapping a provádění více odvozování na různých výchozích stromech v prostředí PC clusterů. Mezi nové funkce patřila podpora bifurkujících a multifurkujících omezujících stromů, stejně jako možnost přiřazovat a odhadovat samostatné parametry modelu pro jednotlivé geny ve vícestupňových zarovnáních (tzv. partitioned models). Hlavním přínosem této verze však byla schopnost spolehlivě počítat velmi velké stromy s více než 1000 taxony.

Nejnovější vydání, RAxML version 8.0.0, bylo publikováno v roce 2014. Přineslo několik zásadních vylepšení, včetně různých metod výpočtu bootstrapové podpory (standardní, SH-like a RELL bootstrap). Kromě DNA a proteinových dat tato verze podporuje také binární a vícestavová morfologická data a RNA data. Rozšířena byla i sada substitučních modelů pro proteiny a program navíc umí automaticky doporučit nejvhodnější model. Přibyly i dva algoritmy určené pro zpracování a analýzu dat z tzv. Next-generation sequencing (NGS). Verze 8.0.0 je úspornější z hlediska paměti, umožňuje rychlé i méně důkladné vyhledávání stromů u dat obsahujících desetitisíce taxonů, dokáže odhadovat marginální stavy předků a nově nabízí i algoritmus pro ukotvení stromů (rooting).

Na RAxML navázal ExaML (Exascale Maximum Likelihood), což je v podstatě varianta původního programu. Tato verze byla však primárně navržena pro vysoký výkon na superpočítačích a postrádala některé základní fylogenetické funkce (např. bootstraping), a navíc byla složitější na použití. Kombinací výhod RAxML a ExaML vznikl roku 2019 kód RAxML-NG (RAxML Next Generation), který je využitelný jak na standardních zařízeních, tak na superpočítačích. Spojuje efektivitu ExaML s plnou funkcionalitou RAxML a přináší navíc vyšší uživatelskou přívětivost. RAxML-NG mimo jiné nově podporuje všechny klasické substituční modely a umožňuje odhady délek větví. Dále došlo k vylepšení algoritmu pro vyhledávání podstromů (převzatého z IQ-Tree) a k implementaci nové metriky podpory větví.

Algoritmus

RAxML využívá heuristiky, které optimalizují věrohodnost výchozího stromu zahrnujícího všechny sekvence. Na rozdíl od jiných programů začíná s parsimoniálním stromem vytvořeným pomocí programu dnapars (DNA Parsimony; PHYLIP). Parsimoniální přístup často poskytuje výchozí strom s poměrně dobrou věrohodností a lze jej rychle vygenerovat metodou postupného přidávání. Náhodné pořadí vstupních sekvencí navíc umožňuje spustit více běhů s různými výchozími stromy, z nichž lze následně vytvořit konsenzuální strom.

Jádrem algoritmu je přeuspořádávání podstromů. Podstromy jsou odstraňovány z aktuálně nejlepší topologie a znovu vkládány do sousedních větví. RAxML přitom provádí rychlou lokální optimalizaci pouze u tří přilehlých větví. Následně uchovává 20 nejslibnějších stromů z jednoho kroku přeuspořádání a provádí globální optimalizaci pouze na nich. Tato strategie umožňuje prozkoumat více různorodých topologií v kratším čase a podporuje hlubší úroveň přeuspořádání.

Další zrychlení poskytuje strategie přijímání zlepšení v raných iteracích. RAxML okamžitě přijme novou topologii, pokud vykazuje vyšší věrohodnost, čímž urychluje konvergenci. Proces následně pokračuje se zvyšujícím se rozsahem přeuspořádání, dokud není nalezen strom s lepší věrohodností, nebo dokud není dosaženo maximální úrovně přeuspořádání.

Literatura

• Stamatakis, A., Ludwig, T., & Meier, H. (2005). RAxML-III: A fast program for maximum likelihood-based inference of large phylogenetic trees. Bioinformatics, 21(4), 456-463. https://doi.org/10.1093/bioinformatics/bti191
• Stamatakis, A. (2006). RAxML-VI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics, 22(21), 2688-2690. https://doi.org/10.1093/bioinformatics/btl446
• Stamatakis, A. (2014). RAxML version 8: A tool for phylogenetic analysis and post-analysis of large phylogenies. Bioinformatics, 30(9), 1312. https://doi.org/10.1093/bioinformatics/btu033
• Kozlov, A. M., Aberer, A. J., & Stamatakis, A. (2015). ExaML version 3: a tool for phylogenomic analyses on supercomputers. Bioinformatics, 31(15), 2577–2579. https://doi.org/10.1093/bioinformatics/btv184
• Kozlov, A. M., Darriba, D., Flouri, T., Morel, B., & Stamatakis, A. (2019). RAxML-NG: a fast, scalable and user-friendly tool for maximum likelihood phylogenetic inference. Bioinformatics, 35(21), 4453–4455. https://doi.org/10.1093/bioinformatics/btz305