TreeShredder: a program for phylogenetic analysis of large sets of trees based on splits

Clement Bader

doi:10.25365/thesis.74014

You are here: University of Vienna PHAIDRA Detail o:1662679

Title (eng)

TreeShredder: a program for phylogenetic analysis of large sets of trees based on splits

Parallel title (deu)

TreeShredder: ein Program für die phylogenetische Analyse von großen Gruppen von Bäumen basierend auf Splits

Author

Clement Bader

Advisor

Arndt von Haeseler

Co-Advisor

Heiko A. Schmidt

Assessor

Arndt von Haeseler

Abstract (deu)

TreeShredder ist ein paralleles Multifunktionsprogramm für die phylogenetische Analyse großer Gruppen von Bäumen basierend auf ihren Splits. Es bietet bewährte Analysewerkzeuge und erweitert diese um zusätzliche, neuere Funktionen. Viele zeitintensive Funktionen, wie das Parsen einer großen Anzahl von Newick-Tree- Strings und das Berechnen von Transfer Bootstrap Expectation-Werten, können parallel ausgeführt werden. Ein platz- und zeitsparendes Dateiformat zur Speicherung und Wiederabrufung von Split- und Baum-Information, die TreeShredder- Datei, wird vorgestellt und ihre Vorteile demonstriert. TreeShredder führt eine Matrix-Representation-Funktion für die Supertree-Konstruktion wieder ein, die in den letzten Jahren nicht mehr gewartet und unterstützt wurde. TreeShredder bietet Referenz- und umfangreiche Konsensus-Baum-Funktionen, einschließlich des neu eingeführten globalen relativen Mehrheits-Konsensus-Baumes. Zusätzlich können User acht verschiedene Split-Maße, einschließlich Häufigkeitsraten, Internode Certainty, oder Transfer Bootstrap Expectation, aber auch die neu entwickelten Maße der Unterstützung des besten inkompatiblen Splits und die Differenz zur Unterstützung des besten inkompatiblen Splits auf Referenz- und Konsensus-Bäume projizieren. Einzigartig unter vergleichbarer Software findet TreeShredder kongruente Bäume und berechnet Kongruenz-Maße für eine Gruppe von vollständigen oder sogar unvollständigen Splits, als auch Kongruenz-Status der Splits der Bäume. Zusammen mit der Robinson-Foulds-Distanzen-Funktion, die Ähnlichkeiten zwischen Baumtopologien anzeigt, wird ein neues Maß namens Split Co-Occurrence eingeführt, das zeigt, wie oft zwei Splits gleichzeitig im selben Baum auftreten. Platzsparende Ausgabekomprimierung bleibt ohne Laufzeiterhöhung. TreeShredder schneidet im Vergleich mit RAxML und BOOSTER positiv ab, insbesondere, aber nicht nur, wenn die phylogenetische Analyse von einer TreeShredder-Datei gestartet wird. Anhand von diversen Gruppen von Bäumen, die dutzende bis tausende Taxa groß sind, zeige ich, dass TreeShredder eine wertvolle und versatile Erweiterung des Repertoires der phylogenetischen Analyse ist.

Abstract (eng)

TreeShredder is a parallelized multi-tool software for the phylogenetic analysis of large sets of trees based on their splits. TreeShredder can deal with datasets of millions of trees with thousands of taxa. It offers well-established analysis approaches and extends them by additional, more recently introduced features. Many time-consuming procedures, such as parsing huge numbers of Newick tree strings, or calculating Transfer Bootstrap Expectation values, are parallelized. A space and time-saving file format for split and tree information storage and retrieval, the TreeShredder file, is introduced and its advantages are demonstrated. TreeShredder implements a matrix representation feature for supertree construction, which has seen discontinued maintenance and support of capable software in recent years. TreeShredder offers comprehensive reference tree and consensus tree features, including the newly introduced global relative majority consensus tree. Additionally, the user can map eight different split measures, including occurrence rates, Internode Certainty, or Transfer Bootstrap Expectation, but also newly developed measures such as a split’s best incompatible split’s support and the difference in their support, onto the reference and consensus trees. Unique among competitor software in the field, TreeShredder can find based on a set of splits or even incomplete spits congruent trees, determine the congruency status with the splits in the trees, and calculate congruency measures. Besides the well-established Robinson-Foulds distances, which show similarity between tree topologies, a new measure, called Split Co-Occurrence is introduced, which shows how often two splits co-occur in the same tree. Space-saving output compression comes without runtime increase. TreeShredder’s performance compares favourably against similar features offered in software such as RAxML and BOOSTER, especially, but not exclusively, if the phylogenetic analysis is started from TreeShredder files. By means of diverse datasets of trees ranging in size from tens to thousands of taxa, I show that TreeShredder is a valuable and versatile addition to the phylogenetic analysis toolbox.

Keywords (deu)

SplitsPhylogenieTreeShredder fileKonsensus-BaumInternode CertaintyTransfer Bootstrap ExpectationSplit Co-Occurrenceparallele Programmierung

Keywords (eng)

splitsphylogenyTreeShredder fileconsensus treeInternode CertaintyTransfer Bootstrap ExpectationSplit Co-Occurrenceparallel compuation

Subject (deu)

Anwendungssoftware

Subject (deu)

Software engineering

Subject (deu)

Parallele Datenverarbeitung

Subject (deu)

Datenstrukturen