Minimum evolution
Fixed a NP-Hard link and moved a citation up
| ← Previous revision | Revision as of 18:41, 21 April 2026 | ||
| Line 92: | Line 92: | ||
==== Theoretically Unbiased ==== |
==== Theoretically Unbiased ==== |
||
Minimum Evolution (ME) is theoretically unbiased, meaning it doesn’t favor incorrect trees when evolutionary distances are used. Rzhetsky and Nei have shown through studies that the ME method doesn’t suffer from either of the 2 problems that affect other least-squares (OLS) methods: |
Minimum Evolution (ME) is theoretically unbiased, meaning it doesn’t favor incorrect trees when evolutionary distances are used. Rzhetsky and NeiM;, R. A. (n.d.). Statistical properties of the ordinary least-squares, generalized least-squares, and minimum-evolution methods of phylogenetic inference. Journal of molecular evolution. https://pubmed.ncbi.nlm.nih.gov/1404422/ have shown through studies that the ME method doesn’t suffer from either of the 2 problems that affect other least-squares (OLS) methods: |
||
# The OLS criterion can be biased and may select an incorrect tree more often than expected under random selection when evolutionary distances are large. |
# The OLS criterion can be biased and may select an incorrect tree more often than expected under random selection when evolutionary distances are large. |
||
# Generalized least-squares (GLS) methods may not be applicable when distances are too small. |
# Generalized least-squares (GLS) methods may not be applicable when distances are too small. |
||
The ME criterion avoids these biases and issues that may hurt other algorithms, making it unbiased and consistent for phylogenetic tree generation when distances are present. |
The ME criterion avoids these biases and issues that may hurt other algorithms, making it unbiased and consistent for phylogenetic tree generation when distances are present. |
||
| Line 104: | Line 103: | ||
=== Disadvantages === |
=== Disadvantages === |
||
==== Time Complexity ==== |
==== Time Complexity ==== |
||
Minimum Evolution (ME) has a time complexity of NP- |
Minimum Evolution (ME) has a time complexity of [[NP-hard]].Semple, C., and Steel, M. (2003). ''Phylogenetics''. Oxford University Press.. This means that as more taxa/sequences are added, the time to find the optimal ME tree grows exponentially, making very large datasets take a long time. Although ME is very time consuming heuristic ME is efficient. As the amount of sequences increases (n is increased) the amount of trees increases exponentially. |
||
Number of unrooted trees for n taxa = (2n−5)! / [2ⁿ⁻³ (n−3)!] |
Number of unrooted trees for n taxa = (2n−5)! / [2ⁿ⁻³ (n−3)!] |
||
