{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T02:05:58Z","timestamp":1684029958071},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Hidden Markov models (HMMs) and generalized HMMs been successfully applied to many problems, but the standard Viterbi algorithm for computing the most probable interpretation of an input sequence (known as decoding) requires memory proportional to the length of the sequence, which can be prohibitive. Existing approaches to reducing memory usage either sacrifice optimality or trade increased running time for reduced memory.<\/jats:p><jats:p>Results: We developed two novel decoding algorithms, Treeterbi and Parallel Treeterbi, and implemented them in the TWINSCAN\/N-SCAN gene-prediction system. The worst case asymptotic space and time are the same as for standard Viterbi, but in practice, Treeterbi optimally decodes arbitrarily long sequences with generalized HMMs in bounded memory without increasing running time. Parallel Treeterbi uses the same ideas to split optimal decoding across processors, dividing latency to completion by approximately the number of available processors with constant average overhead per processor. Using these algorithms, we were able to optimally decode all human chromosomes with N-SCAN, which increased its accuracy relative to heuristic solutions. We also implemented Treeterbi for Pairagon, our pair HMM based cDNA-to-genome aligner.<\/jats:p><jats:p>Availability: The TWINSCAN\/N-SCAN\/PAIRAGON open source software package is available from http:\/\/genes.cse.wustl.edu.<\/jats:p><jats:p>Contact: \u00a0brent@cse.wustl.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl659","type":"journal-article","created":{"date-parts":[[2007,1,20]],"date-time":"2007-01-20T01:12:50Z","timestamp":1169255570000},"page":"545-554","source":"Crossref","is-referenced-by-count":7,"title":["The Treeterbi and Parallel Treeterbi algorithms: efficient, optimal decoding for ordinary, generalized and pair HMMs"],"prefix":"10.1093","volume":"23","author":[{"given":"Evan","family":"Keibler","sequence":"first","affiliation":[{"name":"1 Laboratory for Computational Genomics, Campus Box 1045, Washington University, St. Louis, MO 63130, USA and 2Present address: The European Molecular Biology Laboratory (EMBL), 69117 Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manimozhiyan","family":"Arumugam","sequence":"additional","affiliation":[{"name":"1 Laboratory for Computational Genomics, Campus Box 1045, Washington University, St. Louis, MO 63130, USA and 2Present address: The European Molecular Biology Laboratory (EMBL), 69117 Heidelberg, Germany"},{"name":"1 Laboratory for Computational Genomics, Campus Box 1045, Washington University, St. Louis, MO 63130, USA and 2Present address: The European Molecular Biology Laboratory (EMBL), 69117 Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Brent","sequence":"additional","affiliation":[{"name":"1 Laboratory for Computational Genomics, Campus Box 1045, Washington University, St. Louis, MO 63130, USA and 2Present address: The European Molecular Biology Laboratory (EMBL), 69117 Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,1,18]]},"reference":[{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"118","DOI":"10.2307\/1426771","article-title":"Forwards and backwards models for finite-state Markov processes","volume":"11","author":"Anderson","year":"1979","journal-title":"Adv. Appl. Probab."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/gb-2006-7-s1-s5","article-title":"Pairagon + N-SCAN_EST: a model-based gene annotation pipeline","volume":"7","author":"Arumugam","year":"2006","journal-title":"Genome Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1101\/gr.3696205","article-title":"Begin at the beginning: predicting genes with 5\u2032 UTRs","volume":"15","author":"Brown","year":"2005","journal-title":"Genome Res."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","article-title":"Prediction of complete gene structures in human genomic DNA","volume":"268","author":"Burge","year":"1997","journal-title":"J. Mol. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023041109375267700_","first-page":"114","article-title":"Multiple alignment using hidden Markov models","volume":"3","author":"Eddy","year":"1995","journal-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1093\/bioinformatics\/14.9.755","article-title":"Profile hidden Markov models","volume":"14","author":"Eddy","year":"1998","journal-title":"Bioinformatics"},{"key":"2023041109375267700_","article-title":"Hidden Markov models: estimation and control","volume-title":"Applications of Mathematics","author":"Elliot","year":"1994","edition":"2nd"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1101\/gr.830003","article-title":"Leveraging the mouse genome for gene prediction in human: from whole-genome shotgun reads to a global synteny map","volume":"13","author":"Flicek","year":"2003","journal-title":"Genome Res."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/TIT.1972.1054829","article-title":"Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference","volume":"18","author":"Forney","year":"1972","journal-title":"Information Theory, IEEE T. on"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1109\/PROC.1973.9030","article-title":"The viterbi algorithm","volume":"61","author":"Forney","year":"1973","journal-title":"Proc. IEEE"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3348.001.0001","volume-title":"Graphical Models for Machine Learning and Digital Communication","author":"Frey","year":"1998"},{"key":"2023041109375267700_","first-page":"45","article-title":"Reduced space sequence alignment","volume":"13","author":"Grice","year":"1997","journal-title":"Comput. Appl. Biosci."},{"key":"2023041109375267700_","first-page":"374","article-title":"Using multiple alignments to improve gene prediction","author":"Gross","year":"2005"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1089\/cmb.2006.13.379","article-title":"Using multiple alignments to improve gene prediction","volume":"13","author":"Gross","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1089\/cmb.1997.4.127","article-title":"Finding genes in DNA with a hidden Markov model","volume":"4","author":"Henderson","year":"1997","journal-title":"J. Comput. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Commun. ACM."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-011-5014-9","article-title":"North Atlantic Treaty Organization. Scientific Affairs Division","volume-title":"In Learning in Graphical Models","author":"Jordan","year":"1998"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-4149(96)00060-9","article-title":"Asymptotic filtering for finite state Markov chains","volume":"63","author":"Khasminskii","year":"1996","journal-title":"Stoch. Proc. Appl."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"S140","DOI":"10.1093\/bioinformatics\/17.suppl_1.S140","article-title":"Integrating genomic homology into gene structure prediction","volume":"17","author":"Korf","year":"2001","journal-title":"Bioinformatics"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","article-title":"Hidden Markov models in computational biology. Applications to protein modeling","volume":"235","author":"Krogh","year":"1994","journal-title":"J. Mol. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1006\/jmbi.2000.4315","article-title":"Predicting transmembrane protein topology with a hidden Markov model: application to complete genomes","volume":"305","author":"Krogh","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1038\/nature04338","article-title":"Genome sequence, comparative analysis and haplotype structure of the domestic dog","volume":"438","author":"Lindblad-Toh","year":"2005","journal-title":"Nature"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1093\/bioinformatics\/18.10.1309","article-title":"Comparative ab initio prediction of gene structures using pair HMMs","volume":"18","author":"Meyer","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041109375267700_","first-page":"11","article-title":"Optimal alignments in linear space","volume":"4","author":"Myers","year":"1988","journal-title":"Comput. Appl. Biosci."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1089\/10665270252935520","article-title":"Applications of generalized pair hidden markov models to alignment and gene finding problems","volume":"9","author":"Pachter","year":"2002","journal-title":"J. Comput. Biol."},{"key":"2023041109375267700_","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl","year":"1988"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"D501","DOI":"10.1093\/nar\/gki025","article-title":"NCBI Reference Sequence (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins","volume":"33","author":"Pruitt","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/5.18626","article-title":"A tutorial on hidden Markov models and selected applications in speech recognition","volume":"77","author":"Rabiner","year":"1989","journal-title":"Proc IEEE"},{"key":"2023041109375267700_","article-title":"On performance analysis of state estimators for hidden Markov models","volume-title":"Doctoral Dissertation","author":"Shue","year":"1999"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1093\/bioinformatics\/14.5.401","article-title":"Reduced space hidden Markov model training","volume":"14","author":"Tarnas","year":"1998","journal-title":"Bioinformatics"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TIT.1967.1054010","article-title":"Error bounds for convolution codes and an asymptotically optimum decoding algorithm","volume":"13","author":"Viterbi","year":"1967","journal-title":"IEEE T. Inform. Theory"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1093\/bioinformatics\/16.12.1082","article-title":"Optimizing reduced-space sequence analysis","volume":"16","author":"Wheeler","year":"2000","journal-title":"Bioinformatics"},{"key":"2023041109375267700_","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1101\/gr.1959604","article-title":"Identification of rat genes by TWINSCAN gene prediction, RT-PCR, and direct sequencing","volume":"14","author":"Wu","year":"2004","journal-title":"Genome Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/5\/545\/49829894\/bioinformatics_23_5_545.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/5\/545\/49829894\/bioinformatics_23_5_545.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T13:06:35Z","timestamp":1683723995000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/5\/545\/238397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,18]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl659","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,3]]},"published":{"date-parts":[[2007,1,18]]}}}