Der Satz von Atteson wird in der Bioinformatik bei der Generierung phylogenetischer Bäume, die mit Hilfe des Neighbor-Joining-Algorithmus erzeugt werden verwendet, um zu bewerten, ob ein aus der Distanzmatrix erzeugter phylogenetischer Baum korrekt ist.[1]
Einleitung
BearbeitenFür die Konstruktion phylogenetischer Bäume gibt es eine Vielzahl von entwickelten Algorithmen. Die derzeit gängisten Baumkonstruktionsmethoden sind die Maximum-Likelihood-, die Maximum-Parsimony-, die Bayessche Analyse und die Neighbor-Joining -Methoden. Die Maximum-Likelihood- und Maximum-Parsimony-Algorithmen nutzen einen kladistischen Ansatz zur Konstruktion, während die Neighbor-Joining Methode ein phänetisches Klassifikationsverfahre verwendet. Phänetische Methoden sind distanzbasierende Methoden, deren Ziel es ist, die Blätter in dem konstruierten Baum so anzuordnen, dass deren Positionen mit den paarweisen Distanzen im richtigen Verhältnis stehen. Im Gegensatz dazu bewerten die Parsimony Methoden die Charakteristiken, also eine beobachtbare Eigenschaft, anstatt der Distanzen.[1]
Der Neighbor-Joining-Algorithmus findet nicht immer den optimalen Baum, da er schon während der iterativen Berechnung, Rechenwege verwirft und nicht wie andere Algorithmen alle Möglichkeiten berechnet und daraus das beste Resultat auswählt. Dennoch findet dieser Algorithmus breite Verwendung, da aufgrund seiner vergleichsweise hohen Geschwindigkeit auch große Datenmengen verarbeitet werden können, bei denen die andern Ansätze aufgrund der Zeitkomplexität scheitern würden. Des weiteren erzeugt der Neighbor-Joing-Algorithmus einen unbalanzierten Baum, da er nicht davon ausgeht, dass die Entwicklung der Abstammungslinien mit derselben Rate stattfindet.
Anwendung
BearbeitenDiese Mutationen werden in der Bioinformatik in sogenannten Distanzmatrizen abgebildet. Es besteht nun die Aufgabe, aus solch einer Matrix einen phylogenetischen Baum abzuleiten. Dafür existieren viele Ansätze. Einer davon ist die Verwendung des Neighbour-Joing-Algorithmus. Ist die verwendete Matrix additiv, so ist auch der konstruierte Baum additiv und damit korrekt. Wenn die verwendete Matrix nicht additiv ist, kann mit Hilfe des Satz von Atteson bewertet werden, ob der resultierende Baum korrekt ist oder nicht.[1]
Dieser besagt, dass die Topologie des durch die additive Matrix D generierte Baum T die gleiche ist wir für den Baum T' der durch die fast additive Matrix D' generiert wurde. Für fast additivität gilt:
![{\displaystyle \mid D-D'\mid ={\underset {i,j}{\max(}}\mid D[i,j]-D'[i,j])\leq {\underset {v_{k}}{\min }}({v_{k} \over 2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd7d3da729fbbe0c9b322620433f707a9ec28317)
Dabei ist D' die fast additive Matrix, die Kantenlänge.[2]
Einzelnachweis
Bearbeiten- ↑ a b c Rainer Merkl: Bioinformatik: Grundlagen, Algorithmen, Anwendungen. 3. Auflage. John Wiley, ISBN 3-527-68588-X, S. 262.
- ↑ Vincent Moulton, Mona Singh (Hrsg.): Algorithms in Bioinformatics: 10th International Workshop. Springer Science & Business Media, Liverpool, UK 2010, ISBN 3-642-15293-7, S. 251.