최소 진화

Minimum evolution

최소 진화는 유전체 모델링에 사용되는 거리 방법이다. 분지 길이의 총합이 가장 짧은 계통형태를 검색하는 측면을 최대한 어림짐작으로 공유한다.[1][2]

최소 진화(ME) 기준의 이론적 토대는 키드, 스가라멜라존타[3], 레제츠키, 네이 양자의 세미놀 작품에 놓여 있었다.[4] 이러한 프레임워크에서, taxa로부터의 분자 시퀀스는 그 차이(즉, 소위 "진화 거리")의 일련의 측정으로 대체되며, 근본적인 결과는 그러한 거리가 taxa로부터의 진정한 진화 거리에 대한 편중되지 않은 추정치(즉, 모든 분자 da가 획득될 경우 얻을 수 있는 거리)로 설명된다.ta from taxa) 그러면 taxa의 진정한 phylogeny는 그 거리와 호환되는 다른 가능한 phylogeny T보다 예상 길이가 짧을 것이다.

최대 구문 분석과 관계 및 차이

여기서 최대-파시모니 기준과 ME 기준 사이의 미묘한 차이를 주목할 필요가 있다: 최대-파시모니는 유괴적 휴리스틱스에 근거한 반면, 즉, 보다 복잡한 것에 관한 가장 단순한 세자의 진화 가설의 타당성, ME 기준은 Kidd와 Sgaramella-Zonta의 추측에 근거한다. 22년 후 Rzhetsky와 Nei에 의해 진실성이 입증되었다. 이러한 수학적 결과는 오캄의 면도기 원리로부터 자유로운 ME 기준을 설정하여 확고한 이론적, 정량적 근거를 제시한다.

통계적 일관성

ME 기준은 분기 길이가 OLS(일반 최소 제곱) 또는 선형 프로그래밍을 통해 추정될 때마다 통계적으로 일관되는 것으로 알려져 있다. [5] [6] [7] 그러나 Rzhetsky & Nei의 글에서 관찰된 바와 같이,[8] OLS 분기 길이 추정 모델에 따른 최소 길이를 갖는 계통 생성은 어떤 상황에서는 음의 가지 길이로 특징지어질 수 있는데, 유감스럽게도 생물학적 의미가 없다.

이러한 단점을 해결하기 위해 Pauplin은[9] OLS를 BME(균형화된 최소 진화)로 알려진 새로운 특정 분기 길이 추정 모델로 대체할 것을 제안했다. 리차드 데스페르와 올리비에 가스쿠엘은[10] BME 지점 길이 추정 모델은 세사에서 추정된 진화 거리가 삼각형 불평등을 만족시킬 때마다 최소 길이 계통의 비부정성과 더불어 최소 길이 계통의 일반적인 통계적 일관성을 보장한다는 것을 보여주었다.

Le Sy Vinh와 Arndt von Haeseler는[11] 거대하고 체계적인 시뮬레이션 실험을 통해 BME 지점 길이 추정 모델에 따른 ME 기준의 정확도가 거리 방법에서 월등히 높으며 최대우도 또는 베이시안 추론 등에 기초한 대체 기준의 정확도보다 뒤지지 않는다는 것을 보여주었다. 더욱이 Daniele Catanzaro, Martin Frohn, Raffaele Pessenti에서 알 수 있듯이,[12] BME 분기 길이 추정 모델에 따른 최소 길이 혈전학은 분석된 n에 근거한 골전체의 숲에 의해 인코딩된 동시 최소 엔트로피 프로세스 사이의 (Pareto 최적) 합의 트리로 해석될 수 있다. 이러한 특정한 정보 이론에 기초한 해석은 혈전생리학에서 모든 거리 방법에 의해 공유될 것으로 추측된다.

알고리즘 측면

최단 길이의 혈전증에 대한 검색은 일반적으로 에 기술된 접근법 및 인접 결합 알고리즘,[20] FASTME 또는 기타 메타휴리스틱스와 같은 경험적 접근법을 사용하여 수행된다.[21]

참고 항목

참조

  1. ^ Catanzaro, Daniele (2010). Estimating phylogenies from molecular data, in Mathematical approaches to polymer sequence analysis and related problems. Springer, New York.
  2. ^ Catanzaro D (2009). "The minimum evolution problem: Overview and classification". Networks. 53 (2): 112–125. doi:10.1002/net.20280.
  3. ^ Kidd KK, Sgaramella-Zonta LA (1971). "Phylogenetic analysis: Concepts and methods". American Journal of Human Genetics. 23 (3): 235–252. PMC 1706731. PMID 5089842.
  4. ^ Rzhetsky A, Nei M (1993). "Theoretical foundations of the minimum evolution method of phylogenetic inference". Molecular Biology and Evolution. 10: 21073–1095.
  5. ^ Rzhetsky A, Nei M (1993). "Theoretical foundations of the minimum evolution method of phylogenetic inference". Molecular Biology and Evolution. 10: 21073–1095.
  6. ^ Desper R, Gascuel O (2005). The minimum evolution distance-based approach to phylogenetic inference in Mathematics of Evolution and Phylogeny. Oxford University Press, New York.
  7. ^ Catanzaro D, Aringhieri R, Di Summa M, Pesenti R (2015). "A branch-price-and-cut algorithm for the minimum evolution problem". European Journal of Operational Research. 244 (3): 753–765. doi:10.1016/j.ejor.2015.02.019.
  8. ^ Rzhetsky A, Nei M (1993). "Theoretical foundations of the minimum evolution method of phylogenetic inference". Molecular Biology and Evolution. 10: 21073–1095.
  9. ^ Pauplin Y (2000). "Direct calculation of a tree length using a distance matrix". Journal of Molecular Evolution. 51 (1): 41–47. Bibcode:2000JMolE..51...41P. doi:10.1007/s002390010065. PMID 10903371. S2CID 8619412.
  10. ^ Desper R, Gascuel O (March 2004). "Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting". Molecular Biology and Evolution. 21 (3): 587–98. doi:10.1093/molbev/msh049. PMID 14694080.
  11. ^ Vihn LS, von Haeseler A (2005). "Shortest triplet clustering: Reconstructing large phylogenies using representative sets". BMC Bioinformatics. 6: 1–14. doi:10.1186/1471-2105-6-1. PMC 545949. PMID 15631638.
  12. ^ Catanzaro D, Frohn M, Pesenti R (2020). "An information theory perspective on the Balanced Minimum Evolution Problem". Operations Research Letters. 48 (3): 362–367. doi:10.1016/j.orl.2020.04.010.
  13. ^ Catanzaro D, Labbé M, Pesenti R, Salazar-González JJ (2009). "Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion". Networks. 53 (2): 126–140. doi:10.1002/net.20281.
  14. ^ Aringhieri R, Catanzaro D, Di Summa M (2011). "Optimal solutions for the balanced minimum evolution problem". Computers and Operations Research. 38 (12): 1845–1854. doi:10.1016/j.cor.2011.02.020.
  15. ^ Catanzaro D, Labbé M, Pesenti R, Salazar-González JJ (2012). "The balanced minimum evolution problem". INFORMS Journal on Computing. 24 (2): 276–294. doi:10.1287/ijoc.1110.0455.
  16. ^ Catanzaro D, Labbé M, Pesenti R (2013). "The balanced minimum evolution problem under uncertain data". Discrete Applied Mathematics. 161 (13–14): 1789–1804. doi:10.1016/j.dam.2013.03.012.
  17. ^ Catanzaro D, Aringhieri R, Di Summa M, Pesenti R (2015). "A branch-price-and-cut algorithm for the minimum evolution problem". European Journal of Operational Research. 244 (3): 753–765. doi:10.1016/j.ejor.2015.02.019.
  18. ^ Catanzaro D, Pesenti R (2019). "Enumerating Vertices of the Balanced Minimum Evolution Polytope". Computers and Operations Research. 109: 209–217. doi:10.1016/j.cor.2019.05.001.
  19. ^ Catanzaro D, Pesenti R, Wolsey L (2020). "On the Balanced Minimum Evolution Polytope". Discrete Optimization. 36: 100570. doi:10.1016/j.disopt.2020.100570.
  20. ^ Gascuel O, Steel M (2006). "Neighbor-joining Revealed". Molecular Biology and Evolution. 23 (11): 1997–2000. doi:10.1093/molbev/msl072. PMID 16877499.
  21. ^ Catanzaro D, Pesenti R, Milinkovitch MC (2007). "An ant colony optimization algorithm for phylogenetic estimation under the minimum evolution principle". BMC Evolutionary Biology. 7: 228. doi:10.1186/1471-2148-7-228. PMC 2211314. PMID 18005416.

추가 읽기

  • Catanzaro D, Pesenti R, Wolsey L (2020). "On the Balanced Minimum Evolution Polytope". Discrete Optimization. 36: 100570. doi:10.1016/j.disopt.2020.100570.