Detailansicht
Improving the IQ-TREE tree search with dynamic NNI perturbations
Daniel Sirianni
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Bioinformatik
Betreuer*in
Ivo Hofacker
Mitbetreuer*in
Heiko Andreas Schmidt
DOI
10.25365/thesis.80150
URN
urn:nbn:at:at-ubw:1-20878.29340.367756-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die Rekonstruktion phylogenetischer Stammbäume für große Datensätze stellt aufgrund des exponentiellen Wachstums der möglichen Baumtopologien mit zunehmender Anzahl von Sequenzen eine große numerische Herausforderung dar. Um diese Komplexität zu bewältigen, sind heuristische Suchverfahren unumgänglich, die es ermöglichen, phylogenetische Bäume aus großen Alignments zu rekonstruieren. Trotz der Verfügbarkeit leistungsfähiger Softwarelösungen erlaubt die heuristische Natur dieser Algorithmen keine verlässliche Aussage darüber, ob tatsächlich ein global optimaler Baum gefunden wurde. Um das Risiko zu verringern, in lokalen Optima zu enden, können stochastische Elemente in den Suchprozess integriert werden. IQ-TREE adressiert dieses Problem, indem lokal optimale Bäume zufällig perturbiert werden, wodurch eine umfangreichere Exploration des Suchraums möglich wird. Da die Effizienz unterschiedlicher Perturbationsstärken jedoch von Datensatz zu Datensatz variiert, existiert keine universell optimale Perturbationsstärke. Daher schlagen wir zwei Strategien zur dynamischen Anpassung der Perturbationsstärke während eines IQ-TREE-Laufs vor. Die Success Driven Perturbation (SDP) Strategie passt die Perturbationsstärke an die beobachtete Erfolgsrate an, welche an der Häufigkeit erfolgreicher Aktualisierungen der Kandidatenmenge gemessen wird. Die Performance Weighted Sampling (PWS) Strategie hingegen passt die Auswahlwahrscheinlichkeiten vordefinierter Perturbationsstärken basierend auf deren beobachteter Leistungsfähigkeit an. Unsere Ergebnisse zeigen, dass eine dynamische Anpassung der Perturbationsstärke in bis zu 88.2% der getesteten Datensätze zu Bäumen mit verbesserten Likelihood-Werten führt. Diese Verbesserungen gehen jedoch mit einer deutlichen Erhöhung der Laufzeit einher. Um weitere Verbesserungen zu erzielen, nutzen wir maschinelles Lernen zur Vorhersage geeigneter Perturbationsstärken. Obwohl die Vorhersagegenauigkeit derzeit begrenzt ist, erwarten wir, dass zusätzliche Trainingsdaten die Genauigkeit des Modells deutlich steigern werden. Die Kombination dynamischer Perturbationsstrategien mit maschinell vorhergesagten Startwerten führte zu einer Verbesserung der PWS Strategie, während sich die Ergebnisse der SDP Strategie verschlechterten. Mögliche Erklärungen für diese Ergebnisse werden in der Arbeit diskutiert. Die PWS Strategie übertraf Methoden mit konstanter, geschätzter oder voreingestellter Perturbationsstärke und erzielte in mindestens 72% der Datensätze bessere Ergebnisse. Zwar erwies sich die SDP Strategie bei einigen großen Datensätzen als überlegen, doch lieferte PWS über die Mehrheit der Datensätze hinweg (60.87%) bessere Ergebnisse. Angesichts dieser Ergebnisse und aufgrund der Schwierigkeit, die optimale Perturbationsstärke für ein Alignment verlässlich vorherzusagen, empfehlen wir, die PWS Strategie in IQ-TREE zu integrieren.
Abstract
(Englisch)
Due to the super-exponential growth of phylogenetic tree space with increasing numbers of taxa, heuristic methods are necessary for inferring well-supported phylogenetic trees from large sequence alignments. Although several fast programs exist, their reliance on heuristics makes it unclear whether the optimal tree has been found. To reduce the risk of getting trapped in local optima, stochastic elements can be introduced. IQ-TREE address this challenge through a random nearest neighbor interchange (NNI) step, which perturbs candidate trees to facilitate broader exploration of the tree space. The extent of this perturbation is controlled by a parameter known as the perturbation strength. However, the effectiveness of different perturbation strengths varies across datasets, indicating that no single setting is universally optimal. To overcome this limitation, we propose two strategies for dynamically adjusting the perturbation strength during an IQ-TREE run. The Success Driven Perturbation (SDP) strategy adapts the perturbation strength according to the observed success rate, measured as the rate at which the candidate set is successfully updated. The Performance Weighted Sampling (PWS) strategy adjusts the sampling probabilities of predefined perturbation strengths according to their observed performance. Our results show that dynamically adjusting the perturbation strength yields phylogenies with improved likelihood values in up to 88.2% of the datasets. However, this improvement is accompanied by a substantial increase in runtime. To further improve the results, we explore the use of machine learning to predict suitable perturbation strengths based on features of the input data. While prediction accuracy remains limited, we expect that incorporating more training data will substantially enhance predictive performance. Combining dynamic perturbation strategies with machine learning based initialization improved the effectiveness of the PWS approach but reduced the performance of the SDP strategy. Possible explanations for these outcomes are discussed in the thesis. The PWS strategy outperformed methods using a constant perturbation strength whether estimated or default. It achieves better results in at least 72% of the tested datasets. Although the SDP strategy proved superior on certain large datasets, PWS achieved better results across the majority of the datasets (60.87%). Considering these results and the challenge of predicting optimal perturbation strengths for an input alignment, we recommend incorporating the PWS strategy into the IQ-TREE software.
Schlagwörter
Schlagwörter
(Deutsch)
Phylogenie Phylogenomik Bioinformatik Molekularbiologie Evolutionsbiologie Sequenzanalyse Phylogenetische Stammbäume Rekonstruktion von Stammbäumen
Schlagwörter
(Englisch)
Phylogeny Phylogenomics Bioinformatics Molecular Biology Evolutionary Biology Sequence Analysis Evolutionary Trees Phylogenetic Inference
Autor*innen
Daniel Sirianni
Haupttitel (Englisch)
Improving the IQ-TREE tree search with dynamic NNI perturbations
Publikationsjahr
2025
Umfangsangabe
x, 104 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Ivo Hofacker
Klassifikationen
42 Biologie > 42.13 Molekularbiologie ,
54 Informatik > 54.81 Anwendungssoftware
AC Nummer
AC17763796
Utheses ID
78877
Studienkennzahl
UA | 066 | 875 | |