{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,4]],"date-time":"2026-11-04T20:53:24Z","timestamp":1793825604816,"version":"4.6.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,1,24]],"date-time":"2005-01-24T00:00:00Z","timestamp":1106524800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,1,24]],"date-time":"2005-01-24T00:00:00Z","timestamp":1106524800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>The Generalized Hidden Markov Model (GHMM) has proven a useful framework for the task of computational gene prediction in eukaryotic genomes, due to its flexibility and probabilistic underpinnings. As the focus of the gene finding community shifts toward the use of homology information to improve prediction accuracy, extensions to the basic GHMM model are being explored as possible ways to integrate this homology information into the prediction process. Particularly prominent among these extensions are those techniques which call for the simultaneous prediction of genes in two or more genomes at once, thereby increasing significantly the computational cost of prediction and highlighting the importance of speed and memory efficiency in the implementation of the underlying GHMM algorithms. Unfortunately, the task of implementing an efficient GHMM-based gene finder is already a nontrivial one, and it can be expected that this task will only grow more onerous as our models increase in complexity.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>As a first step toward addressing the implementation challenges of these next-generation systems, we describe in detail two software architectures for GHMM-based gene finders, one comprising the common array-based approach, and the other a highly optimized algorithm which requires significantly less memory while achieving virtually identical speed. We then show how both of these architectures can be accelerated by a factor of two by optimizing their content sensors. We finish with a brief illustration of the impact these optimizations have had on the feasibility of our new homology-based gene finder, TWAIN.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusions<\/jats:title>\n                        <jats:p>In describing a number of optimizations for GHMM-based gene finders and making available two complete open-source software systems embodying these methods, it is our hope that others will be more enabled to explore promising extensions to the GHMM framework, thereby improving the state-of-the-art in gene prediction techniques.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-16","type":"journal-article","created":{"date-parts":[[2005,1,25]],"date-time":"2005-01-25T09:11:28Z","timestamp":1106644288000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Efficient decoding algorithms for generalized hidden Markov model gene finders"],"prefix":"10.1186","volume":"6","author":[{"given":"William H","family":"Majoros","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihaela","family":"Pertea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arthur L","family":"Delcher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven L","family":"Salzberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,1,24]]},"reference":[{"key":"341_CR1","first-page":"134","volume":"4","author":"D Kulp","year":"1996","unstructured":"Kulp D, Haussler D, Reese MG, Eeckman FH: A generalized hidden Markov model for the recognition of human genes in DNA. Proc Int Con Intell Syst Mol Biol 1996, 4: 134\u2013142.","journal-title":"Proc Int Con Intell Syst Mol Biol"},{"key":"341_CR2","volume-title":"PhD Thesis","author":"C Burge","year":"1997","unstructured":"Burge C: Identification of Genes in Human Genomic DNA. In PhD Thesis. Department of Mathematics, Stanford University; 1997."},{"key":"341_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0166-6851(01)00363-2","volume":"118","author":"SE Cawley","year":"2001","unstructured":"Cawley SE, Wirth AI, Speed TP: Phat \u2013 a gene finding program for Plasmodium falciparum . Mol Biochem Parasitol 2001, 118: 167\u2013174. 10.1016\/S0166-6851(01)00363-2","journal-title":"Mol Biochem Parasitol"},{"key":"341_CR4","doi-asserted-by":"publisher","first-page":"II215","DOI":"10.1093\/bioinformatics\/btg1080","volume":"19","author":"M Stanke","year":"2003","unstructured":"Stanke M, Waack S: Gene prediction with a hidden Markov model and a new intron submodel. Bioinformatics 2003, 19: II215-II225. 10.1093\/bioinformatics\/btg1080","journal-title":"Bioinformatics"},{"key":"341_CR5","doi-asserted-by":"publisher","first-page":"2878","DOI":"10.1093\/bioinformatics\/bth315","volume":"20","author":"WM Majoros","year":"2004","unstructured":"Majoros WM, Pertea M, Salzberg SL: TIGRscan and GlimmerHMM: two open-source ab initio eukaryotic gene finders. Bioinformatics 2004, 20: 2878\u20132879. 10.1093\/bioinformatics\/bth315","journal-title":"Bioinformatics"},{"key":"341_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1186\/1471-2105-5-59","volume":"5","author":"I Korf","year":"2004","unstructured":"Korf I: Gene finding in novel genomes. BMC Bioinf 2004, 5: 59. 10.1186\/1471-2105-5-59","journal-title":"BMC Bioinf"},{"key":"341_CR7","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1089\/10665270252935520","volume":"9","author":"L Pachter","year":"2002","unstructured":"Pachter L, Alexandersson M, Cawley S: Applications of generalized pair hidden Markov models to alignment and gene finding problems. J Comput Biol 2002, 9: 389\u2013399. 10.1089\/10665270252935520","journal-title":"J Comput Biol"},{"key":"341_CR8","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1101\/gr.424203","volume":"13","author":"M Alexandersson","year":"2003","unstructured":"Alexandersson M, Cawley S, Pachter L: SLAM: Cross-species gene finding and alignment with a generalized pair hidden Markov model. Genome Res 2003, 13: 496\u2013502. 10.1101\/gr.424203","journal-title":"Genome Res"},{"key":"341_CR9","first-page":"4","volume":"3","author":"LR Rabiner","year":"1986","unstructured":"Rabiner LR, Juang B-H: An introduction to hidden Markov models. IEEE Transactions on Acoustics Speech, Signal Processing 1986, 3: 4\u201316.","journal-title":"IEEE Transactions on Acoustics Speech, Signal Processing"},{"key":"341_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/5.18626","volume":"77","author":"LR Rabiner","year":"1989","unstructured":"Rabiner LR: A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 1989, 77: 257\u2013286. 10.1109\/5.18626","journal-title":"Proceedings of the IEEE"},{"key":"341_CR11","volume-title":"Computational Methods in Molecular Biology","author":"SL Salzberg","year":"1998","unstructured":"Salzberg SL, Searls DB, Kasif S: Computational Methods in Molecular Biology. Amsterdam: Elsevier; 1998."},{"key":"341_CR12","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":"341_CR13","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","volume":"268","author":"C Burge","year":"1997","unstructured":"Burge C, Karlin S: Prediction of complete gene structures in human genomic DNA. J Mol Biol 1997, 268: 78\u201394. 10.1006\/jmbi.1997.0951","journal-title":"J Mol Biol"},{"key":"341_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/geno.1999.5854","volume":"59","author":"SL Salzberg","year":"1999","unstructured":"Salzberg SL, Pertea M, Delcher AL, Gardner MJ, Tettelin H: Interpolated Markov models for eukaryotic gene finding. Genomics 1999, 59: 24\u201331. 10.1006\/geno.1999.5854","journal-title":"Genomics"},{"key":"341_CR15","volume-title":"Bioinformatics","author":"WM Majoros","year":"2005","unstructured":"Majoros WM, Pertea M, Salzberg SL: Efficient implementation of a centralized Pair. Hidden Markov Model for comparative gene finding. Bioinformatics 2005, in press."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-16.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-16\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-16.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:04:49Z","timestamp":1728302689000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1,24]]},"references-count":15,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["341"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-16","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1,24]]},"assertion":[{"value":"15 November 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}