Login / Signup

Reconstruction of time-consistent species trees.

Manuel LafondMarc Hellmuth
Published in: Algorithms for molecular biology : AMB (2020)
In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a time-consistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a "time-consistent" species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity.
Keyphrases
  • copy number
  • genome wide
  • genome wide identification
  • genetic diversity
  • pet imaging
  • mental health
  • machine learning
  • magnetic resonance imaging
  • gene expression
  • deep learning
  • transcription factor
  • neural network