Berechnung von galled Netzwerken aus echten Daten

MOTIVATION: Die Entwicklung von Methoden zur Berechnung phylogenetischer Netzwerke aus biologischen Daten ist ein wichtiges Problem, das durch die molekulare Evolution aufgeworfen wird, und es wird derzeit viel Arbeit in diesem Bereich geleistet. Obwohl vielversprechende Ansätze existieren, gibt es keine Werkzeuge, die Biologen leicht und routinemäßig verwenden könnten, um verwurzelte phylogenetische Netzwerke aus echten Datensätzen mit Dutzenden oder Hunderten von Taxa zu berechnen. Biologen interessieren sich für Kladen, d.h. Gruppen monophyletischer Taxa, und diese werden in der Regel durch Cluster in einem verwurzelten phylogenetischen Baum dargestellt. Das Problem, ein optimales verwurzeltes phylogenetisches Netzwerk aus einer Menge von Clustern zu berechnen, ist im Allgemeinen schwierig. Tatsächlich ist bereits das Problem, nur zu bestimmen, ob ein gegebenes Netzwerk einen bestimmten Cluster enthält, schwierig. Daher haben sich einige Forscher auf topologisch eingeschränkte Klassen von Netzwerken konzentriert, wie galled Bäume und level-k Netzwerke, die besser handhabbar sind, jedoch den praktischen Nachteil haben, dass eine gegebene Menge von Clustern in der Regel keine solche Darstellung besitzt. ERGEBNISSE: In diesem Artikel argumentieren wir, dass galled Netzwerke (eine Verallgemeinerung galled Bäume) einen guten Kompromiss zwischen Allgemeinheit und Handhabarkeit bieten. Jede Menge von Clustern kann durch ein galled Netzwerk dargestellt werden, und die Frage, ob ein Cluster in einem solchen Netzwerk enthalten ist, ist einfach zu lösen. Obwohl die Berechnung eines optimalen galled Netzwerks das wiederholte Lösen von Instanzen zweier verschiedener NP-vollständiger Probleme umfasst, löst unser Algorithmus dieses Problem in der Praxis exakt auf großen Datensätzen mit Hunderten von Taxa und vielen Retikulationen in Sekunden, wie ein Datensatz mit 279 Prokaryoten zeigt. VERFÜGBARKEIT: Wir bieten eine schnelle, robuste und benutzerfreundliche Implementierung dieser Arbeit in Version 2.0 unserer Baumverarbeitungssoftware Dendroscope an, die kostenlos unter http://www.dendroscope.org erhältlich ist.