skip to main content
Ngôn ngữ:
Giới hạn tìm kiếm: Giới hạn tìm kiếm: Dạng tài nguyên Hiển thị kết quả với: Hiển thị kết quả với: Chỉ mục

Do Branch Lengths Help to Locate a Tree in a Phylogenetic Network?(Report)

Gambette, Philippe ; Iersel, Leo ; Kelk, Steven ; Pardi, Fabio ; Scornavacca, Celine

Bulletin of Mathematical Biology, 2016, Vol.78(9), p.1773(23) [Tạp chí có phản biện]

ISSN: 0092-8240 ; DOI: 10.1007/s11538-016-0199-4

Toàn văn sẵn có

Trích dẫn Trích dẫn bởi
  • Nhan đề:
    Do Branch Lengths Help to Locate a Tree in a Phylogenetic Network?(Report)
  • Tác giả: Gambette, Philippe ; Iersel, Leo ; Kelk, Steven ; Pardi, Fabio ; Scornavacca, Celine
  • Chủ đề: Phylogeny – Analysis ; Evolutionary Biology – Analysis
  • Là 1 phần của: Bulletin of Mathematical Biology, 2016, Vol.78(9), p.1773(23)
  • Mô tả: To access, purchase, authenticate, or subscribe to the full-text of this article, please visit this link: http://dx.doi.org/10.1007/s11538-016-0199-4 Byline: Philippe Gambette (1), Leo Iersel (2), Steven Kelk (3), Fabio Pardi (4), Celine Scornavacca (5) Keywords: Phylogenetic network; Tree containment; Branch lengths; Displayed trees; Computational complexity Abstract: Phylogenetic networks are increasingly used in evolutionary biology to represent the history of species that have undergone reticulate events such as horizontal gene transfer, hybrid speciation and recombination. One of the most fundamental questions that arise in this context is whether the evolution of a gene with one copy in all species can be explained by a given network. In mathematical terms, this is often translated in the following way: is a given phylogenetic tree contained in a given phylogenetic network? Recently this tree containment problem has been widely investigated from a computational perspective, but most studies have only focused on the topology of the phylogenies, ignoring a piece of information that, in the case of phylogenetic trees, is routinely inferred by evolutionary analyses: branch lengths. These measure the amount of change (e.g., nucleotide substitutions) that has occurred along each branch of the phylogeny. Here, we study a number of versions of the tree containment problem that explicitly account for branch lengths. We show that, although length information has the potential to locate more precisely a tree within a network, the problem is computationally hard in its most general form. On a positive note, for a number of special cases of biological relevance, we provide algorithms that solve this problem efficiently. This includes the case of networks of limited complexity, for which it is possible to recover, among the trees contained by the network with the same topology as the input tree, the closest one in terms of branch lengths. Author Affiliation: (1) LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM, Universite Paris-Est, 77454, Marne-la-Vallee, France (2) Delft Institute of Applied Mathematics, Delft University of Technology, Postbus 5031, 2600 GA, Delft, The Netherlands (3) Department of Data Science and Knowledge Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD, Maastricht, The Netherlands (4) Institut de Biologie Computationnelle (IBC) Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier (LIRMM), CNRS, Universite de Montpellier, Montpellier, France (5) Institut de Biologie Computationnelle (IBC) Institut des Sciences de l'Evolution, CC 064 Place Eugene Bataillon, Montpellier, France Article History: Registration Date: 16/08/2016 Received Date: 10/05/2016 Accepted Date: 16/08/2016 Online Date: 22/09/2016
  • Ngôn ngữ: English
  • Số nhận dạng: ISSN: 0092-8240 ; DOI: 10.1007/s11538-016-0199-4

Đang tìm Cơ sở dữ liệu bên ngoài...