{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T20:50:53Z","timestamp":1790023853845,"version":"4.0.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background:<\/jats:title><jats:p>Baum-Welch training is an expectation-maximisation algorithm for training the emission and transition probabilities of hidden Markov models in a fully automated way. It can be employed as long as a training set of annotated sequences is known, and provides a rigorous way to derive parameter values which are guaranteed to be at least locally optimal. For complex hidden Markov models such as pair hidden Markov models and very long training sequences, even the most efficient algorithms for Baum-Welch training are currently too memory-consuming. This has so far effectively prevented the automatic parameter training of hidden Markov models that are currently used for biological sequence analyses.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results:<\/jats:title><jats:p>We introduce the first linear space algorithm for Baum-Welch training. For a hidden Markov model with<jats:italic>M<\/jats:italic>states,<jats:italic>T<\/jats:italic>free transition and<jats:italic>E<\/jats:italic>free emission parameters, and an input sequence of length<jats:italic>L<\/jats:italic>, our new algorithm requires<jats:italic>O<\/jats:italic>(<jats:italic>M<\/jats:italic>) memory and<jats:italic>O<\/jats:italic>(<jats:italic>LMT<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub>(<jats:italic>T + E<\/jats:italic>)) time for one Baum-Welch iteration, where<jats:italic>T<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub>is the maximum number of states that any state is connected to. The most memory efficient algorithm until now was the checkpointing algorithm with<jats:italic>O<\/jats:italic>(log(<jats:italic>L<\/jats:italic>)<jats:italic>M<\/jats:italic>) memory and<jats:italic>O<\/jats:italic>(log(<jats:italic>L<\/jats:italic>)<jats:italic>LMT<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub>) time requirement. Our novel algorithm thus renders the memory requirement completely independent of the length of the training sequences. More generally, for an n-hidden Markov model and n input sequences of length<jats:italic>L<\/jats:italic>, the memory requirement of<jats:italic>O<\/jats:italic>(log(<jats:italic>L<\/jats:italic>)<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic>-1<\/jats:sup><jats:italic>M<\/jats:italic>) is reduced to<jats:italic>O<\/jats:italic>(<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic>-1<\/jats:sup><jats:italic>M<\/jats:italic>) memory while the running time is changed from<jats:italic>O<\/jats:italic>(log(<jats:italic>L<\/jats:italic>)<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup><jats:italic>MT<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub>+<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>(<jats:italic>T<\/jats:italic>+<jats:italic>E<\/jats:italic>)) to<jats:italic>O<\/jats:italic>(<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup><jats:italic>MT<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub>(<jats:italic>T<\/jats:italic>+<jats:italic>E<\/jats:italic>)).<\/jats:p><jats:p>An added advantage of our new algorithm is that a reduced time requirement can be traded for an increased memory requirement and<jats:italic>vice versa<\/jats:italic>, such that for any<jats:italic>c<\/jats:italic>\u2208 {1, ..., (<jats:italic>T<\/jats:italic>+<jats:italic>E<\/jats:italic>)}, a time requirement of<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup><jats:italic>MT<\/jats:italic><jats:sub><jats:italic>max<\/jats:italic><\/jats:sub><jats:italic>c<\/jats:italic>incurs a memory requirement of<jats:italic>L<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic>-1<\/jats:sup><jats:italic>M<\/jats:italic>(<jats:italic>T<\/jats:italic>+<jats:italic>E<\/jats:italic>-<jats:italic>c<\/jats:italic>).<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>For the large class of hidden Markov models used for example in gene prediction, whose number of states does not scale with the length of the input sequence, our novel algorithm can thus be both faster and more memory-efficient than any of the existing algorithms.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-6-231","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T06:13:57Z","timestamp":1127196837000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["A linear memory algorithm for Baum-Welch training"],"prefix":"10.1186","volume":"6","author":[{"given":"Istv\u00e1n","family":"Mikl\u00f3s","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Irmtraud M","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,9,19]]},"reference":[{"key":"556_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological sequence analysis. Cambridge University Press; 1998."},{"key":"556_CR2","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","volume":"235","author":"A Krogh","year":"1994","unstructured":"Krogh A, Brown M, Mian IS, Sj\u00f6lander K, Haussler D: Hidden Markov models in biology: Applications to protein modelling. J Mol Biol 1994, 235: 1501\u20131531. 10.1006\/jmbi.1994.1104","journal-title":"J Mol Biol"},{"key":"556_CR3","volume-title":"HMMER: Profile hidden Markov models for biological sequence analysis","author":"S Eddy","year":"2001","unstructured":"Eddy S: HMMER: Profile hidden Markov models for biological sequence analysis.2001. [http:\/\/hmmer.wustl.edu\/]"},{"issue":"10","key":"556_CR4","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1093\/bioinformatics\/18.10.1309","volume":"18","author":"IM Meyer","year":"2002","unstructured":"Meyer IM, Durbin R: Comparative ab initio prediction of gene structures using pair HMMs. Bioinformatics 2002, 18(10):1309\u20131318. 10.1093\/bioinformatics\/18.10.1309","journal-title":"Bioinformatics"},{"issue":"2","key":"556_CR5","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1093\/nar\/gkh211","volume":"32","author":"IM Meyer","year":"2004","unstructured":"Meyer IM, Durbin R: Gene structure conservation aids similarity based gene prediction. Nucleic Acids Research 2004, 32(2):776\u2013783. 10.1093\/nar\/gkh211","journal-title":"Nucleic Acids Research"},{"key":"556_CR6","first-page":"260","volume-title":"IEEE Trans Infor Theor","author":"A Viterbi","year":"1967","unstructured":"Viterbi A: Error bounds for convolutional codes and an assymptotically optimum decoding algorithm. IEEE Trans Infor Theor 1967, 260\u2013269. 10.1109\/TIT.1967.1054010"},{"key":"556_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"AP Dempster","year":"1977","unstructured":"Dempster AP, Laird NM, Rubin DB: Maximum likelihood from incomplete data via the EM algorithm. J Roy Stat Soc B 1977, 39: 1\u201338.","journal-title":"J Roy Stat Soc B"},{"key":"556_CR8","first-page":"1","volume":"3","author":"LE Baum","year":"1972","unstructured":"Baum LE: An equality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes. Inequalities 1972, 3: 1\u20138.","journal-title":"Inequalities"},{"key":"556_CR9","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS: A linear space algorithm for computing maximal common subsequences. Commun ACM 1975, 18: 341\u2013343. 10.1145\/360825.360861","journal-title":"Commun ACM"},{"key":"556_CR10","first-page":"11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W: Optimal alignments in linear space. CABIOS 1988, 4: 11\u201317.","journal-title":"CABIOS"},{"key":"556_CR11","first-page":"45","volume":"13","author":"JA Grice","year":"1997","unstructured":"Grice JA, Hughey R, Speck D: Reduced space sequence alignment. CABIOS 1997, 13: 45\u201353.","journal-title":"CABIOS"},{"issue":"5","key":"556_CR12","doi-asserted-by":"publisher","first-page":"4001","DOI":"10.1093\/bioinformatics\/14.5.401","volume":"14","author":"C Tarnas","year":"1998","unstructured":"Tarnas C, Hughey R: Reduced space hidden Markov model training. Bioinformatics 1998, 14(5):4001\u2013406. 10.1093\/bioinformatics\/14.5.401","journal-title":"Bioinformatics"},{"issue":"12","key":"556_CR13","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1093\/bioinformatics\/16.12.1082","volume":"16","author":"R Wheeler","year":"2000","unstructured":"Wheeler R, Hughey R: Optimizing reduced-space sequence analysis. Bioinformatics 2000, 16(12):1082\u20131090. 10.1093\/bioinformatics\/16.12.1082","journal-title":"Bioinformatics"},{"key":"556_CR14","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1038\/35057062","volume":"409","author":"International Human Genome Sequencing Consortium","year":"2001","unstructured":"International Human Genome Sequencing Consortium: Initial sequencing and analysis of the human genome. Nature 2001, 409: 860\u2013921. 10.1038\/35057062","journal-title":"Nature"},{"key":"556_CR15","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD Jr, Vecchi MP: Optimization by Simulated Annealing. Science 1983, 220: 671\u2013680.","journal-title":"Science"},{"key":"556_CR16","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1111\/1467-9868.00123","volume":"60","author":"GO Roberts","year":"1998","unstructured":"Roberts GO, Rosenthal JS: Optimal scaling of discrete approximations to Langevin diffusions. J R Statist Soc B 1998, 60: 255\u2013268. 10.1111\/1467-9868.00123","journal-title":"J R Statist Soc B"},{"key":"556_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1471-2105-3-18","volume":"3","author":"S Eddy","year":"2002","unstructured":"Eddy S: A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. BMC Bioinformatics 2002, 3: 18. 10.1186\/1471-2105-3-18","journal-title":"BMC Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-231.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T10:52:31Z","timestamp":1735987951000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9,19]]},"references-count":17,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["556"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-231","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9,19]]},"assertion":[{"value":"24 June 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"231"}}