A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA or protein sequences. Among different criteria used for this purpose, the minimum evolution criterion is an optimality based criterion aiming to rebuild PT characterized by a minimal length. This problem is known to be NP-hard. We introduce in this article some mixed integer programming models, and we also study possible cuts and lower bounds for the optimal value. So far, the number of sequences that can be involved in optimal phylogenetic reconstruction is still limited to 10.

Mathematical Models to Reconstruct Phylogenetic Trees Under the Minimum Evolution Criterion

PESENTI, Raffaele;
2009-01-01

Abstract

A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA or protein sequences. Among different criteria used for this purpose, the minimum evolution criterion is an optimality based criterion aiming to rebuild PT characterized by a minimal length. This problem is known to be NP-hard. We introduce in this article some mixed integer programming models, and we also study possible cuts and lower bounds for the optimal value. So far, the number of sequences that can be involved in optimal phylogenetic reconstruction is still limited to 10.
2009
53(2)
File in questo prodotto:
File Dimensione Formato  
Networks3TREES.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 209.52 kB
Formato Adobe PDF
209.52 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/29306
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact