Neighbour-Joining-Algorithmen
aus Freepedia, der freien Wissensdatenbank
| Bild:Qsicon Achtung.png | Dieser Artikel oder Abschnitt ist noch recht unvollständig und weist folgende Lücken auf: {{{1|}}} |
Der Neighbour-Joining-Algorithmus ist ein mathematisches Verfahren um Datensätze zu vergleichen und hierarchich bifurcal(zweigabelig) anzuordnen.
In der Bioinformatik bezeichnet das Neighbour-Joining-Verfahren eine bottom-up Clustermethode, welche zur Erstellung von phylogenetischen Baumstrukturen verwendet wird. Hiermit soll anhand von varrierenden Merkmalen in der Datenmatrix die Wahrscheinlichkeit einer Abstammungs- oder Verwandschafts-Beziehung in einer Stammbaumartigen Darstellung berechnet werden. Normalerweise werden damit Bäume aus DNA- oder Proteinsequenzdaten oder klassisch morphologischen Datensätzen erstellt. Der Algorithmus benötigt Wissen über die Distanz zwischen zwei Paaren von Taxa (also beispielsweise Arten oder Sequenzen) in einem Baum.
Neighbour-joining basiert auf dem "Minimum Evolution Kriterium" für phylogenetische Bäume: Die Baum-Topologie mit der geringsten Verzweigungslänge wird in jedem Schritt des Algorithmus ausgewählt. Die Richtigkeit dieser Stammbäume beruht auf der Annahme, dass die Veränderung der betrachteten Merkmale keine unbekannten Zwischenschritte enthält. Es wird also vereinfacht angenommen, daß "die Evolution keine Umwege geht".
Der Neighbour-Joining-Algorithmus berechnet den Stammbaum schrittweise und findet deshalb nicht zwangsläufig die "wahre" Baum-Topologie mit der geringsten Verzweigungslänge. Dies beruht auf seinem Konstruktionsprinzip, als Greedy Algorithmus. Im Gegensatz zu anderen Algorhytmen berechnet dieser nicht alle möglichen Bäume und wählt zum Schluss die optimalsten aus, sondern verwirft schon während des Verfahrens einige Rechenwege. Obwohl der Algorithmus in diesem Sinne suboptimal ist, wurde er ausführlich getestet und findet normalerweise einen Baum, der dem Optimum relativ nahe kommt.
Der größte Vorteil dieses Verfahrens ist Effizienz. Man kann es auf gewaltige Datenmengen anwenden, selbst dort, wo andere Methoden der phylogenetischen Analyse wie minimum evolution, maximum parsimony und Maximum-Likelihood) nicht mehr durchführbar sind. Im Gegensatz zum UPGMA-Algorithmus (Unweighted Pair Group Method with Arithmetic mean) zur phylogenetischen Baumrekonstruktion nimmt Neighbour-Joining nicht an, dass die Entwicklung der Abstammungslinien mit derselben Rate (siehe auch Molekulare Uhr) stattfindet und erzeugt daher infolgedessen einen unbalancierten Baum.
