IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v300y2022i1p1-19.html
   My bibliography  Save this article

A tutorial on the balanced minimum evolution problem

Author

Listed:
  • Catanzaro, Daniele
  • Frohn, Martin
  • Gascuel, Olivier
  • Pesenti, Raffaele

Abstract

The Balanced Minimum Evolution Problem (BMEP) is an APX-hard network design problem that consists of finding a minimum length unrooted binary tree (also called a phylogeny) having as a leaf-set a given set of molecular sequences. The optimal solution to the BMEP (i.e., the optimal phylogeny) encodes the hierarchical evolutionary relationships of the input sequences. This information is crucial for a multitude of research fields, ranging from systematics to medical research, passing through drug discovery, epidemiology, ecology, biodiversity assessment and population dynamics. In this article, we introduce the reader to the problem and present the current state-of-the-art; we include the most important achievements reached so far and the challenges that still remain to be addressed.

Suggested Citation

  • Catanzaro, Daniele & Frohn, Martin & Gascuel, Olivier & Pesenti, Raffaele, 2022. "A tutorial on the balanced minimum evolution problem," European Journal of Operational Research, Elsevier, vol. 300(1), pages 1-19.
    • Handle: RePEc:eee:ejores:v:300:y:2022:i:1:p:1-19
    DOI: 10.1016/j.ejor.2021.08.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721006718
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.08.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Catanzaro, Daniele & Aringhieri, Roberto & Di Summa, Marco & Pesenti, Raffaele, 2015. "A branch-price-and-cut algorithm for the minimum evolution problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 753-765.
    2. Peng Zhou & Xing-Lou Yang & Xian-Guang Wang & Ben Hu & Lei Zhang & Wei Zhang & Hao-Rui Si & Yan Zhu & Bei Li & Chao-Lin Huang & Hui-Dong Chen & Jing Chen & Yun Luo & Hua Guo & Ren-Di Jiang & Mei-Qin L, 2020. "Addendum: A pneumonia outbreak associated with a new coronavirus of probable bat origin," Nature, Nature, vol. 588(7836), pages 6-6, December.
    3. Li, Shasha & Tu, Jianhua & Yu, Chenyan, 2016. "The generalized 3-connectivity of star graphs and bubble-sort graphs," Applied Mathematics and Computation, Elsevier, vol. 274(C), pages 41-46.
    4. Catanzaro, Daniele & Pesenti, Raffaele & Wolsey, Laurence, 2020. "On the balanced minimum evolution polytope," LIDAM Reprints CORE 3096, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Peng Zhou & Xing-Lou Yang & Xian-Guang Wang & Ben Hu & Lei Zhang & Wei Zhang & Hao-Rui Si & Yan Zhu & Bei Li & Chao-Lin Huang & Hui-Dong Chen & Jing Chen & Yun Luo & Hua Guo & Ren-Di Jiang & Mei-Qin L, 2020. "A pneumonia outbreak associated with a new coronavirus of probable bat origin," Nature, Nature, vol. 579(7798), pages 270-273, March.
    6. Xing-Yi Ge & Jia-Lu Li & Xing-Lou Yang & Aleksei A. Chmura & Guangjian Zhu & Jonathan H. Epstein & Jonna K. Mazet & Ben Hu & Wei Zhang & Cheng Peng & Yu-Ji Zhang & Chu-Ming Luo & Bing Tan & Ning Wang , 2013. "Isolation and characterization of a bat SARS-like coronavirus that uses the ACE2 receptor," Nature, Nature, vol. 503(7477), pages 535-538, November.
    7. Daniele Catanzaro & Raffaele Pesenti, 2019. "Enumerating vertices of the balanced minimum evolution polytope," LIDAM Reprints CORE 3005, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Daniele Catanzaro & Martine Labbé & Raffaele Pesenti & Juan-José Salazar-González, 2012. "The Balanced Minimum Evolution Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 276-294, May.
    9. Olivier Gascuel & Denise Levy, 1996. "A reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance," Journal of Classification, Springer;The Classification Society, vol. 13(1), pages 129-155, March.
    10. Daniele CATANZARO & Stanley E. SCHACKNEY & Alejandro A. SCHÄFFER & Russell SCHWARTZ, 2016. "Classifying the progression of Ductal Carcinoma from single-cell sampled data via integer linear programming: a case study," LIDAM Reprints CORE 2778, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Daniele CATANZARO & Roberto ARINGHIERI & Mardo DI SUMMA & Raffaele PESENTI, 2015. "A branch-price-and-cut algorithm for the minimum evolution problem," LIDAM Reprints CORE 2767, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Olivier Gascuel & Andy McKenzie, 2004. "Performance Analysis of Hierarchical Clustering Algorithms," Journal of Classification, Springer;The Classification Society, vol. 21(1), pages 3-18, March.
    13. Catanzaro, Daniele & Frohn, Martin & Pesenti, Raffaele, 2020. "An information theory perspective on the balanced minimum evolution problem," LIDAM Reprints CORE 3097, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Catanzaro, Daniele & Frohn, Martin & Gascuel, Olivier & Pesenti, Raffaele, 2023. "A Massively Parallel Exact Solution Algorithm for the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2023001, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Gasparin, Andrea & Camerota Verdù, Federico Julian & Catanzaro, Daniele, 2023. "An evolution strategy approach for the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2023021, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Catanzaro, Daniele & Frohn, Martin & Gascuel, Olivier & Pesenti, Raffaele, 2021. "A Tutorial on the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 20210, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Catanzaro, Daniele & Frohn, Martin & Gascuel, Olivier & Pesenti, Raffaele, 2023. "A Massively Parallel Exact Solution Algorithm for the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2023001, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Catanzaro, Daniele & Frohn, Martin & Pesenti, Raffaele, 2021. "A Massively Parallel Exact Solution Algorithm for the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2021023, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Catanzaro, Daniele & Frohn, Martin & Pesenti, Raffaele, 2021. "On Numerical Stability and Statistical Consistency of the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2021026, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Gasparin, Andrea & Camerota Verdù, Federico Julian & Catanzaro, Daniele, 2023. "An evolution strategy approach for the Balanced Minimum Evolution Problem," LIDAM Discussion Papers CORE 2023021, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Jun-Yu Si & Yuan-Mei Chen & Ye-Hui Sun & Meng-Xue Gu & Mei-Ling Huang & Lu-Lu Shi & Xiao Yu & Xiao Yang & Qing Xiong & Cheng-Bao Ma & Peng Liu & Zheng-Li Shi & Huan Yan, 2024. "Sarbecovirus RBD indels and specific residues dictating multi-species ACE2 adaptiveness," Nature Communications, Nature, vol. 15(1), pages 1-15, December.
    7. Olga Fajarda & Cristina Requejo, 2022. "MIP model-based heuristics for the minimum weighted tree reconstruction problem," Operational Research, Springer, vol. 22(3), pages 2305-2342, July.
    8. Jing Wang & Yuan-fei Pan & Li-fen Yang & Wei-hong Yang & Kexin Lv & Chu-ming Luo & Juan Wang & Guo-peng Kuang & Wei-chen Wu & Qin-yu Gou & Gen-yang Xin & Bo Li & Huan-le Luo & Shoudeng Chen & Yue-long, 2023. "Individual bat virome analysis reveals co-infection and spillover among bats and virus zoonotic potential," Nature Communications, Nature, vol. 14(1), pages 1-13, December.
    9. Cecilia A. Sánchez & Hongying Li & Kendra L. Phelps & Carlos Zambrana-Torrelio & Lin-Fa Wang & Peng Zhou & Zheng-Li Shi & Kevin J. Olival & Peter Daszak, 2022. "A strategy to assess spillover risk of bat SARS-related coronaviruses in Southeast Asia," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    10. Yelin Han & Panpan Xu & Yuyang Wang & Wenliang Zhao & Junpeng Zhang & Shuyi Zhang & Jianwei Wang & Qi Jin & Zhiqiang Wu, 2023. "Panoramic analysis of coronaviruses carried by representative bat species in Southern China to better understand the coronavirus sphere," Nature Communications, Nature, vol. 14(1), pages 1-20, December.
    11. Shahadat Uddin & Arif Khan & Haohui Lu & Fangyu Zhou & Shakir Karim, 2022. "Suburban Road Networks to Explore COVID-19 Vulnerability and Severity," IJERPH, MDPI, vol. 19(4), pages 1-9, February.
    12. Kirsten R.C. Hensgens & Inge H.T. van Rensen & Anita W. Lekx & Frits H.M. van Osch & Lieve H.H. Knarren & Caroline E. Wyers & Joop P. van den Bergh & Dennis G. Barten, 2021. "Sort and Sieve: Pre-Triage Screening of Patients with Suspected COVID-19 in the Emergency Department," IJERPH, MDPI, vol. 18(17), pages 1-11, September.
    13. Quan-Hoang Vuong & Tam-Tri Le & Viet-Phuong La & Huyen Thanh Thanh Nguyen & Manh-Toan Ho & Quy Khuc & Minh-Hoang Nguyen, 2022. "Covid-19 vaccines production and societal immunization under the serendipity-mindsponge-3D knowledge management theory and conceptual framework," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-12, December.
    14. Hengrui Liu & Sho Iketani & Arie Zask & Nisha Khanizeman & Eva Bednarova & Farhad Forouhar & Brandon Fowler & Seo Jung Hong & Hiroshi Mohri & Manoj S. Nair & Yaoxing Huang & Nicholas E. S. Tay & Sumin, 2022. "Development of optimized drug-like small molecule inhibitors of the SARS-CoV-2 3CL protease for treatment of COVID-19," Nature Communications, Nature, vol. 13(1), pages 1-16, December.
    15. Graziella Orrù & Ciro Conversano & Eleonora Malloggi & Francesca Francesconi & Rebecca Ciacchini & Angelo Gemignani, 2020. "Neurological Complications of COVID-19 and Possible Neuroinvasion Pathways: A Systematic Review," IJERPH, MDPI, vol. 17(18), pages 1-18, September.
    16. Gleidson Sobreira Leite & Adriano Bessa Albuquerque & Plácido Rogerio Pinheiro, 2021. "Applications of Technological Solutions in Primary Ways of Preventing Transmission of Respiratory Infectious Diseases—A Systematic Literature Review," IJERPH, MDPI, vol. 18(20), pages 1-50, October.
    17. Britton Boras & Rhys M. Jones & Brandon J. Anson & Dan Arenson & Lisa Aschenbrenner & Malina A. Bakowski & Nathan Beutler & Joseph Binder & Emily Chen & Heather Eng & Holly Hammond & Jennifer Hammond , 2021. "Preclinical characterization of an intravenous coronavirus 3CL protease inhibitor for the potential treatment of COVID19," Nature Communications, Nature, vol. 12(1), pages 1-17, December.
    18. Susanne Kessler & Bradly Burke & Geoffroy Andrieux & Jan Schinköthe & Lea Hamberger & Johannes Kacza & Shijun Zhan & Clara Reasoner & Taru S. Dutt & Maria Kaukab Osman & Marcela Henao-Tamayo & Julian , 2024. "Deciphering bat influenza H18N11 infection dynamics in male Jamaican fruit bats on a single-cell level," Nature Communications, Nature, vol. 15(1), pages 1-18, December.
    19. Yongzhu Xiong & Yunpeng Wang & Feng Chen & Mingyong Zhu, 2020. "Spatial Statistics and Influencing Factors of the COVID-19 Epidemic at Both Prefecture and County Levels in Hubei Province, China," IJERPH, MDPI, vol. 17(11), pages 1-26, May.
    20. Eugene Song & Jae-Eun Lee & Seola Kwon, 2021. "Effect of Public Empathy with Infection-Control Guidelines on Infection-Prevention Attitudes and Behaviors: Based on the Case of COVID-19," IJERPH, MDPI, vol. 18(24), pages 1-18, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:300:y:2022:i:1:p:1-19. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.