title: Non-Markovian effects on protein sequence evolution due to site dependent substitution rates.
abstract: BACKGROUND
  Many models of protein sequence evolution, in particular those based on Point Accepted Mutation (PAM) matrices, assume that its dynamics is Markovian. Nevertheless, it has been observed that evolution seems to proceed differently at different time scales, questioning this assumption. In 2011 Kosiol and Goldman proved that, if evolution is Markovian at the codon level, it can not be Markovian at the amino acid level. However, it remains unclear up to which point the Markov assumption is verified at the codon level.
  
  
  RESULTS
  Here we show how also the among-site variability of substitution rates makes the process of full protein sequence evolution effectively not Markovian even at the codon level. This may be the theoretical explanation behind the well known systematic underestimation of evolutionary distances observed when omitting rate variability. If the substitution rate variability is neglected the average amino acid and codon replacement probabilities are affected by systematic errors and those with the largest mismatches are the substitutions involving more than one nucleotide at a time. On the other hand, the instantaneous substitution matrices estimated from alignments with the Markov assumption tend to overestimate double and triple substitutions, even when learned from alignments at high sequence identity.
  
  
  CONCLUSIONS
  These results discourage the use of simple Markov models to describe full protein sequence evolution and encourage to employ, whenever possible, models that account for rate variability by construction (such as hidden Markov models or mixture models) or substitution models of the type of Le and Gascuel (2008) that account for it explicitly.
authors.affiliation: International School for Advanced Studies (SISSA), Via Bonomea 265, Trieste, 34136, Italy.
authors.forename: Francesca
authors.initials: F
authors.lastname: Rizzato
authors.affiliation: International School for Advanced Studies (SISSA), Via Bonomea 265, Trieste, 34136, Italy.
authors.forename: Alex
authors.initials: A
authors.lastname: Rodriguez
authors.affiliation: International School for Advanced Studies (SISSA), Via Bonomea 265, Trieste, 34136, Italy. laio@sissa.it.
authors.forename: Alessandro
authors.initials: A
authors.lastname: Laio
mesh_terms: D000595:Amino Acid Sequence; D003062:Codon; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D011506:Proteins / Q000737:chemistry / Q000235:genetics*
chemical_list: D003062:Codon; D011506:Proteins
keywords: Amino acid substitution matrices; Evolutionary distances; Non-Markovian evolution; Protein sequence evolution; Substitution rate variability