title: Sufficient statistics and expectation maximization algorithms in phylogenetic tree models.
abstract: BACKGROUND
  Measuring evolutionary conservation is a routine step in the identification of functional elements in genome sequences. Although a number of studies have proposed methods that use the continuous time Markov models (CTMMs) to find evolutionarily constrained elements, their probabilistic structures have been less frequently investigated.
  
  
  RESULTS
  In this article, we investigate a sufficient statistic for CTMMs. The statistic is composed of the fractional duration of nucleotide characters over evolutionary time, F(d), and the number of substitutions occurring in phylogenetic trees, N(s). We first derive basic properties of the sufficient statistic. Then, we derive an expectation maximization (EM) algorithm for estimating the parameters of a phylogenetic model, which iteratively computes the expectation values of the sufficient statistic. We show that the EM algorithm exhibits much faster convergence than other optimization methods that use numerical gradient descent algorithms. Finally, we investigate the genome-wide distribution of fractional duration time F(d) which, unlike the number of substitutions N(s), has rarely been investigated. We show that F(d) has evolutionary information that is distinct from that in N(s), which may be useful for detecting novel types of evolutionary constraints existing in the human genome.
  
  
  BACKGROUND
  The C++ source code of the 'Fdur' software is available at http://www.ncrna.org/software/fdur/
  
  
  BACKGROUND
  kiryu-h@k.u-tokyo.ac.jp
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, Kashiwa, Chiba 277-8561, Japan. kiryu-h@k.u-tokyo.ac.jp
authors.forename: Hisanori
authors.initials: H
authors.lastname: Kiryu
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D015894:Genome, Human; D023281:Genomics / Q000379:methods; D006801:Humans; D008390:Markov Chains; D010802:Phylogeny