Tarnas C, Hughey R
Department of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, CA 95064, USA.
Bioinformatics. 1998 Jun;14(5):401-6. doi: 10.1093/bioinformatics/14.5.401.
Complete forward-backward (Baum-Welch) hidden Markov model training cannot take advantage of the linear space, divide-and-conquer sequence alignment algorithms because of the examination of all possible paths rather than the single best path.
This paper discusses the implementation and performance of checkpoint-based reduced space sequence alignment in the SAM hidden Markov modeling package. Implementation of the checkpoint algorithm reduced memory usage from O(mn) to O (m square root n) with only a 10% slowdown for small m and n, and vast speed-up for the larger values, such as m = n = 2000, that cause excessive paging on a 96 Mbyte workstation. The results are applicable to other types of dynamic programming.
A World-Wide Web server, as well as information on obtaining the Sequence Alignment and Modeling (SAM) software suite, can be found at http://www.cse.ucsc. edu/research/compbio/sam.html.
完整的前向-后向（鲍姆-韦尔奇）隐马尔可夫模型训练无法利用线性空间、分治序列比对算法，因为它考察的是所有可能路径而非单一最佳路径。
本文讨论了基于检查点的缩减空间序列比对在SAM隐马尔可夫建模软件包中的实现与性能。检查点算法的实现将内存使用从O(mn)减少到O(m√n)，对于较小的m和n，速度仅降低10%，而对于较大的值（如m = n = 2000），速度大幅提升，这些值在96兆字节的工作站上会导致过多的分页。结果适用于其他类型的动态规划。
可在http://www.cse.ucsc.edu/research/compbio/sam.html找到万维网服务器以及获取序列比对与建模（SAM）软件套件的信息。
