Difference between revisions of "Neighbour joining"
(Started article) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | In [[bioinformatics]], '''neighbour-joining''' is a bottom-up clustering method used for the creation of [[phylogeny|phylogenetic]] [[tree data structure|tree]]s. Usually used for trees based on [[DNA]] or [[protein]] [[primary structure|sequence]] data, the algorithm requires knowledge of the distance between each pair of taxa (e.g. species or sequences) in the tree. | + | In [[:Category:Bioinformatics|bioinformatics]], '''neighbour-joining''' is a bottom-up clustering method used for the creation of [[phylogeny|phylogenetic]] [[tree data structure|tree]]s. Usually used for trees based on [[DNA]] or [[protein]] [[primary structure|sequence]] data, the algorithm requires knowledge of the distance between each pair of taxa (e.g. species or sequences) in the tree. |
Neighbour-joining is based on the minimum evolution criterion for [[phylogenetic tree]]s, i.e. the topology that gives the least total branch length is preferred at each step of the algorithm. However, neighbour-joining may not find the true tree topology with least total branch length because it is a greedy algorithm that constructs the tree in a step-wise fashion. Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree. | Neighbour-joining is based on the minimum evolution criterion for [[phylogenetic tree]]s, i.e. the topology that gives the least total branch length is preferred at each step of the algorithm. However, neighbour-joining may not find the true tree topology with least total branch length because it is a greedy algorithm that constructs the tree in a step-wise fashion. Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree. | ||
| Line 5: | Line 5: | ||
The main virtue of neighbour-joining is its efficiency. It can be used on very large data sets for which other means of phylogenetic analysis (e.g. [[minimum evolution]], [[maximum parsimony]], [[maximum likelihood]]) are computationally prohibitive. Unlike the [[UPGMA]] algorithm for phylogenetic tree reconstruction, neighbour-joining does not assume that all lineages evolve at the same rate ([[molecular clock hypothesis]]) and produces an unrooted tree. | The main virtue of neighbour-joining is its efficiency. It can be used on very large data sets for which other means of phylogenetic analysis (e.g. [[minimum evolution]], [[maximum parsimony]], [[maximum likelihood]]) are computationally prohibitive. Unlike the [[UPGMA]] algorithm for phylogenetic tree reconstruction, neighbour-joining does not assume that all lineages evolve at the same rate ([[molecular clock hypothesis]]) and produces an unrooted tree. | ||
| − | == | + | ==References== |
| − | * | + | *Saitou N, Nei M (1987). "The neighbor-joining method: a new method for reconstructing phylogenetic trees". ''Mol Biol Evol, 4(4):406-425''. |
| − | [ | + | ==External links== |
| + | *[http://en.wikipedia.org/wiki/Neighbour_joining Wikipedia article on '''Neighbour joining'''] | ||
| + | |||
| + | {{Phylogenetics}} | ||
[[Category:Phylogenetics]] | [[Category:Phylogenetics]] | ||
Latest revision as of 10:35, 19 April 2007
In bioinformatics, neighbour-joining is a bottom-up clustering method used for the creation of phylogenetic trees. Usually used for trees based on DNA or protein sequence data, the algorithm requires knowledge of the distance between each pair of taxa (e.g. species or sequences) in the tree.
Neighbour-joining is based on the minimum evolution criterion for phylogenetic trees, i.e. the topology that gives the least total branch length is preferred at each step of the algorithm. However, neighbour-joining may not find the true tree topology with least total branch length because it is a greedy algorithm that constructs the tree in a step-wise fashion. Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree.
The main virtue of neighbour-joining is its efficiency. It can be used on very large data sets for which other means of phylogenetic analysis (e.g. minimum evolution, maximum parsimony, maximum likelihood) are computationally prohibitive. Unlike the UPGMA algorithm for phylogenetic tree reconstruction, neighbour-joining does not assume that all lineages evolve at the same rate (molecular clock hypothesis) and produces an unrooted tree.
References
- Saitou N, Nei M (1987). "The neighbor-joining method: a new method for reconstructing phylogenetic trees". Mol Biol Evol, 4(4):406-425.
External links
| Topics in phylogenetics |
|---|
| Relevant fields: phylogenetics | computational phylogenetics | molecular phylogeny | cladistics |
| Basic concepts: synapomorphy | phylogenetic tree | phylogenetic network | long branch attraction |
| Phylogeny inference methods: maximum parsimony | maximum likelihood | neighbour joining | UPGMA |
