Bioinformatics Research Center, Aarhus University, Aarhus, Denmark.
BMC Bioinformatics. 2011 Dec 5;12:465. doi: 10.1186/1471-2105-12-465.
Continuous time Markov chains (CTMCs) is a widely used model for describing the evolution of DNA sequences on the nucleotide, amino acid or codon level. The sufficient statistics for CTMCs are the time spent in a state and the number of changes between any two states. In applications past evolutionary events (exact times and types of changes) are unaccessible and the past must be inferred from DNA sequence data observed in the present.
We describe and implement three algorithms for computing linear combinations of expected values of the sufficient statistics, conditioned on the end-points of the chain, and compare their performance with respect to accuracy and running time. The first algorithm is based on an eigenvalue decomposition of the rate matrix (EVD), the second on uniformization (UNI), and the third on integrals of matrix exponentials (EXPM). The implementation in R of the algorithms is available at http://www.birc.au.dk/~paula/.
We use two different models to analyze the accuracy and eight experiments to investigate the speed of the three algorithms. We find that they have similar accuracy and that EXPM is the slowest method. Furthermore we find that UNI is usually faster than EVD.
连续时间马尔可夫链（CTMC）是一种广泛用于描述核苷酸、氨基酸或密码子水平上 DNA 序列演变的模型。CTMC 的充分统计量是在一个状态中花费的时间和在任何两个状态之间发生的变化次数。在应用中，过去的进化事件（确切的时间和变化类型）是无法访问的，必须从当前观察到的 DNA 序列数据中推断过去。
我们描述并实现了三种算法，用于计算充分统计量的线性组合，条件是链的终点，并比较它们在准确性和运行时间方面的性能。第一种算法基于速率矩阵的特征值分解（EVD），第二种算法基于均匀化（UNI），第三种算法基于矩阵指数的积分（EXPM）。算法在 R 中的实现可在 http://www.birc.au.dk/~paula/ 获得。
我们使用两种不同的模型来分析准确性，并进行了八项实验来研究三种算法的速度。我们发现它们具有相似的准确性，并且 EXPM 是最慢的方法。此外，我们发现 UNI 通常比 EVD 更快。
