{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,14]],"date-time":"2026-11-14T11:02:26Z","timestamp":1794654146265,"version":"4.9.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T00:00:00Z","timestamp":1108425600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T00:00:00Z","timestamp":1108425600000},"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>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Exhaustive methods of sequence alignment are accurate but slow, whereas heuristic approaches run quickly, but their complexity makes them more difficult to implement. We introduce bounded sparse dynamic programming (BSDP) to allow rapid approximation to exhaustive alignment. This is used within a framework whereby the alignment algorithms are described in terms of their underlying model, to allow automated development of efficient heuristic implementations which may be applied to a general set of sequence comparison problems.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>This system allows rapid implementation of heuristics approximating to many complex alignment models, and has been incorporated into the freely available sequence alignment program, exonerate.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/1471-2105-6-31","type":"journal-article","created":{"date-parts":[[2005,2,16]],"date-time":"2005-02-16T02:25:21Z","timestamp":1108520721000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2802,"title":["Automated generation of heuristics for biological sequence comparison"],"prefix":"10.1186","volume":"6","author":[{"given":"Guy St C","family":"Slater","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ewan","family":"Birney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,2,15]]},"reference":[{"key":"356_CR1","volume-title":"Robustness in Statistics","author":"GE Box","year":"1979","unstructured":"Box GE: Robustness in the Strategy of Scientific Model Building. In Robustness in Statistics. Edited by: Launer R, Wilkinson G. Academic Press New York; 1979."},{"key":"356_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M: Identification of Common Molecular Subsequences. Journal of Molecular Biology 1981, 147: 195\u2013197.","journal-title":"Journal of Molecular Biology"},{"key":"356_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic Local Alignment Search Tool. Journal of Molecular Biology 1990, 215: 403\u2013410.","journal-title":"Journal of Molecular Biology"},{"key":"356_CR4","first-page":"341","volume-title":"Proceedings of the Third International Conference On Intelligent Systems for Molecular Biology","author":"DB Searls","year":"1995","unstructured":"Searls DB, Murphy KP: Automata-Theoretic Models of Mutation and Alignment. In Proceedings of the Third International Conference On Intelligent Systems for Molecular Biology. The AAAI Press; 1995:341\u2013349."},{"key":"356_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0168-9525(96)81387-4","volume":"12","author":"DB Searls","year":"1996","unstructured":"Searls DB: Sequence alignment through pictures. Trends in Genetics 1996, 12: 35\u201337.","journal-title":"Trends in Genetics"},{"key":"356_CR6","first-page":"56","volume-title":"Proceedings of the Fifth International Conference On Intelligent Systems for Molecular Biology","author":"E Birney","year":"1997","unstructured":"Birney E, Durbin R: Dynamite: A flexible code generating language for dynamic programming methods used in sequence comparison. In Proceedings of the Fifth International Conference On Intelligent Systems for Molecular Biology. The AAAI Press; 1997:56\u201364."},{"key":"356_CR7","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O: An Improved Algorithm for Matching Biological Sequences. Journal of Molecular Biology 1982, 162: 705\u2013708.","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"356_CR8","first-page":"477","volume":"13","author":"R Mott","year":"1997","unstructured":"Mott R: EST_GENOME: a program to align spliced DNA sequences to unspliced genomic DNA. CABIOS 1997, 13(4):477\u2013478.","journal-title":"CABIOS"},{"key":"356_CR9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/(SICI)1097-0134(19980701)32:1<88::AID-PROT10>3.0.CO;2-J","volume":"32","author":"SF Altschul","year":"1998","unstructured":"Altschul SF: Generalized Affine Gap Costs for Protein Sequence Alignment. PROTEINS: Structure, Function and Genetics 1998, 32: 88\u201396.","journal-title":"PROTEINS: Structure, Function and Genetics"},{"key":"356_CR10","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1101\/gr.9.9.815","volume":"9","author":"N Jareborg","year":"1999","unstructured":"Jareborg N, Birney E, Durbin R: Comparative Analysis of Noncoding Regions of 77 Orthologous Mouse and Human Gene Pairs. Genome Research 1999, 9: 815\u2013824.","journal-title":"Genome Research"},{"issue":"14","key":"356_CR11","doi-asserted-by":"publisher","first-page":"2730","DOI":"10.1093\/nar\/24.14.2730","volume":"24","author":"E Birney","year":"1996","unstructured":"Birney E, Thompson JD, Gibson TJ: PairWise and SearchWise: finding the optimal alignment in a simultaneous comparison of a protein profile against all DNA translation frames. Nucleic Acids Research 1996, 24(14):2730\u20132739.","journal-title":"Nucleic Acids Research"},{"issue":"5","key":"356_CR12","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1101\/gr.1865504","volume":"14","author":"E Birney","year":"2004","unstructured":"Birney E, Clamp M, Durbin R: GeneWise and Genomewise. Genome Research 2004, 14(5):988\u2013995.","journal-title":"Genome Research"},{"key":"356_CR13","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1101\/gr.6.8.653","volume":"6","author":"RF Smith","year":"1996","unstructured":"Smith RF: Perspectives: Sequence Data Base Searching in the Era of Large-scale Genomic Sequencing. Genome Research 1996, 6: 653\u2013660.","journal-title":"Genome Research"},{"key":"356_CR14","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1126\/science.2983426","volume":"277","author":"DJ Lipman","year":"1985","unstructured":"Lipman DJ, Pearson WR: Rapid and Sensitive Protein Similarity Searches. Science 1985, 277: 1435\u20131441.","journal-title":"Science"},{"key":"356_CR15","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1101\/gr.8.9.967","volume":"8","author":"L Florea","year":"1998","unstructured":"Florea L, Hartzell G, Zhang Z, Rubin GM, Miller W: A Computer Program for Aligning a cDNA Sequence with a Genomic DNA Sequence. Genome Research 1998, 8: 967\u2013974.","journal-title":"Genome Research"},{"issue":"10","key":"356_CR16","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1101\/gr.194201","volume":"11","author":"Z Ning","year":"2001","unstructured":"Ning Z, Cox AJ, Mullikin JC: SSAHA: A Fast Search Method for Large DNA Databases. Genome Research 2001, 11(10):1725\u20131729.","journal-title":"Genome Research"},{"key":"356_CR17","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/299432.299460","volume-title":"Proceedings of the Third Annual International Conference on Computational Molecular Biology","author":"S Burkhardt","year":"1999","unstructured":"Burkhardt S, Crauser A, Ferragina P, Lenhof HP, Rivals E, Vingron M: q -gram Based Database Searching Using a Suffix Array (QUASAR). In Proceedings of the Third Annual International Conference on Computational Molecular Biology. The ACM Press; 1999:77\u201383."},{"issue":"5","key":"356_CR18","first-page":"481","volume":"8","author":"KM Chao","year":"1992","unstructured":"Chao KM, Pearson WR, Miller W: Aligning two sequences within a specified diagonal band. CABIOS 1992, 8(5):481\u2013487.","journal-title":"CABIOS"},{"issue":"17","key":"356_CR19","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"SF Altschul","year":"1997","unstructured":"Altschul SF, Madden TL, Sch\u00e4ffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research 1997, 25(17):3389\u20133402.","journal-title":"Nucleic Acids Research"},{"issue":"6","key":"356_CR20","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho AV, Corasick MJ: Efficient String Matching: An Aid to Bibiographic Search. Communications of the ACM 1975, 18(6):333\u2013340.","journal-title":"Communications of the ACM"},{"issue":"11","key":"356_CR21","doi-asserted-by":"publisher","first-page":"1052","DOI":"10.1093\/bioinformatics\/16.11.1052","volume":"16","author":"I Korf","year":"2000","unstructured":"Korf I, Gish W: MPBLAST: improved BLAST performance with multiplexed queries. Bioinformatics 2000, 16(11):1052\u20131053.","journal-title":"Bioinformatics"},{"key":"356_CR22","first-page":"513","volume-title":"Proc 1st Symp Discrete Algorithms","author":"D Eppstein","year":"1990","unstructured":"Eppstein D, Galil Z, Giancarlo R, Italiano GF: Sparse Dynamic Programming. In Proc 1st Symp Discrete Algorithms. ACM and SIAM; 1990:513\u2013522."},{"issue":"2","key":"356_CR23","first-page":"147","volume":"11","author":"KM Chao","year":"1995","unstructured":"Chao KM, Zhang J, Ostell J, Miller W: A local alignment tool for very long DNA sequences. CABIOS 1995, 11(2):147\u2013153.","journal-title":"CABIOS"},{"key":"356_CR24","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","volume":"197","author":"MS Waterman","year":"1987","unstructured":"Waterman MS, Eggert M: A New Algorithm for Best Subsequence Alignments with Application to tRNA-rRNA Comparisons. Journal of Molecular Biology 1987, 197: 723\u2013728.","journal-title":"Journal of Molecular Biology"},{"key":"356_CR25","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1101\/gr.1858004","volume":"14","author":"V Curwen","year":"2004","unstructured":"Curwen V, Eyras E, Andrews TD, Clarke L, Mongin E, Searle SM, Clamp M: The Ensembl Automatic Gene Annotation System. Genome Research 2004, 14: 942\u2013950.","journal-title":"Genome Research"},{"key":"356_CR26","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1038\/414865a","volume":"414","author":"P Deloukas","year":"2001","unstructured":"Deloukas P, Matthews LH, Ashurst J, Burton J, Gilbert JGR, Jones M, Stavrides G, Almeida JP, Babbage AK, Bagguley CL, Bailey J, Barlow KF, Bates KN, Beard LM, Beare DM, Beasley OP, Bird CP, Blakey SE, Bridgeman AM, Brown AJ, Buck D, Burrill W, Butler AP, Carder C, Carter NP, Chapman JC, Clamp M, Clark G, Clark LN, Clark SY, Clee CM, Clegg S, Cobley VE, Collier RE, Connor R, Corby NR, Coulson A, Coville GJ, Dead-man R, Dhami P, Dunn M, Ellington AG, Frankland JA, Fraser A, French L, Garner P, Grafham DV, Griffiths C, Griffiths MND, Gwilliam R, Hall RE, Hammond S, Harley JL, Heath PD, Ho S, Holden JL, Howden PJ, Huckle E, Hunt AR, Hunt SE, Jekosch K, Johnson CM, Johnson D, Kay MP, Kimberley AM, King A, Knights A, Laird GK, Lawlor S, Lehvaslaiho MH, Leversha M, Lloyd C, Lloyd DM, Lovell JD, Marsh VL, Martin SL, McConnachie LJ, McLay K, McMurray AA, Milne S, Mistry D, Moore MJF, Mullikin JC, Nickerson T, Oliver K, Parker A, Patel R, Pearce TAV, Peck AI, Phillimore BJCT, Prathalingam SR, Plumb RW, Ramsay H, Rice CM, Ross MT, Scott CE, Sehra HK, Shownkeen R, Sims S, Skuce CD, Smith ML, Soderlund C, Steward CA, Sulston JE, Swann M, Sycamore N, Taylor R, Tee L, Thomas DW, Thorpe A, Tracey A, Tromans AC, Vaudin M, Wall M, Wallis JM, Whitehead SL, Whittaker P, Willey DL, Williams L, Williams SA, Wilming L, Wray PW, Hubbard T, Durbin RM, Bentley DR, Beck S, Rogers J: The DNA sequence and comparative analysis of human chromosome 20. Nature 2001, 414: 865\u2013871.","journal-title":"Nature"},{"issue":"4","key":"356_CR27","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1093\/bioinformatics\/16.4.334","volume":"16","author":"E Rivas","year":"2000","unstructured":"Rivas E, Eddy SR: The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics 2000, 16(4):334\u2013340.","journal-title":"Bioinformatics"},{"issue":"3","key":"356_CR28","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1093\/nar\/21.3.607","volume":"21","author":"EE Snyder","year":"1993","unstructured":"Snyder EE, Stormo GD: Identification of coding regions in genomic DNA sequences: an application of dynamic programming and neural networks. Nucleic Acids Research 1993, 21(3):607\u2013613.","journal-title":"Nucleic Acids Research"},{"issue":"11","key":"356_CR29","doi-asserted-by":"publisher","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"AL Delcher","year":"1999","unstructured":"Delcher AL, Kasif S, Fleischmann RD, Peterson J, White O, Salzberg SL: Alignment of whole genomes. Nucleic Acids Research 1999, 27(11):2369\u20132376.","journal-title":"Nucleic Acids Research"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-31.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-31\/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-31.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T08:06:12Z","timestamp":1728288372000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2,15]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["356"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-31","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2,15]]},"assertion":[{"value":"15 September 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"31"}}