ارائه الگوریتمی نوین برای حل مساله ساخت درخت فیلوژنتیک ریشه‌دار بر اساس سه‌تایی‌های ریشه‌دار ورودی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، دانشگاه میبد، میبد، ایران

2 گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه میبد، میبد، ایران

چکیده

فیلوژنتیک شاخه‌ای از دانش بیوانفورماتیک است که تاریخچه روابط تکاملی بین گونه‌های موجودات زنده را بررسی می‌کند و مدل‌هایی را ارائه می‌دهد و گونه‌ها را دسته‌بندی نیز می‌کند. فیلوژنتیک از شبکه‌ها برای بیان روابط تکاملی در یک مدل جامع استفاده می‌کند. ساده‌ترین مدل شبکه ای، یک درخت است که درخت فیلوژنتیک نامیده می‌شود. درختهای فیلوژنتیک به دو زیرمجموعه ریشه‌دار و بدون ریشه تقسیم می‌شوند. در این پژوهش علاقه ما، درخت‌ها‌‌ی فیلوژنتیک ریشه‌دار است. ورودی‌های مختلفی برای ساخت درخت‌های فیلوژنتیک ریشه‌دار موجود است. سه‌تایی‌های ریشه‌دار یکی از انواع مهم ورودی‌ها در تحلیل روابط بین گونه‌ها و ساخت درخت فیلوژنتیک ریشه‌دارند که در این پژوهش از آن استفاده می‌کنیم. سه‌تایی ریشه‌دار یک درخت دودویی ریشه‌دار با سه برگ است. سه‌تایی ریشه‌دار ساده‌ترین مدل درختی ریشه‌دار است که حاوی اطلاعات است. مساله ساخت درخت فیلوژنتیک ریشه‌داری که دربرگیرنده بیش‌ترین سه‌تایی ورودی باشد، یک مساله بهینه سازی است و به مساله MRTC مشهور است. چالش مهم در فیلوژنتیک، -NP سخت بودن مساله MRTC است. از این‌رو در این مقاله، یک الگوریتم نوین برای مساله MRTC با هدف افزایش میزان سازگاری سه‌تایی‌های ریشه‌دار ورودی با درخت نهایی، معرفی می‌شود. با هدف بیان کارایی الگوریتم نوین، روش معرفی‌شده را با روش TRH و بر روی داده‌های واقعی مقایسه می‌کنیم. الگوریتم TRH یکی از بهترین روش‌ها برای حل مساله MRTC و بر روی سه‌تایی‌های ریشه‌داری است که از روی داده‌های واقعی به‌دست آمده‌اند. نتایج آزمایش‌ها نشان می‌دهد که با در نظر گرفتن زمان اجرا و سازگاری سه‌تایی‌ها با درخت نهایی، الگوریتم ما نتایج TRH را بهبود می‌بخشد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

A novel Algorithm for constructing rooted phylogenetic trees based on rooted triplets

نویسندگان [English]

  • Hadi Poormohammadi 1
  • Mohsen Sardari Zarchi 1
  • Mohamad Ali Sehati 1
  • Mohamad Mirabi 2
  • Seyaed Hasan Mortazavi Zarch 1
1 Department of Computer Engineering, Meybod University, Meybod, Iran
2 Department of Industrial Engineering, Meybod University, Meybod, Iran
چکیده [English]

Phylogenetics is a field in bioinformatics that categorizes and structures the evolutionary hisotiry of currently living species. Phylogenetics uses network tools to represent evolutionary histories in a comprehensive model. The simpleset possible network model is a tree model that is called a phylogenetic tree. Phylogenetic trees are divided into two categories, which are rooted and un-rooted. In this research, rooted phylogenetic trees are of interest. There are different types of input for constructing rooted phylogenetic trees. Rooted triplets are one of the important inputs for constructing rooted phylogenetic trees, which are used in this study. A rooted triplet is a rooted binary tree with three leaves. The rooted triplet is the most simplest model, which contains valuable information. The problem of building a rooted phylogenetic tree that includes the maximum number of a set of rooted triplets is an optimizataion problem, known as MRTC problem. The important challenge in phylogenetics is that MRTC is NP-hard. Therefore, the focus of this research is to introduce a novel algorithm for MRTC problem. The aim of the new algorithm is to improve the consistency of input rooted triplets with the final rooted phylogenetic tree. In order to indicate the performance of the new algorithm, it is compared with on of the best methods on biological data which is called TRH. The Experimental results on triplets that are obtained from biological data show that our new algorithm outperforms TRH base on time complexity and consistency.

کلیدواژه‌ها [English]

  • Bioinformatics
  • Biological sequence
  • MRTC problem
  • Rooted phylogenetic tree
  • Rooted triplet

مراجع

[1] Aho‎, ‎A.V‎. ‎Sagiv‎, ‎Y‎. ‎Szymanski‎, ‎T.G‎. ‎and Ullman‎, ‎J.D‎. ‎(1981)‎. ‎Inferring a tree from lowest common ancestors with an application to the %optimization of relational expressions‎, ‎SIAM Journal on Computing‎, ‎ 10(3)‎, ‎405-421‎.
[2] Bouckaert , R . Lemey , P . Dunn , M . Greenhill , S.J . Alekseyenko , A.V . Drummond , A.J . Gray , R.D . Suchard , M.A . and Atkinson , Q.D . (2012) . Mapping the origins and expansion of the Indo-European language family . Science , 337(6097) , 957-960 .
[3] Bryant , D . (1997) . Building trees , hunting for trees , and comparing trees : theory and methods in phylogenetic analysis , University of Canterbury . Mathematics and Statistics .
[4] Byrka , J . Gawrychowski , P . Huber , K . T . and Kelk , S . (2010) . Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks . Journal of Discrete Algorithms , 8(1) , 65-75 .
[5] Chor , B . Hendy , M . and Penny , D . (2007) . Analytic solutions for three taxon ML trees with variable rates across sites , Discrete Applied Mathematics , 155(6-7) , 750-758 .
[6] Eades , P. , Lin , X. , and Smyth , W . F . (1993) . A fast and effective heuristic for the feedback arc set problem , Information Processing Letters , 47(6) , 319-323 .
[7] Eslahchi , C . Hassanzadeh , R . Mottaghi , E . Habibi , M . Pezeshk , H . and Sadeghi , M . (2012) . Constructing circular phylogenetic networks from weighted quartets using simulated annealing , Mathematical biosciences , 235(2) , 123-127 .
[8] Felsenstein , J . (2003) . Inferring Phylogenies . Sunderland , Sinauer Ass . Inc . Publishers .
 [9] Gasieniec , L . Jansson , J . Lingas , A . and ?stlin , A . (1999) . On the complexity of constructing evolutionary trees . Journal of Combinatorial Optimization , 3(2-3) , 183-197 .
[10] Grassly , N . and Rambaut , A . (1997).Treevole : a program to simulate the evolution of DNA sequences under different population dynamic scenarios , Wellcome Centre for Infectious Disease , Department of Zoology .
[11] Hein J . (1990) . Reconstructing evolution of sequences subject to recombination using parsimony , Mathematical biosciences , 98(2) , 185-200 .
[12] Henzinger , M.R . King , V . and Warnow , T . (1999) . Constructing a tree from homeomorphic subtrees , with applications to computational evolutionary biology , Algorithmica , 24(1) , 1-13 .
[13] Huson , D.H . and Rupp , R . and Scornavacca , C . (2010) . Phylogenetic networks : concepts , algorithms and applications , Cambridge University Press .
[14] Jahangiri , S . Hashemi , S . N . and Poormohammadi , H . (2013) . New heuristics for rooted triplet consistency, Algorithms , 6(3) , 396-406 .
[15] Jansson , J . (2001) . On the complexity of inferring rooted evolutionary trees . Electronic Notes in Discrete Mathematics , 7 , 1-4 .
[16] Jansson , J . Ng , J.H.K. Sadakane , K . and Sung , W.K . (2005) . Rooted maximum agreement supertrees , Algorithmica , 43(4) , 293-307 .
[17] Jansson , J . Nguyen , N.B . and Sung , W.K . (2006) . Algorithms for combining rooted triplets into a galled phylogenetic network , SIAM Journal on Computing , 35(5) , 1098-1121 .
[18] Jansson , J . and Sung , W.K . (2006) . Inferring a level-1 phylogenetic network from a dense set of rooted triplets , Theoretical Computer Science , 363(1) , 60-68 .
[19] Kannan , S.K . Lawler , E.L . and Warnow , T.J . (1996) . Determining the evolutionary tree using experiments, Journal of Algorithms , 21(1) , 26-50 .
[20] Maemura , K . Jansson , J . Ono , H . Sadakane , K . and Yamashita , M . (2007) . Approximation algorithms for constructing evolutionary trees from rooted triplets . In Proceedings of 10th Korea-Japan Joint Workshop on Algorithms and Computation , 56-63 .
[21] Poormohammadi H . (2012) . A New Heuristic Algorithm for MRTC Problem , Journal of Emerging Trends in Computing and Information Sciences , 3 , 1037-1041 .
[22] Poormohammadi , H . Eslahchi , C. , and Tusserkani , R . (2014) . Tripnet : a method for constructing rooted phylogenetic networks from rooted triplets , PLoS One , 9(9) , e106531 .
[23] Poormohammadi , H . and Sardari Zarchi , M . (2020) . NetCombin : An algorithm for optimal level-k network construction from triplets , Plos One , 15(9) , e0227842 .
[24] Poormohammadi , H . Sardari Zarchi , M . and Ghaneai , H . (2020) . NCHB : A method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization , Journal of Theoretical Biology , 489 , 110-144 .
[25] Reyhani , M.H . and Poormohammadi , H . (2017) . RPNCH : A method for constructing rooted phylogenetic
networks from rooted triplets based on height function . Archives of Advances in Biosciences ,
8(4) , 14-20 .
[26] Stoer , M. , and Wagner , F . (1997) . A simple min-cut algorithm , Journal of the ACM (JACM) , 44(4) , 585-591 .
[27] Van Iersel , L . Keijsper , J . Kelk , S . Stougie , L . Hagen , F . and Boekhout , T . (2008) . Constructing level-2 phylogenetic networks from triplets . In Annual International Conference on Research in Computational Molecular Biology (pp . 450-462) . Springer , Berlin , Heidelberg .
[28] Van Iersel , L . and Kelk , S . (2011) . Constructing the simplest possible phylogenetic network from triplets , Algorithmica , 60(2) , 207-235 .
[29] Wu , B . Y . (2004) . Constructing the maximum consensus tree from rooted triples . Journal of Combinatorial Optimization , 8(1) , 29-39 .
مجله مدل‌سازی پیشرفته ریاضی
دوره 11، شماره 2
تیر 1400
صفحه 195-209

فایل ها

سابقه مقاله

  • تاریخ دریافت: 31 شهریور 1399
  • تاریخ بازنگری: 01 دی 1399
  • تاریخ پذیرش: 29 دی 1399

هم رسانی

ارجاع به این مقاله

آمار