www.wikidata.de-de.nina.az

Neighbor Joining Algorithmus Der ist ein mathematisches Verfahren um Datensätze zu vergleichen und hierarchisch bifurcal

Neighbor-Joining-Algorithmus

Der Neighbor-Joining-Algorithmus ist ein mathematisches Verfahren, um Datensätze zu vergleichen und hierarchisch bifurcal (zweigabelig) anzuordnen. Dieses Verfahren wurde 1987 von Saitou und Nei vorgestellt und 1988 von Studier und Keppler weiterentwickelt und vereinfacht.

Anwendung Bearbeiten

In der Bioinformatik bezeichnet das Neighbor-Joining-Verfahren eine phänetische bottom-up Clustermethode, welche zur Erstellung von phylogenetischen Baumstrukturen verwendet wird. Hiermit soll anhand von variierenden Merkmalen in der Datenmatrix die Wahrscheinlichkeit einer Abstammungs- oder Verwandtschaftsbeziehung 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.

Algorithmus Bearbeiten

Drei Schritte bei der Erstellung eines phylogenetischen Baumes für fünf Taxa mit dem Neighbor-Joining-Algorithmus

Neighbor-joining basiert meist auf dem „Minimum Evolution“-Kriterium für phylogenetische Bäume: Ausgehend von einem zunächst sternförmigen „Baum“, in dem alle Taxa mit einem „Zentrum“ verbunden sind, werden paarweise die DNA- oder Proteinsequenzen mit der geringsten genetischen Distanz ausgewählt und zu einem Ast des Baumes vereinigt. Die genetischen Distanzen der Sequenzen werden neu berechnet und wieder die nächstverwandten zu einem Ast mit zwei Taxa zusammengefügt. Dies erfolgt solange, bis alle Taxa in dem Baum eingefügt wurden und die Sternstruktur des Baumes völlig aufgelöst wurde. Im Unterschied zum UPGMA berücksichtigt Neighbor-Joining, dass die Evolutionsgeschwindigkeit nicht konstant ist: Wenn ein Taxon von allen anderen Taxa weit entfernt ist, so ist dies nicht auf einen entfernten Verwandtschaftsgrad, sondern auf beschleunigte Evolution zurückzuführen.

Der Algorithmus ist iterativ und ersetzt in jedem Schritt ein Paar der Operational Taxonomic Units (OTU) durch eine neue Sequenz. Er iteriert auf den jeweils verbleibenden Sequenzen weiter, bis es für drei verbleibende OTUs nur noch eine mögliche Topologie gibt. Danach wird die Baumstruktur erstellt.

Beispiel Bearbeiten

Folgend ist eine typische Tabelle von Distanzen zwischen Taxa angegeben, wobei die Werte rein hypothetisch, aber realistisch sind: Studier und Keppler führten einen alternativen Parameter im Algorithmus ein, der als Mij bezeichnet wird. Saitou und Nei verwendeten ursprünglich zur Bestimmung der Nachbarn die „minimal sum of branches“ (Sij) also die minimale Anzahl an Verzweigungen. Das Beispiel basiert auf dem Algorithmus von Studier und Keppler, welche gegen den ursprünglichen Parameter eine Komplexitätsklasse bietet.

Mensch Maus Rose Tulpe
Mensch 0 3 14 12
Maus 3 0 13 11
Rose 14 13 0 4
Tulpe 12 11 4 0

Da die Tabelle dreiecks-symmetrisch ist, muss die untere Hälfte nicht unbedingt gespeichert werden. Die Werte in dieser Tabelle werden als benannt.

Schritt 1: Es müssen die Durchschnittlichen Distanzen von jedem Taxon zu jedem anderen berechnet werden. Dies geschieht mit folgender Formel für die Netto-Divergenz ri:

Wobei N die Anzahl der Taxa ist.

Mensch
Maus
Rose
Tulpe

Interpretation: Die Rose besitzt in unserem Beispiel die größte Netto-Divergenz, hat also im Vergleich mit den anderen Taxa eine größere Evolutionsgeschwindigkeit durchlebt.

Schritt 2: Wir berechnen eine Zwischenmatrix M.

Wie z. B. zwischen Mensch und Maus:

Mensch Maus Rose Tulpe
Mensch −25 −16 −16
Maus −25 −16 −16
Rose −16 −16 −25
Tulpe −16 −16 −25

Schritt 3: In dieser neu berechneten Distanzmatrix M wird nun der kleinste Wert, also die kleinste Distanz zwischen zwei Taxa, gesucht, und die gefundenen zwei Taxa werden zu einem neuen Teilbaum u = (i,j) zusammengefügt. In diesem Beispiel ergeben sich also die zwei Möglichkeiten Mensch und Maus, oder Rose und Tulpe zu einem Teilbaum zusammenzufügen. Wir entscheiden uns zunächst für Mensch und Maus.

Die Kantenlänge des Knotens zu der Verzweigung berechnet sich wie folgt:

Also Mensch zu MeMa ist gleich

Schritt 4: In der ursprünglichen Distanzmatrix wird der neue Eintrag u = MeMa angefügt:

Mensch Maus Rose Tulpe MeMa
Mensch 0 3 14 12 ?
Maus 3 0 13 11 ?
Rose 14 13 0 4 ?
Tulpe 12 11 4 0 ?
MeMa ? ? ? ? 0

Um die Distanzen des neuen Eintrages u = (i,j) = (1,2) = (Mensch, Maus) = MeMa zu den restlichen Taxa zu berechnen, wird folgende Formel verwendet:

Wobei die Einträge i und j zu einem neuen Eintrag u zusammengefügt wird, und die Distanz zum Eintrag k ausgerechnet wird. Die Distanz zwischen Rose und dem neuen Teilbaum ist also:

Die „alten“, zusammengefügten Einträge, werden aus den Distanzmatrixen gelöscht.

Rose Tulpe MeMa
Rose 0 4 12
Tulpe 4 0 10
MeMa 12 10 0

Danach werden wieder und berechnet, neu zusammengefügt und wieder von vorne angefangen. Dies wird solange wiederholt, bis nur noch zwei Taxa übrig bleiben, die dann schlussendlich verbunden werden.

Das Ergebnis unseres Beispiels lässt sich wie folgt darstellen:

additiver Baum Ausgabe des Phylip Programms 
Mensch Rose \ / \ 2 3 / \ 9 / ----------------- / \ / 1 1 \ / \ Maus Tulpe 
 +----Maus  !  ! +-------------Rose 1-----------------------------------------2  ! +----Tulpe  ! +--------Mensch

Einordnung Bearbeiten

Neighbor-Joining gehört zu den expliziten Methoden. Dies bedeutet, dass bei der Berechnung der genetischen Distanzen unterschiedliche Evolutionsmodelle, also unterschiedliche Wahrscheinlichkeiten für Punktmutationen angenommen werden können. 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, dass „die Evolution keine Umwege geht“ (“minimum evolution”).

Der Neighbor-Joining-Algorithmus berechnet den Stammbaum schrittweise und findet deshalb nicht zwangsläufig die optimale Baum-Topologie mit der geringsten Verzweigungslänge. Dies beruht auf seinem Konstruktionsprinzip, als Greedy-Algorithmus. Im Gegensatz zu anderen Algorithmen berechnet dieser nicht alle möglichen Bäume und wählt zum Schluss die optimalen aus, sondern verwirft schon während des Verfahrens einige Rechenwege. Obwohl der Algorithmus suboptimal ist, wurde er ausführlich getestet und findet normalerweise einen Baum, der dem Optimum relativ nahekommt.

Vorteile Bearbeiten

Der größte Vorteil dieses Verfahrens ist seine Geschwindigkeit. Man kann es auf gewaltige Datenmengen anwenden, selbst dort, wo andere Methoden der phylogenetischen Analyse wie 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 Neighbor-Joining nicht an, dass die Entwicklung der Abstammungslinien mit derselben Rate (siehe auch Molekulare Uhr) stattfindet und erzeugt daher infolgedessen einen unbalancierten Baum.

Literatur Bearbeiten

  • N. Saitou, M. Nei: The neighbor-joining method. A new method for reconstructing phylogenetic trees. In: Molecular Biology and Evolution. Band 4, Nr. 4, 1. Juli 1987, S. 406–425 (oxfordjournals.org).
  • J. A. Studier, K. J. Keppler: A note on the neighbor-joining algorithm of Saitou and Nei. In: Molecular Biology and Evolution. Band 5, Nr. 6, 1. November 1988, S. 729–731, PMID 3221794 (mbe.oxfordjournals.org [PDF]).
  • Volker Knoop, Kai Müller: Gene und Stammbäume. Ein Handbuch zur molekularen Phylogenetik. 1. Auflage. Elsevier, Spektrum Akademischer Verlag, München / Heidelberg 2006, ISBN 3-8274-1642-6.
  • Olivier Gascuel, Mike Steel: Neighbor-Joining Revealed. In: Molecular Biology and Evolution. Band 23, Nr. 11, 1. November 2006, S. 1997–2000, doi:10.1093/molbev/msl072, PMID 16877499.

Quellen Bearbeiten

  1. N. Saitou, M. Nei: The neighbor-joining method: a new method for reconstructing phylogenetic trees. In: Molecular Biology and Evolution. Band 4, Nr. 4, Juli 1987, ISSN 0737-4038, S. 406–425, doi:10.1093/oxfordjournals.molbev.a040454, PMID 3447015.
  2. ↑ 3.1 neighbor-joining-Algorithmus (PDF, S. 7).
  3. The Neighbor-Joining Method auf icp.ucl.ac.be
  4. (Memento des Originals vom 16. September 2016 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.stat.berkeley.edu auf stat.berkeley.edu
  5. Kord Eickmeyer, Peter Huggins, Lior Pachter, Ruriko Yoshida: On the optimality of the neighbor-joining algorithm. In: Algorithms for Molecular Biology (AMB). Band 3, 30. April 2008, ISSN 1748-7188, S. 5, doi:10.1186/1748-7188-3-5.

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Neighbor Joining Algorithmus ist ein mathematisches Verfahren um Datensatze zu vergleichen und hierarchisch bifurcal zweigabelig anzuordnen Dieses Verfahren wurde 1987 von Saitou und Nei vorgestellt 1 und 1988 von Studier und Keppler weiterentwickelt und vereinfacht Inhaltsverzeichnis 1 Anwendung 2 Algorithmus 3 Beispiel 4 Einordnung 5 Vorteile 6 Literatur 7 Quellen 8 WeblinksAnwendung BearbeitenIn der Bioinformatik bezeichnet das Neighbor Joining Verfahren eine phanetische bottom up Clustermethode welche zur Erstellung von phylogenetischen Baumstrukturen verwendet wird Hiermit soll anhand von variierenden Merkmalen in der Datenmatrix die Wahrscheinlichkeit einer Abstammungs oder Verwandtschaftsbeziehung in einer stammbaumartigen Darstellung berechnet werden Normalerweise werden damit Baume aus DNA oder Proteinsequenzdaten oder klassisch morphologischen Datensatzen erstellt Der Algorithmus benotigt Wissen uber die Distanz zwischen zwei Paaren von Taxa also beispielsweise Arten oder Sequenzen in einem Baum Algorithmus Bearbeiten nbsp Drei Schritte bei der Erstellung eines phylogenetischen Baumes fur funf Taxa mit dem Neighbor Joining AlgorithmusNeighbor joining basiert meist auf dem Minimum Evolution Kriterium fur phylogenetische Baume Ausgehend von einem zunachst sternformigen Baum in dem alle Taxa mit einem Zentrum verbunden sind werden paarweise die DNA oder Proteinsequenzen mit der geringsten genetischen Distanz ausgewahlt und zu einem Ast des Baumes vereinigt Die genetischen Distanzen der Sequenzen werden neu berechnet und wieder die nachstverwandten zu einem Ast mit zwei Taxa zusammengefugt Dies erfolgt solange bis alle Taxa in dem Baum eingefugt wurden und die Sternstruktur des Baumes vollig aufgelost wurde Im Unterschied zum UPGMA berucksichtigt Neighbor Joining dass die Evolutionsgeschwindigkeit nicht konstant ist Wenn ein Taxon von allen anderen Taxa weit entfernt ist so ist dies nicht auf einen entfernten Verwandtschaftsgrad sondern auf beschleunigte Evolution zuruckzufuhren Der Algorithmus ist iterativ und ersetzt in jedem Schritt ein Paar der Operational Taxonomic Units OTU durch eine neue Sequenz Er iteriert auf den jeweils verbleibenden Sequenzen weiter bis es fur drei verbleibende OTUs nur noch eine mogliche Topologie gibt Danach wird die Baumstruktur erstellt 2 Beispiel BearbeitenFolgend ist eine typische Tabelle von Distanzen zwischen Taxa angegeben wobei die Werte rein hypothetisch aber realistisch sind 3 Studier und Keppler fuhrten einen alternativen Parameter im Algorithmus ein der als Mij bezeichnet wird Saitou und Nei verwendeten ursprunglich zur Bestimmung der Nachbarn die minimal sum of branches Sij also die minimale Anzahl an Verzweigungen Das Beispiel basiert auf dem Algorithmus von Studier und Keppler welche gegen den ursprunglichen Parameter eine Komplexitatsklasse O n 3 displaystyle O n 3 nbsp bietet 4 Mensch Maus Rose TulpeMensch 0 3 14 12Maus 3 0 13 11Rose 14 13 0 4Tulpe 12 11 4 0Da die Tabelle dreiecks symmetrisch ist muss die untere Halfte nicht unbedingt gespeichert werden Die Werte in dieser Tabelle werden als d i j displaystyle d i j nbsp benannt Schritt 1 Es mussen die Durchschnittlichen Distanzen von jedem Taxon zu jedem anderen berechnet werden Dies geschieht mit folgender Formel fur die Netto Divergenz ri 2 r i 1 N 2 k 1 N d i k displaystyle r i frac 1 N 2 sum k 1 N d i k nbsp Wobei N die Anzahl der Taxa ist Mensch r 1 0 3 14 12 4 2 14 5 displaystyle r 1 frac 0 3 14 12 4 2 14 5 nbsp Maus r 2 3 0 13 11 4 2 13 5 displaystyle r 2 frac 3 0 13 11 4 2 13 5 nbsp Rose r 3 14 13 0 4 4 2 15 5 displaystyle r 3 frac 14 13 0 4 4 2 15 5 nbsp Tulpe r 4 12 11 4 0 4 2 13 5 displaystyle r 4 frac 12 11 4 0 4 2 13 5 nbsp Interpretation Die Rose besitzt in unserem Beispiel die grosste Netto Divergenz hat also im Vergleich mit den anderen Taxa eine grossere Evolutionsgeschwindigkeit durchlebt Schritt 2 Wir berechnen eine Zwischenmatrix M M i j d i j r i r j displaystyle M i j d i j r i r j nbsp Wie z B zwischen Mensch und Maus M 1 2 d 1 2 r 1 r 2 3 14 5 13 5 25 displaystyle M 1 2 d 1 2 r 1 r 2 3 14 5 13 5 25 nbsp M displaystyle M nbsp Mensch Maus Rose TulpeMensch 25 16 16Maus 25 16 16Rose 16 16 25Tulpe 16 16 25Schritt 3 In dieser neu berechneten Distanzmatrix M wird nun der kleinste Wert also die kleinste Distanz zwischen zwei Taxa gesucht und die gefundenen zwei Taxa werden zu einem neuen Teilbaum u i j zusammengefugt In diesem Beispiel ergeben sich also die zwei Moglichkeiten Mensch und Maus oder Rose und Tulpe zu einem Teilbaum zusammenzufugen Wir entscheiden uns zunachst fur Mensch und Maus Die Kantenlange des Knotens zu der Verzweigung berechnet sich wie folgt v i u d i j r i r j 2 displaystyle v i u frac d i j r i r j 2 nbsp v j u d i j v i u displaystyle v j u d i j v i u nbsp Also Mensch zu MeMa ist gleich 3 14 5 13 5 2 2 displaystyle frac 3 14 5 13 5 2 2 nbsp Schritt 4 In der ursprunglichen Distanzmatrix wird der neue Eintrag u MeMa angefugt Mensch Maus Rose Tulpe MeMaMensch 0 3 14 12 Maus 3 0 13 11 Rose 14 13 0 4 Tulpe 12 11 4 0 MeMa 0Um die Distanzen des neuen Eintrages u i j 1 2 Mensch Maus MeMa zu den restlichen Taxa zu berechnen wird folgende Formel verwendet d u k d i k d j k d i j 2 displaystyle d u k frac d i k d j k d i j 2 nbsp Wobei die Eintrage i und j zu einem neuen Eintrag u zusammengefugt wird und die Distanz zum Eintrag k ausgerechnet wird Die Distanz zwischen Rose und dem neuen Teilbaum ist also d 5 3 d 1 3 d 2 3 d 1 2 2 14 13 3 2 12 displaystyle d 5 3 frac d 1 3 d 2 3 d 1 2 2 frac 14 13 3 2 12 nbsp Die alten zusammengefugten Eintrage werden aus den Distanzmatrixen geloscht Rose Tulpe MeMaRose 0 4 12Tulpe 4 0 10MeMa 12 10 0Danach werden wieder r i displaystyle r i nbsp und M i j displaystyle M i j nbsp berechnet neu zusammengefugt und wieder von vorne angefangen Dies wird solange wiederholt bis nur noch zwei Taxa ubrig bleiben die dann schlussendlich verbunden werden Das Ergebnis unseres Beispiels lasst sich wie folgt darstellen additiver Baum Ausgabe des Phylip ProgrammsMensch Rose 2 3 9 1 1 Maus Tulpe Maus Rose 1 2 Tulpe MenschEinordnung BearbeitenNeighbor Joining gehort zu den expliziten Methoden Dies bedeutet dass bei der Berechnung der genetischen Distanzen unterschiedliche Evolutionsmodelle also unterschiedliche Wahrscheinlichkeiten fur Punktmutationen angenommen werden konnen Die Richtigkeit dieser Stammbaume beruht auf der Annahme dass die Veranderung der betrachteten Merkmale keine unbekannten Zwischenschritte enthalt Es wird also vereinfacht angenommen dass die Evolution keine Umwege geht minimum evolution Der Neighbor Joining Algorithmus berechnet den Stammbaum schrittweise und findet deshalb nicht zwangslaufig die optimale Baum Topologie mit der geringsten Verzweigungslange Dies beruht auf seinem Konstruktionsprinzip als Greedy Algorithmus 5 Im Gegensatz zu anderen Algorithmen berechnet dieser nicht alle moglichen Baume und wahlt zum Schluss die optimalen aus sondern verwirft schon wahrend des Verfahrens einige Rechenwege Obwohl der Algorithmus suboptimal ist wurde er ausfuhrlich getestet und findet normalerweise einen Baum der dem Optimum relativ nahekommt Vorteile BearbeitenDer grosste Vorteil dieses Verfahrens ist seine Geschwindigkeit Man kann es auf gewaltige Datenmengen anwenden selbst dort wo andere Methoden der phylogenetischen Analyse wie maximum parsimony und Maximum Likelihood nicht mehr durchfuhrbar sind Im Gegensatz zum UPGMA Algorithmus Unweighted Pair Group Method with Arithmetic mean zur phylogenetischen Baumrekonstruktion nimmt Neighbor Joining nicht an dass die Entwicklung der Abstammungslinien mit derselben Rate siehe auch Molekulare Uhr stattfindet und erzeugt daher infolgedessen einen unbalancierten Baum Literatur BearbeitenN Saitou M Nei The neighbor joining method A new method for reconstructing phylogenetic trees In Molecular Biology and Evolution Band 4 Nr 4 1 Juli 1987 S 406 425 oxfordjournals org J A Studier K J Keppler A note on the neighbor joining algorithm of Saitou and Nei In Molecular Biology and Evolution Band 5 Nr 6 1 November 1988 S 729 731 PMID 3221794 mbe oxfordjournals org PDF Volker Knoop Kai Muller Gene und Stammbaume Ein Handbuch zur molekularen Phylogenetik 1 Auflage Elsevier Spektrum Akademischer Verlag Munchen Heidelberg 2006 ISBN 3 8274 1642 6 Olivier Gascuel Mike Steel Neighbor Joining Revealed In Molecular Biology and Evolution Band 23 Nr 11 1 November 2006 S 1997 2000 doi 10 1093 molbev msl072 PMID 16877499 Quellen Bearbeiten N Saitou M Nei The neighbor joining method a new method for reconstructing phylogenetic trees In Molecular Biology and Evolution Band 4 Nr 4 Juli 1987 ISSN 0737 4038 S 406 425 doi 10 1093 oxfordjournals molbev a040454 PMID 3447015 a b 3 1 neighbor joining Algorithmus PDF S 7 The Neighbor Joining Method auf icp ucl ac be Neighbour Joining Method Saitou and Nei 1987 Summary Memento des Originals vom 16 September 2016 im Internet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot www stat berkeley edu auf stat berkeley edu Kord Eickmeyer Peter Huggins Lior Pachter Ruriko Yoshida On the optimality of the neighbor joining algorithm In Algorithms for Molecular Biology AMB Band 3 30 April 2008 ISSN 1748 7188 S 5 doi 10 1186 1748 7188 3 5 Weblinks BearbeitenQuicktree Eine Implementierung von Neighbour Joining Memento vom 11 Marz 2010 im Internet Archive Das PHYLIP Paket Abgerufen von https de wikipedia org w index php title Neighbor Joining Algorithmus amp oldid 239216388