{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:26:52Z","timestamp":1773149212189,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,3,22]],"date-time":"2005-03-22T00:00:00Z","timestamp":1111449600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,3,22]],"date-time":"2005-03-22T00:00:00Z","timestamp":1111449600000},"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>We present a complete re-implementation of the segment-based approach to multiple protein alignment that contains a number of improvements compared to the previous version 2.2 of <jats:italic>DIALIGN<\/jats:italic>. This previous version is superior to Needleman-Wunsch-based multi-alignment programs on <jats:italic>locally<\/jats:italic> related sequence sets. However, it is often outperformed by these methods on data sets with <jats:italic>global<\/jats:italic> but weak similarity at the primary-sequence level.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>In the present paper, we discuss strengths and weaknesses of DIALIGN in view of the underlying <jats:italic>objective function<\/jats:italic>. Based on these results, we propose several heuristics to improve the segment-based alignment approach. For pairwise alignment, we implemented a fragment-chaining algorithm that favours chains of low-scoring local alignments over isolated high-scoring fragments. For multiple alignment, we use an improved <jats:italic>greedy<\/jats:italic> procedure that is less sensitive to spurious local sequence similarities. To evaluate our method on globally related protein families, we used the well-known database <jats:italic>BAliBASE<\/jats:italic>. For benchmarking tests on locally related sequences, we created a new reference database called <jats:italic>IRMBASE<\/jats:italic> which consists of simulated conserved motifs implanted into non-related random sequences.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>On BAliBASE, our new program performs significantly better than the previous version of DIALIGN and is comparable to the standard global aligner CLUSTAL W, though it is outperformed by some newly developed programs that focus on global alignment. On the locally related test sets in IRMBASE, our method outperforms all other programs that we evaluated.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-66","type":"journal-article","created":{"date-parts":[[2005,3,23]],"date-time":"2005-03-23T07:16:08Z","timestamp":1111562168000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":102,"title":["DIALIGN-T: An improved algorithm for segment-based multiple sequence alignment"],"prefix":"10.1186","volume":"6","author":[{"given":"Amarendran R","family":"Subramanian","sequence":"first","affiliation":[]},{"given":"Jan","family":"Weyer-Menkhoff","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,3,22]]},"reference":[{"key":"391_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45727-5_1","volume":"2066","author":"S Abdedda\u00efm","year":"2001","unstructured":"Abdedda\u00efm S, Morgenstern B: Speeding up the DIALIGN multiple alignment program by using the 'greedy alignment of biological sequences library' (GABIOS-LIB). Lecture Notes in Computer Science 2001, 2066: 1\u201311.","journal-title":"Lecture Notes in Computer Science"},{"key":"391_CR2","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1186\/1471-2105-4-66","volume":"4","author":"M Brudno","year":"2003","unstructured":"Brudno M, Chapman M, G\u00f6ttgens B, Batzoglou S, Morgenstern B: Fast and sensitive multiple alignment of large genomic sequences. BMC Bioinformatics 2003, 4: 66. [http:\/\/www.biomedcentral.com\/1471\u20132105\/4\/66] 10.1186\/1471-2105-4-66","journal-title":"BMC Bioinformatics"},{"key":"391_CR3","doi-asserted-by":"crossref","unstructured":"Brudno M, Malde S, Poliakov A, Do CB, Couronne O, Dubchak I, Batzoglou S: Glocal alignment: finding rearrangements during alignment. Bioinformatics 2003, (Suppl 1):i54-i62. 10.1093\/bioinformatics\/btg1005","DOI":"10.1093\/bioinformatics\/btg1005"},{"key":"391_CR4","doi-asserted-by":"publisher","first-page":"10881","DOI":"10.1093\/nar\/16.22.10881","volume":"16","author":"F Corpet","year":"1988","unstructured":"Corpet F: Multiple sequence alignment with hierarchical clustering. Nucleic Acids Res 1988, 16: 10881\u201310890.","journal-title":"Nucleic Acids Res"},{"key":"391_CR5","first-page":"501","volume":"8","author":"E Depiereux","year":"1992","unstructured":"Depiereux E, Feytmans E: Match-box: a fundamentally new algorithm for the simultaneous alignment of several protein sequences. CABIOS 1992, 8: 501\u2013509.","journal-title":"CABIOS"},{"key":"391_CR6","first-page":"703","volume-title":"Proceedings Nineteenth National Conference on Artificial Intelligence","author":"C Do","year":"2004","unstructured":"Do C, Brudno M, Batzoglou S: ProbCons: probabilistic consistency-based multiple alignment of amino acid sequences. Proceedings Nineteenth National Conference on Artificial Intelligence 2004, 703\u2013708."},{"key":"391_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy SR, Krogh A, Mitchison G: Biological sequence analysis. Cambridge University Press, Cambridge, UK; 1998."},{"key":"391_CR8","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"R Edgar","year":"2004","unstructured":"Edgar R: MUSCLE: Multiple sequence alignment with high score accuracy and high throughput. Nuc Acids Res 2004, 32: 1792\u20131797. 10.1093\/nar\/gkh340","journal-title":"Nuc Acids Res"},{"key":"391_CR9","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1006\/jmbi.1996.0679","volume":"264","author":"O Gotoh","year":"1996","unstructured":"Gotoh O: Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. J Mol Biol 1996, 264: 823\u2013838. 10.1006\/jmbi.1996.0679","journal-title":"J Mol Biol"},{"key":"391_CR10","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1101\/gr.122800","volume":"10","author":"R Guig\u00f3","year":"2002","unstructured":"Guig\u00f3 R, Agarwal P, Abril JF, Burset M, Fickett JW: An assessment of gene prediction accuracy in large DNA sequences. Genome Research 2002, 10: 1631\u20131642. 10.1101\/gr.122800","journal-title":"Genome Research"},{"key":"391_CR11","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/S0014-5793(02)03189-7","volume":"529","author":"T Lassmann","year":"2002","unstructured":"Lassmann T, Sonnhammer EL: Quality assessment of multiple alignment programs. FEBS Letters 2002, 529: 126\u2013130. 10.1016\/S0014-5793(02)03189-7","journal-title":"FEBS Letters"},{"issue":"5131","key":"391_CR12","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1126\/science.8211139","volume":"262","author":"CE Lawrence","year":"1993","unstructured":"Lawrence CE, Altschul SF, Boguski MS, Liu JS, Neuwald AF, Wootton JC: Detecting subtle sequence signals: a gibbs sampling strategy for multiple alignment. Science 1993, 262(5131):208\u201314.","journal-title":"Science"},{"issue":"3","key":"391_CR13","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C Lee","year":"2002","unstructured":"Lee C, Grasso C, Sharlow MF: Multiple sequence alignment using partial order graphs. Bioinformatics 2002, 18(3):452\u2013464. 10.1093\/bioinformatics\/18.3.452","journal-title":"Bioinformatics"},{"key":"391_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","volume":"15","author":"B Morgenstern","year":"1999","unstructured":"Morgenstern B: DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics 1999, 15: 211\u2013218. 10.1093\/bioinformatics\/15.3.211","journal-title":"Bioinformatics"},{"key":"391_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0893-9659(01)00085-4","volume":"15","author":"B Morgenstern","year":"2002","unstructured":"Morgenstern B: A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences. Applied Mathematics Letters 2002, 15: 11\u201316. 10.1016\/S0893-9659(01)00085-4","journal-title":"Applied Mathematics Letters"},{"key":"391_CR16","doi-asserted-by":"publisher","first-page":"W33","DOI":"10.1093\/nar\/gkh373","volume":"32","author":"B Morgenstern","year":"2004","unstructured":"Morgenstern B: DIALIGN: Multiple DNA and protein sequence alignment at BiBiServ. Nucleic Acids Research 2004, 32: W33-W36. 10.1093\/nar\/gnh029","journal-title":"Nucleic Acids Research"},{"key":"391_CR17","doi-asserted-by":"publisher","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","volume":"93","author":"B Morgenstern","year":"1996","unstructured":"Morgenstern B, Dress A, Werner T: Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc Natl Acad Sci USA 1996, 93: 12098\u201312103. 10.1073\/pnas.93.22.12098","journal-title":"Proc Natl Acad Sci USA"},{"key":"391_CR18","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 1970, 48: 443\u2013453. 10.1016\/0022-2836(70)90057-4","journal-title":"J Mol Biol"},{"key":"391_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins D, Heringa J: T-Coffee: a novel algorithm for multiple sequence alignment. J Mol Biol 2000, 302: 205\u2013217. 10.1006\/jmbi.2000.4042","journal-title":"J Mol Biol"},{"key":"391_CR20","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1186\/1471-2105-5-6","volume":"5","author":"DA Pollard","year":"2004","unstructured":"Pollard DA, Bergman CM, Stoye J, Celniker SE, Eisen MB: Benchmarking tools for the alignment of functional noncoding DNA. BMC Bioinformatics 2004, 5: 6. [http:\/\/www.biomedcentral.com\/1471\u20132105\/5\/6] 10.1186\/1471-2105-5-6","journal-title":"BMC Bioinformatics"},{"key":"391_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1186\/1471-2105-4-47","volume":"4","author":"G Raghava","year":"2003","unstructured":"Raghava G, Searle SM, Audley PC, Barber JD, Barton GJ: OXBench: A benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics 2003, 4: 47. 10.1186\/1471-2105-4-47","journal-title":"BMC Bioinformatics"},{"key":"391_CR22","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1101\/gr.2657504","volume":"14","author":"B Raphael","year":"2004","unstructured":"Raphael B, Zhi D, Tang H, Pevzner P: A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Research 2004, 14: 2336\u20132346. 10.1101\/gr.2657504","journal-title":"Genome Research"},{"key":"391_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1093\/bioinformatics\/14.2.157","volume":"14","author":"J Stoye","year":"1998","unstructured":"Stoye J, Evers D, Meyer F: Rose: Generating sequence families. Bioinformatics 1998, 14: 157\u2013163. 10.1093\/bioinformatics\/14.2.157","journal-title":"Bioinformatics"},{"key":"391_CR24","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research 1994, 22: 4673\u20134680.","journal-title":"Nucleic Acids Research"},{"key":"391_CR25","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","volume":"15","author":"JD Thompson","year":"1999","unstructured":"Thompson JD, Plewniak F, Poch O: BAliBASE: A benchmark alignment database for the evaluation of multiple sequence alignment programs. Bioinformatics 1999, 15: 87\u201388. 10.1093\/bioinformatics\/15.1.87","journal-title":"Bioinformatics"},{"key":"391_CR26","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","volume":"27","author":"JD Thompson","year":"1999","unstructured":"Thompson JD, Plewniak F, Poch O: A comprehensive comparison of protein sequence alignment programs. Nucleic Acids Research 1999, 27: 2682\u20132690. 10.1093\/nar\/27.13.2682","journal-title":"Nucleic Acids Research"},{"key":"391_CR27","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1093\/bioinformatics\/bth116","volume":"20","author":"IV Walle","year":"2004","unstructured":"Walle IV, Lasters I, Wyns L: Align-m \u2013 a new algorithm for multiple alignment of highly divergent sequences. Bioinformatics 2004, 20: 1428\u20131435. 10.1093\/bioinformatics\/bth116","journal-title":"Bioinformatics"},{"key":"391_CR28","doi-asserted-by":"crossref","unstructured":"Walle IV, Lasters I, Wyns L: SABmark \u2013 a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics, in press. doi: 10.1093\/bioinformatics\/bth493.","DOI":"10.1093\/bioinformatics\/bth493"},{"key":"391_CR29","doi-asserted-by":"publisher","first-page":"9095","DOI":"10.1093\/nar\/14.22.9095","volume":"14","author":"MS Waterman","year":"1986","unstructured":"Waterman MS: Multiple sequence alignment by consensus. Nucleic Acids Res 1986, 14: 9095\u20139102.","journal-title":"Nucleic Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-66.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-66\/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-66.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:08:34Z","timestamp":1728302914000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3,22]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["391"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-66","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3,22]]},"assertion":[{"value":"1 November 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"66"}}