Výpočetní fylogenetika je aplikace výpočetních algoritmů, metod a programů k fylogenetickým analýzám. Cílem je sestavit fylogenetický strom představující hypotézu o evolučních předcích souboru genů, druhů nebo jiných taxonů. Tyto techniky byly například použity k prozkoumání rodokmenu hominidních druhů a vztahů mezi specifickými geny sdílenými mnoha typy organismů. Tradiční fylogenetika se opírá o morfologické údaje získané měřením a kvantifikací fenotypových vlastností reprezentativních organismů, zatímco novější obor molekulární fylogenetiky používá jako základ pro klasifikaci nukleotidové sekvence kódující geny nebo sekvence aminokyselin kódující proteiny. Mnohé formy molekulární fylogenetiky jsou úzce spjaty s uspořádáním sekvencí při konstrukci a rafinaci fylogenetických stromů, které se používají ke klasifikaci evolučních vztahů mezi homologními geny zastoupenými v genomech rozdílných druhů. Je nepravděpodobné, že by fylogenetické stromy konstruované výpočetními metodami dokonale reprodukovaly evoluční strom, který představuje historické vztahy mezi analyzovanými druhy. Historický druhový strom se také může lišit od historického stromu jednotlivého homologního genu sdíleného těmito druhy.
Produkce fylogenetického stromu vyžaduje míru homologie mezi charakteristikami sdílenými srovnávanými taxony. V morfologických studiích to vyžaduje explicitní rozhodnutí o tom, které fyzikální charakteristiky měřit a jak je používat ke kódování odlišných stavů odpovídajících vstupním taxonům. V molekulárních studiích je primárním problémem vytvoření vícenásobného sekvenčního vyrovnání (MSA) mezi sledovanými geny nebo sekvencemi aminokyselin. Postupné metody sekvenčního vyrovnání produkují fylogenetický strom z nutnosti, protože do vypočítaného vyrovnání začleňují nové sekvence v pořadí podle genetické vzdálenosti.
Druhy fylogenetických stromů
Fylogenetické stromy generované výpočetní fylogenetikou mohou být buď zakořeněné, nebo nezakořeněné v závislosti na vstupních datech a použitém algoritmu. Kořenový strom je směrovaný graf, který explicitně identifikuje posledního společného předka (MRCA), obvykle jde o imputovanou sekvenci, která není ve vstupu zastoupena. Měřítka genetické vzdálenosti mohou být použita k zakreslení stromu se vstupními sekvencemi jako listovými uzly a jejich vzdáleností od kořene úměrnou jejich genetické vzdálenosti od hypotetického MRCA. Identifikace kořene obvykle vyžaduje zahrnutí alespoň jedné „výstupní skupiny“ do vstupních dat, o níž je známo, že se jen vzdáleně vztahuje k sledovaným sekvencím.
Naproti tomu nezakořeněné stromy vykreslují vzdálenosti a vztahy mezi vstupními sekvencemi, aniž by vytvářely předpoklady ohledně jejich sestupu. Nezakořeněný strom může být vždy vytvořen z zakořeněného stromu, ale kořen nemůže být obvykle umístěn na nezakořeněný strom bez dodatečných údajů o divergenci, jako je předpoklad hypotézy molekulárních hodin.
Sadu všech možných fylogenetických stromů pro danou skupinu vstupních sekvencí lze pojmout jako diskrétně definovaný multidimenzionální „stromový prostor“, přes který lze dohledávat cesty pomocí optimalizačních algoritmů. I když počítání celkového počtu stromů pro netriviální počet vstupních sekvencí může být komplikované změnami v definici topologie stromu, vždy platí, že pro daný počet vstupů a volbu parametrů existuje více zakořeněných než nezakořeněných stromů.
Kódování znaků a definování homologie
Základním problémem morfologické fylogenetiky je sestavení matice představující mapování z každého taxonu porovnávaného s reprezentativními měřeními pro každou fenotypovou charakteristiku používanou jako třídič. Typy fenotypových dat použitých pro konstrukci této matice závisí na porovnávaných taxonech; pro jednotlivé druhy mohou zahrnovat měření průměrné velikosti těla, délky nebo velikosti konkrétních kostí nebo jiných fyzikálních znaků, nebo dokonce behaviorálních projevů. Samozřejmě, protože ne všechny možné fenotypové charakteristiky mohly být změřeny a zakódovány pro analýzu, je výběr těch znaků, které mají být změřeny, hlavní inherentní překážkou metody. Rozhodnutí o tom, které znaky použít jako základ pro matici, nutně představuje hypotézu o tom, které znaky druhu nebo vyššího taxonu jsou evolučně relevantní. Morfologické studie mohou být zmateny příklady konvergentního vývoje fenotypů. Velkou výzvou při konstrukci užitečných tříd je vysoká pravděpodobnost mezitaxonového překrývání v rozložení variace fenotypu. Zahrnutí vyhynulých taxonů do morfologické analýzy je často obtížné kvůli absenci nebo neúplným fosilním záznamům, ale bylo prokázáno, že má významný vliv na produkované stromy; v jedné studii pouze zahrnutí vyhynulých druhů opic vytvořilo morfologicky odvozený strom, který byl konzistentní s tím, který byl vytvořen na základě molekulárních dat.
Některé fenotypové klasifikace, zejména ty, které se používají při analýze velmi různorodých skupin taxonů, jsou diskrétní a jednoznačné; klasifikace organismů jako organismů majících nebo postrádajících ocas je například ve většině případů přímočará, stejně jako počítání znaků, jako jsou oči nebo obratle. Nicméně nejvhodnější reprezentace kontinuálně se měnících fenotypových měření je kontroverzním problémem bez obecného řešení. Běžnou metodou je jednoduše roztřídit sledovaná měření do dvou nebo více tříd, čímž se kontinuální pozorované odchylky stanou diskrétně klasifikovatelnými (např. všechny příklady s kostmi pažních kostí delšími než daná mez jsou bodovány jako členové jednoho státu a všichni členové, jejichž kosti pažních kostí jsou kratší než mez, jsou bodovány jako členové druhého státu). Výsledkem je snadno manipulovatelný soubor dat, ale byl kritizován za špatné vykazování základu pro definice tříd a za obětování informací ve srovnání s metodami, které používají spojité vážené rozložení měření.
Problém kódování znaků je v molekulárních analýzách velmi odlišný, protože znaky v datech biologických sekvencí jsou okamžité a diskrétně definované – odlišné nukleotidy v sekvencích DNA nebo RNA a odlišné aminokyseliny v sekvencích proteinů. Definování homologie však může být náročné vzhledem k potížím spojeným s vícenásobným zarovnáním sekvencí. Pro danou rozevřenou MSA lze zkonstruovat několik zakořeněných fylogenetických stromů, které se liší ve svých interpretacích, které změny jsou „mutacemi“ oproti původnímu znaku a které události jsou mutacemi vkládání nebo mutacemi delece. Například při pouze párovém zarovnání s oblastí mezer není možné určit, zda jedna sekvence nese mutaci vkládání nebo druhá nese delece. Problém je zvětšen v MSA s nezařazenými a nepřekrývajícími se mezerami. V praxi mohou být v konstrukci fylogenetického stromu diskontovány rozměrné oblasti vypočteného zarovnání, aby se zabránilo integraci hlučných dat do výpočtu stromu.
Metody distanční matice fylogenetické analýzy se výslovně opírají o míru „genetické vzdálenosti“ mezi sekvencemi, které jsou klasifikovány, a proto vyžadují jako vstup MSA. Distance je často definována jako zlomek nesouladu na zarovnaných pozicích, přičemž mezery jsou buď ignorovány, nebo započítány jako nesoulad. Distanční metody se pokoušejí sestrojit matici vše-vše z množiny sekvenčních dotazů popisujících vzdálenost mezi jednotlivými sekvenčními páry. Z toho je sestrojen fylogenetický strom, který umisťuje úzce související sekvence pod stejný vnitřní uzel a jehož délka větví věrně reprodukuje pozorované vzdálenosti mezi sekvencemi. Metody distanční matice mohou v závislosti na algoritmu použitém k jejich výpočtu produkovat buď zakořeněné, nebo nezkořeněné stromy. Často jsou používány jako základ pro progresivní a iterativní typy vícenásobných sekvenčních zarovnání. Hlavní nevýhodou metod distanční matice je jejich neschopnost efektivně využívat informace o lokálních oblastech s vysokou variací, které se objevují napříč více podstromy.
Metody sdružování sousedů používají obecné techniky sdružování dat pro sekvenční analýzu s využitím genetické vzdálenosti jako metriky sdružování. Jednoduchá metoda sdružování sousedů produkuje nezakořeněné stromy, ale nepředpokládá konstantní rychlost vývoje (tj. molekulární hodiny) napříč rodokmeny. Její příbuzná, UPGMA (Metoda nevážené párové skupiny s aritmetickým průměrem) produkuje zakořeněné stromy a vyžaduje předpoklad konstantní rychlosti – to znamená, že předpokládá ultrametrický strom, ve kterém jsou vzdálenosti od kořene ke každému vrcholu větve stejné.
Metoda Fitch-Margoliash používá pro shlukování na základě genetické vzdálenosti metodu nejmenších čtverců. Těsně příbuzným sekvencím je při konstrukci stromu přikládána větší váha, aby se opravila zvýšená nepřesnost při měření vzdáleností mezi vzdáleně příbuznými sekvencemi. Vzdálenosti použité jako vstup do algoritmu musí být normalizovány, aby se zabránilo velkým artefaktům ve výpočetních vztazích mezi úzce příbuznými a vzdáleně příbuznými skupinami. Vzdálenosti vypočítané touto metodou musí být lineární; kritérium linearity pro vzdálenosti vyžaduje, aby se očekávané hodnoty délek větví pro dvě jednotlivé větve rovnaly očekávané hodnotě součtu dvou vzdáleností větví – což je vlastnost, která platí pro biologické sekvence pouze tehdy, když byly korigovány na možnost zpětných mutací na jednotlivých místech. Tato korekce se provádí pomocí substituční matice, která je odvozena z Jukes-Cantorova modelu evoluce DNA. Korekce vzdáleností je v praxi nutná pouze tehdy, když se míry evoluce liší mezi větvemi. Jiná modifikace algoritmu může být užitečná, zejména v případě koncentrovaných vzdáleností (hlaste se prosím do Koncentrace jevu měření a Prokletí dimenzionality): tato modifikace, popsaná v, prokazatelně zlepšuje efektivitu algoritmu a jeho robustnost.
Kritérium nejmenších čtverců aplikované na tyto vzdálenosti je přesnější, ale méně efektivní než metody spojování sousedů. Dodatečné vylepšení, které opravuje korelace mezi vzdálenostmi, které vznikají z mnoha úzce souvisejících sekvencí v datové sadě, může být také aplikováno se zvýšenými výpočetními náklady. Nalezení optimálního stromu nejmenších čtverců s jakýmkoliv korekčním faktorem je NP-kompletní, takže heuristické vyhledávací metody jako ty, které se používají v analýze maximální parsimonie, jsou aplikovány na vyhledávání ve stromovém prostoru.
Nezávislé informace o vztahu mezi sekvencemi nebo skupinami mohou být použity k tomu, aby se zmenšil prostor pro vyhledávání stromů a zakořenily nezkořeněné stromy. Standardní použití metod distanční matice zahrnuje zahrnutí alespoň jedné sekvence outgroup, o níž je známo, že se jen vzdáleně vztahuje k zájmovým sekvencím v množině dotazů. Toto použití lze považovat za typ experimentální kontroly. Pokud byla outgroup vhodně vybrána, bude mít mnohem větší genetickou vzdálenost, a tedy delší délku větve než kterákoli jiná sekvence, a objeví se v blízkosti kořene kořenového stromu. Volba vhodné outgroup vyžaduje výběr sekvence, která se mírně vztahuje k zájmovým sekvencím; příliš těsný vztah maří účel outgroup a příliš vzdálená přidá analýze šum. Je třeba také dbát na to, aby nedocházelo k situacím, kdy druhy, z nichž byly sekvence odebrány, jsou vzdáleně příbuzné, ale gen kódovaný sekvencemi je vysoce konzervován napříč rodokmeny. Horizontální přenos genů, zejména mezi jinak rozdílnými bakteriemi, může také zmást použití výstupní skupiny.
Maximální parsimonie (MP) je metoda identifikace potenciálního fylogenetického stromu, která vyžaduje co nejmenší celkový počet evolučních událostí k vysvětlení pozorovaných sekvenčních dat. Některé způsoby bodování stromů také zahrnují „náklady“ spojené s konkrétními typy evolučních událostí a pokus o nalezení stromu s co nejmenšími celkovými náklady. To je užitečný přístup v případech, kdy není každý možný typ události stejně pravděpodobný – například když je známo, že konkrétní nukleotidy nebo aminokyseliny jsou mutovatelnější než ostatní.
Nejnaivnější způsob identifikace nejprimitivnějšího stromu je jednoduchý výčet – zvážení každého možného stromu za sebou a hledání stromu s nejmenším skóre. To je však možné pouze u relativně malého počtu sekvencí nebo druhů, protože problém identifikace nejprimitivnějšího stromu je známý jako NP-hard; následně byla vyvinuta řada heuristických metod vyhledávání pro optimalizaci, aby se našel strom vysoce prétavý, ne-li nejlepší v množině. Většina takových metod zahrnuje mechanismus minimalizace ve stylu nejstrmějšího klesání fungující na kritériu přeskupení stromu.
Větvičkový a vázaný algoritmus je obecná metoda používaná ke zvýšení efektivity hledání téměř optimálních řešení NP-tvrdých problémů, poprvé aplikovaných na fylogenetiku na počátku 80. let. Větvička a vázaný je obzvláště vhodný pro stavbu fylogenetického stromu, protože ze své podstaty vyžaduje rozdělení problému do stromové struktury, protože rozděluje problémový prostor na menší oblasti. Jak jeho název napovídá, vyžaduje jako vstup jak pravidlo větvení (v případě fylogenetiky přidání dalšího druhu nebo sekvence do stromu), tak vázanost (pravidlo, které vylučuje určité oblasti vyhledávacího prostoru z úvah, čímž předpokládá, že optimální řešení nemůže obsadit tuto oblast). Identifikace dobré vázanosti je nejnáročnějším aspektem aplikace algoritmu na fylogenetiku. Jednoduchý způsob definování vázanosti je maximální počet předpokládaných evolučních změn povolených na strom. Soubor kritérií známých jako Žarkikova pravidla výrazně omezují prostor pro vyhledávání definováním charakteristik sdílených všemi kandidáty „nejprimitivnějšími“ stromy. Dvě nejzákladnější pravidla vyžadují odstranění všech nadbytečných sekvencí kromě jedné (pro případy, kdy více pozorování přineslo totožná data) a odstranění znakových míst, na kterých se nevyskytují dva nebo více stavů alespoň u dvou druhů. Za ideálních podmínek by tato pravidla a s nimi spojený algoritmus zcela definovaly strom.
Sankoffův-Morelův-Cedergrenův algoritmus
Sankoff-Morel-Cedergrenův algoritmus byl mezi prvními publikovanými metodami, které současně vytvořily MSA a fylogenetický strom pro nukleotidové sekvence. Metoda používá výpočet maximální parsimonie ve spojení s bodovací funkcí, která penalizuje mezery a neshody, čímž upřednostňuje strom, který zavádí minimální počet takových událostí. imputované sekvence ve vnitřních uzlech stromu jsou bodovány a sečteny přes všechny uzly v každém možném stromu. Součet nejnižších bodovacích stromů poskytuje optimální strom i optimální MSA vzhledem k bodovací funkci. Protože metoda je vysoce výpočetně náročná, přibližná metoda, při které jsou počáteční odhady pro vnitřní zarovnání zpřesňovány po jednom uzlu. Úplná i přibližná verze jsou v praxi vypočítány dynamickým programováním.
Novější metody fylogenetického stromu/MSA používají heuristiky k izolaci stromů s vysokým skóre, ale ne nutně optimálních. Metoda MALIGN používá techniku maximální parsimonie k výpočtu vícenásobného zarovnání pomocí maximalizace kladogramového skóre a její průvodce POY používá iterační metodu, která spojuje optimalizaci fylogenetického stromu se zlepšeními v odpovídající MSA. Nicméně použití těchto metod při konstrukci evolučních hypotéz bylo kritizováno jako neobjektivní kvůli záměrné konstrukci stromů odrážející minimální evoluční události.
Metoda maximální pravděpodobnosti používá standardní statistické techniky pro odvození rozdělení pravděpodobnosti, aby přiřadila pravděpodobnosti konkrétním možným fylogenetickým stromům. Metoda vyžaduje substituční model pro posouzení pravděpodobnosti konkrétních mutací; zhruba strom, který vyžaduje více mutací na vnitřních uzlech, aby vysvětlil pozorovanou fylogenezi, bude vyhodnocen jako strom s nižší pravděpodobností. To je zhruba podobné metodě maximální parsimonie, ale maximální pravděpodobnost umožňuje dodatečnou statistickou flexibilitu tím, že umožňuje různou rychlost evoluce napříč rodokmeny i lokalitami. Metoda ve skutečnosti vyžaduje, aby evoluce na různých místech a podél různých rodokmenů byla statisticky nezávislá. Maximální pravděpodobnost se tak dobře hodí pro analýzu vzdáleně souvisejících sekvencí, ale protože formálně vyžaduje hledání všech možných kombinací topologie stromů a délky větví, je výpočetně nákladné provádět ji na více než několika sekvencích.
Algoritmus „prořezávání“, což je varianta dynamického programování, se často používá k redukci vyhledávacího prostoru efektivním výpočtem pravděpodobnosti podstromů. Metoda vypočítává pravděpodobnost pro každou lokalitu „lineárním“ způsobem, počínaje uzlem, jehož jedinými potomky jsou listy (tedy špičky stromu) a postupuje pozpátku směrem k „spodnímu“ uzlu ve vnořených množinách. Stromy vytvořené metodou jsou však zakořeněny pouze v případě, že je substituční model nevratný, což obecně neplatí pro biologické systémy. Vyhledávání stromu s maximální pravděpodobností zahrnuje také komponentu optimalizace délky větve, kterou je obtížné algoritmicky vylepšit; často se používají obecné globální optimalizační nástroje, jako je Newton-Raphsonova metoda. Vyhledávání topologií stromů definovaných podle pravděpodobnosti nebylo prokázáno jako NP-úplné, ale zůstává extrémně náročné, protože hledání větví a vázaných větví zatím není efektivní pro takto zastoupené stromy.
Bayesovská inference může být použita k produkci fylogenetických stromů způsobem úzce souvisejícím s metodami maximální pravděpodobnosti. Bayesovské metody předpokládají předchozí rozdělení pravděpodobnosti možných stromů, což může být jednoduše pravděpodobnost jakéhokoli jednoho stromu mezi všemi možnými stromy, které by mohly být generovány z dat, nebo může být sofistikovanější odhad odvozený z předpokladu, že divergenční události, jako je speciace, se vyskytují jako stochastické procesy. Volba předchozí distribuce je sporným bodem mezi uživateli Bayesovsko-inferenčních fylogenetických metod.
Implementace bayesovských metod obecně používají Markovův řetěz Monte Carlo vzorkovací algoritmy, i když výběr sady tahů se liší; výběry používané v bayesovské fylogenetice zahrnují kruhově permutující listové uzly navrhovaného stromu v každém kroku a výměnu potomků podstromů náhodného vnitřního uzlu mezi dvěma příbuznými stromy. Použití bayesovských metod v fylogenetice bylo kontroverzní, především kvůli neúplné specifikaci výběru sady tahů, akceptačnímu kritériu a předchozí distribuci v publikované práci.
Metody molekulární fylogenetiky se opírají o definovaný substituční model, který kóduje hypotézu o relativních mírách mutací na různých místech podél zkoumaného genu nebo sekvencí aminokyselin. Ve své nejjednodušší podobě mají substituční modely za cíl korigovat rozdíly v mírách přechodů a transverzí v nukleotidových sekvencích. Použití substitučních modelů je vynuceno skutečností, že genetická vzdálenost mezi dvěma sekvencemi se lineárně zvyšuje jen krátkou dobu poté, co se od sebe obě sekvence odchýlí (alternativně je vzdálenost lineární jen krátce před koalescencí). Čím delší je doba po divergence, tím je pravděpodobnější, že se dvě mutace vyskytnou ve stejném nukleotidovém místě. Jednoduché výpočty genetické vzdálenosti tak sníží počet mutačních událostí, které se vyskytly v evoluční historii. Rozsah tohoto snížení se zvyšuje s rostoucí dobou od divergence, což může vést k jevu přitahování dlouhých větví, nebo nesprávnému přiřazení dvou vzdáleně příbuzných, ale konvergentně se vyvíjejících sekvencí jako úzce příbuzných. Metoda maximální parsimonie je k tomuto problému obzvláště náchylná díky svému explicitnímu hledání stromu představujícího minimální počet odlišných evolučních událostí.
Všechny substituční modely přiřazují sadu vah každé možné změně stavu zastoupené v posloupnosti. Nejčastější typy modelů jsou implicitně reverzibilní, protože přiřazují stejnou váhu například mutaci nukleotidu G>C jako mutaci C>G. Nejjednodušší možný model, Jukes-Cantorův model, přiřazuje stejnou pravděpodobnost každé možné změně stavu pro danou nukleotidovou bázi. Rychlost změny mezi jakýmikoli dvěma odlišnými nukleotidy bude jedna třetina celkové substituční rychlosti. Pokročilejší modely rozlišují mezi přechody a transverzemi. Nejobecnější možný model s časovou reverzibilitou, nazývaný GTR model, má šest parametrů mutační rychlosti. Ještě zobecněnější model známý jako obecný model s 12 parametry porušuje časovou reverzibilitu za cenu mnohem větší složitosti při výpočtu genetických vzdáleností, které jsou konzistentní mezi více rodokmeny. Jedna z možných variací na toto téma upravuje míry tak, aby se celkový obsah GC – důležité měřítko stability dvoušroubovice DNA – měnil v čase.
Modely mohou také umožňovat variaci rychlostí s pozicemi ve vstupní sekvenci. Nejnápadnější příklad takové variace vyplývá z uspořádání nukleotidů v genech kódujících proteiny do tříbázových kodonů. Je-li známo umístění otevřeného čtecího rámce (ORF), může být míra mutace upravena pro pozici daného místa v kodonu, protože je známo, že rozviklané párování bází může umožnit vyšší míru mutace ve třetím nukleotidu daného kodonu, aniž by to ovlivnilo význam kodonu v genetickém kódu. Příklad méně založený na hypotézách, který nespoléhá na identifikaci ORF, jednoduše přiřadí každému místu rychlost náhodně vybranou z předem určeného rozdělení, často gama rozdělení nebo log-normální rozdělení. A konečně, konzervativnější odhad variací rychlostí známý jako metoda covarionu umožňuje autokorelované variace rychlostí, takže míra mutace daného místa je korelována napříč místy a rodokmeny.
Výběr vhodného modelu je kritický pro tvorbu dobrých fylogenetických analýz, jednak proto, že nedostatečně parametrizované nebo příliš restriktivní modely mohou produkovat aberantní chování, když jsou porušeny jejich základní předpoklady, a také proto, že příliš složité nebo nadměrně parametrizované modely jsou výpočetně drahé a parametry mohou být nadměrně složité. Nejběžnější metodou výběru modelu je test poměru pravděpodobnosti (LRT), který vytváří odhad pravděpodobnosti, který lze interpretovat jako měřítko „vhodnosti“ mezi modelem a vstupními daty. Při používání těchto výsledků je však třeba dbát opatrnosti, protože složitější model s více parametry bude mít vždy vyšší pravděpodobnost než zjednodušená verze stejného modelu, což může vést k naivnímu výběru modelů, které jsou příliš složité. Z tohoto důvodu počítačové programy pro výběr modelu zvolí nejjednodušší model, který není výrazně horší než složitější substituční modely. Významnou nevýhodou LRT je nutnost provádět sérii párových srovnání mezi modely; bylo prokázáno, že pořadí, ve kterém jsou modely porovnávány, má zásadní vliv na ten, který je nakonec vybrán.
Alternativní metodou výběru modelu je Akaikeho informační kritérium (AIC), formálně odhad Kullbackova-Leiblerova rozdílu mezi skutečným modelem a testovaným modelem. Lze jej interpretovat jako odhad pravděpodobnosti s korekčním faktorem penalizujícím nadparametrizované modely. AIC se vypočítává spíše na individuálním modelu než na páru, takže je nezávislý na pořadí, v jakém jsou modely hodnoceny. Podobnou základní interpretaci má i související alternativa, Bayesovo informační kritérium (BIC), které však složité modely penalizuje více.