Algorithms For Phylogeny Reconstruction In a New Mathematical Model

Gabriele Lenzini, Silvia Marianelli

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
16 Downloads (Pure)

Abstract

The evolutionary history of a set of species is represented by a tree called phylogenetic tree or phylogeny. Its structure depends on precise biological assumptions about the evolution of species. Problems related to phylogeny reconstruction (i.e., finding a tree representation of information regarding a set of items) are widely studied in computer science. Most of these problems have found to be NP-hard. Sometimes they can solved polynomially if appropriate restrictions on the structure of the tree are fixed. This paper summarizes the most recent problems and results in phylogeny reconstruction, and introduces an innovative tree model, called Phylogenetic Parsimonious Tree, which is justified by significant biological hypothesis. Using PPT two problems are studied: the existence and the reconstruction of a tree both when sequences of characters and partial order on interspecies distances are given. We rove complexity results that confirm the hardness of this class of problems.
Original languageUndefined
Pages (from-to)1-24
Number of pages24
JournalCalcolo - A Quarterly on Numerical Analysis and Theory of Computation
Volume1-4
Issue number34
Publication statusPublished - 1997

Keywords

  • EWI-1073
  • IR-64234

Cite this

@article{de01b171aa364afe862d82b6460bdbd3,
title = "Algorithms For Phylogeny Reconstruction In a New Mathematical Model",
abstract = "The evolutionary history of a set of species is represented by a tree called phylogenetic tree or phylogeny. Its structure depends on precise biological assumptions about the evolution of species. Problems related to phylogeny reconstruction (i.e., finding a tree representation of information regarding a set of items) are widely studied in computer science. Most of these problems have found to be NP-hard. Sometimes they can solved polynomially if appropriate restrictions on the structure of the tree are fixed. This paper summarizes the most recent problems and results in phylogeny reconstruction, and introduces an innovative tree model, called Phylogenetic Parsimonious Tree, which is justified by significant biological hypothesis. Using PPT two problems are studied: the existence and the reconstruction of a tree both when sequences of characters and partial order on interspecies distances are given. We rove complexity results that confirm the hardness of this class of problems.",
keywords = "EWI-1073, IR-64234",
author = "Gabriele Lenzini and Silvia Marianelli",
note = "Imported from DIES",
year = "1997",
language = "Undefined",
volume = "1-4",
pages = "1--24",
journal = "Calcolo - A Quarterly on Numerical Analysis and Theory of Computation",
issn = "0008-0624",
publisher = "Springer",
number = "34",

}

Algorithms For Phylogeny Reconstruction In a New Mathematical Model. / Lenzini, Gabriele; Marianelli, Silvia.

In: Calcolo - A Quarterly on Numerical Analysis and Theory of Computation, Vol. 1-4, No. 34, 1997, p. 1-24.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Algorithms For Phylogeny Reconstruction In a New Mathematical Model

AU - Lenzini, Gabriele

AU - Marianelli, Silvia

N1 - Imported from DIES

PY - 1997

Y1 - 1997

N2 - The evolutionary history of a set of species is represented by a tree called phylogenetic tree or phylogeny. Its structure depends on precise biological assumptions about the evolution of species. Problems related to phylogeny reconstruction (i.e., finding a tree representation of information regarding a set of items) are widely studied in computer science. Most of these problems have found to be NP-hard. Sometimes they can solved polynomially if appropriate restrictions on the structure of the tree are fixed. This paper summarizes the most recent problems and results in phylogeny reconstruction, and introduces an innovative tree model, called Phylogenetic Parsimonious Tree, which is justified by significant biological hypothesis. Using PPT two problems are studied: the existence and the reconstruction of a tree both when sequences of characters and partial order on interspecies distances are given. We rove complexity results that confirm the hardness of this class of problems.

AB - The evolutionary history of a set of species is represented by a tree called phylogenetic tree or phylogeny. Its structure depends on precise biological assumptions about the evolution of species. Problems related to phylogeny reconstruction (i.e., finding a tree representation of information regarding a set of items) are widely studied in computer science. Most of these problems have found to be NP-hard. Sometimes they can solved polynomially if appropriate restrictions on the structure of the tree are fixed. This paper summarizes the most recent problems and results in phylogeny reconstruction, and introduces an innovative tree model, called Phylogenetic Parsimonious Tree, which is justified by significant biological hypothesis. Using PPT two problems are studied: the existence and the reconstruction of a tree both when sequences of characters and partial order on interspecies distances are given. We rove complexity results that confirm the hardness of this class of problems.

KW - EWI-1073

KW - IR-64234

M3 - Article

VL - 1-4

SP - 1

EP - 24

JO - Calcolo - A Quarterly on Numerical Analysis and Theory of Computation

JF - Calcolo - A Quarterly on Numerical Analysis and Theory of Computation

SN - 0008-0624

IS - 34

ER -