{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T03:26:44Z","timestamp":1764905204804},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2004,9,9]],"date-time":"2004-09-09T00:00:00Z","timestamp":1094688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2004,9,9]],"date-time":"2004-09-09T00:00:00Z","timestamp":1094688000000},"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>Parallel computing is frequently used to speed up computationally expensive tasks in Bioinformatics.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>Herein, a parallel version of the multi-alignment program DIALIGN is introduced. We propose two ways of dividing the program into independent sub-routines that can be run on different processors: (<jats:italic>a<\/jats:italic>) pair-wise sequence alignments that are used as a first step to multiple alignment account for most of the CPU time in DIALIGN. Since alignments of different sequence pairs are completely independent of each other, they can be distributed to multiple processors without any effect on the resulting output alignments. (<jats:italic>b<\/jats:italic>) For alignments of large genomic sequences, we use a heuristics by splitting up sequences into sub-sequences based on a previously introduced <jats:italic>anchored alignment<\/jats:italic> procedure. For our test sequences, this combined approach reduces the program running time of DIALIGN by up to 97%.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusions<\/jats:title>\n                        <jats:p>By distributing sub-routines to multiple processors, the running time of DIALIGN can be crucially improved. With these improvements, it is possible to apply the program in large-scale genomics and proteomics projects that were previously beyond its scope.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-5-128","type":"journal-article","created":{"date-parts":[[2004,9,15]],"date-time":"2004-09-15T08:32:40Z","timestamp":1095237160000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["DIALIGN P: Fast pair-wise and multiple sequence alignment using parallel processors"],"prefix":"10.1186","volume":"5","author":[{"given":"Martin","family":"Schmollinger","sequence":"first","affiliation":[]},{"given":"Kay","family":"Nieselt","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,9,9]]},"reference":[{"key":"244_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1517\/14622416.3.1.131","volume":"3","author":"C Notredame","year":"2002","unstructured":"Notredame C: Recent progress in multiple sequence alignment: a survey.\n                           Pharmacogenomics 2002, 3: 131\u2013144.","journal-title":"Pharmacogenomics"},{"key":"244_CR2","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.\n                           FEBS Letters 2002, 529: 126\u2013130. 10.1016\/S0014-5793(02)03189-7","journal-title":"FEBS Letters"},{"key":"244_CR3","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.\n                           BMC Bioinformatics 2004, 5: 6. [http:\/\/www.biomedcentral.com\/1471\u20132105\/5\/6] 10.1186\/1471-2105-5-6","journal-title":"BMC Bioinformatics"},{"key":"244_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1093\/bib\/4.2.105","volume":"4","author":"P Chain","year":"2003","unstructured":"Chain P, Kurtz S, Ohlebusch E, Slezak T: An applications-focused review of comparative genomics tools: capabilities, limitations, and future challenges.\n                           Briefings in Bioinformatics 2003, 4: 105\u2013123.","journal-title":"Briefings in Bioinformatics"},{"key":"244_CR5","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1093\/bioinformatics\/17.5.391","volume":"17","author":"W Miller","year":"2001","unstructured":"Miller W: Comparison of genomic DNA sequences: solved and unsolved problems.\n                           Bioinformatics 2001, 17: 391\u2013397. 10.1093\/bioinformatics\/17.5.391","journal-title":"Bioinformatics"},{"key":"244_CR6","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1093\/nar\/26.2.544","volume":"26","author":"SL Salzberg","year":"1998","unstructured":"Salzberg SL, Delcher AL, Kasif S, White O: Microbial gene identification using interpolated Markov models.\n                           Nucleic Acids Research 1998, 26: 544\u2013548. 10.1093\/nar\/26.2.544","journal-title":"Nucleic Acids Research"},{"key":"244_CR7","doi-asserted-by":"publisher","first-page":"S312","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312","volume":"18 Suppl 1","author":"M Hohl","year":"2002","unstructured":"Hohl M, Kurtz S, Ohlebusch E: Efficient multiple genome alignment.\n                           Bioinformatics 2002, 18 Suppl 1: S312-S320.","journal-title":"Bioinformatics"},{"key":"244_CR8","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.\n                           Bioinformatics 1999, 15: 211\u2013218. 10.1093\/bioinformatics\/15.3.211","journal-title":"Bioinformatics"},{"key":"244_CR9","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1093\/bioinformatics\/18.6.777","volume":"18","author":"B Morgenstern","year":"2002","unstructured":"Morgenstern B, Rinner O, Abdedda\u00efm S, Haase D, Mayer K, Dress A, Mewes HW: Exon Discovery by Genomic Sequence Alignment.\n                           Bioinformatics 2002, 18: 777\u2013787. 10.1093\/bioinformatics\/18.6.777","journal-title":"Bioinformatics"},{"key":"244_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1038\/72635","volume":"18","author":"B G\u00f6ttgens","year":"2000","unstructured":"G\u00f6ttgens B, Barton L, Gilbert J, Bench A, Sanchez M, Bahn S, Mistry S, Grafham D, McMurray A, Vaudin M, Amaya E, Bentley D, Green A: Analysis of vertebrate SCL loci identifies conserved enhancers.\n                           Nature Biotechnology 2000, 18: 181\u2013186. 10.1038\/72635","journal-title":"Nature Biotechnology"},{"key":"244_CR11","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1101\/gr.153001","volume":"11","author":"B G\u00f6ttgens","year":"2001","unstructured":"G\u00f6ttgens B, Gilbert J, Barton L, Grafham D, Rogers J, Bentley D, Green A: Long-range comparison of human and mouse SCL loci: localized regions of sensitivity to restriction endonucleases correspond precisely with peaks of conserved noncoding sequences.\n                           Genome Res 2001, 11: 87\u201397. 10.1101\/gr.153001","journal-title":"Genome Res"},{"key":"244_CR12","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1101\/gr.45502","volume":"12","author":"B G\u00f6ttgens","year":"2002","unstructured":"G\u00f6ttgens B, Barton L, Chapman M, Sinclair A, Knudsen B, Grafham D, Gilbert J, Rogers J, Bentley D, Green A: Transcriptional regulation of the Stem Cell Leukemia gene (SCL) Comparative analysis of five vertebrate SCL loci.\n                           Genome Res 2002, 12: 749\u2013759. 10.1101\/gr.45502","journal-title":"Genome Res"},{"key":"244_CR13","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1105\/tpc.010181","volume":"15","author":"H Guo","year":"2003","unstructured":"Guo H, Moose SP: Conserved noncoding sequences among cultivated cereal genomes identify candidate regulatory sequence elements and patterns of promoter evolution.\n                           Plant Cell 2003, 15: 1143\u20131158. 10.1105\/tpc.010181","journal-title":"Plant Cell"},{"key":"244_CR14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0888-7543(03)00005-3","volume":"81","author":"MA Chapman","year":"2003","unstructured":"Chapman MA, Charchar FJ, Kinston S, Bird CP, Grafham D, Rogers J, Gr\u00fctzner F, Graves JAM, Green AR, G\u00f6ttgens B: Comparative and functional analysis of LYL1 loci establish marsupial sequences as a model for phylogenetic footprinting.\n                           Genomics 2003, 81: 249\u2013259. 10.1016\/S0888-7543(03)00005-3","journal-title":"Genomics"},{"key":"244_CR15","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/j.ympev.2003.08.009","volume":"31","author":"S Prohaska","year":"2004","unstructured":"Prohaska S, Fried C, Flamm C, Wagner GP, Stadler PF: Surveying Phylogenetic Footprints in Large Gene Clusters: Applications to Hox Cluster Duplications.\n                           Mol Evol Phylog 2004, 31: 581\u2013604. 10.1016\/j.ympev.2003.08.009","journal-title":"Mol Evol Phylog"},{"key":"244_CR16","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1002\/jez.b.37","volume":"299B","author":"C Fried","year":"2003","unstructured":"Fried C, Prohaska S, Stadler P: Independent Hox-cluster duplications in lampreys.\n                           J EXP ZOOL PART B 2003, 299B: 18\u201325. 10.1002\/jez.b.37","journal-title":"J EXP ZOOL PART B"},{"key":"244_CR17","doi-asserted-by":"publisher","first-page":"1708","DOI":"10.1109\/JPROC.2002.804680","volume":"90","author":"J Fitch","year":"2002","unstructured":"Fitch J, Gardner S, Kuczmarski T, Kurtz S, Myers R, Ott L, Slezak T, Vitalis E, Zemla A, McCready P: Rapid Development of Nucleic Acid Diagnostics.\n                           Proceedings of the IEEE 2002, 90: 1708\u20131721. 10.1109\/JPROC.2002.804680","journal-title":"Proceedings of the IEEE"},{"key":"244_CR18","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.\n                           BMC Bioinformatics 2003, 4: 66. [http:\/\/www.biomedcentral.com\/1471\u20132105\/4\/66] 10.1186\/1471-2105-4-66","journal-title":"BMC Bioinformatics"},{"key":"244_CR19","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1109\/71.674320","volume":"9","author":"TK Yap","year":"1998","unstructured":"Yap TK, Frieder O, Martino RL: Parallel Computation in biological sequence analysis.\n                           IEEE Transactions on Parallel and Distributed Systems 1998, 9: 283\u2013294. 10.1109\/71.674320","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"244_CR20","doi-asserted-by":"publisher","first-page":"1270","DOI":"10.1093\/bioinformatics\/18.9.1270","volume":"18","author":"J Kleinjung","year":"2002","unstructured":"Kleinjung J, Douglas N, Heringa J: Parallelized multiple alignment.\n                           Bioinformatics 2002, 18: 1270\u20131271. 10.1093\/bioinformatics\/18.9.1270","journal-title":"Bioinformatics"},{"key":"244_CR21","doi-asserted-by":"publisher","first-page":"1585","DOI":"10.1093\/bioinformatics\/btg192","volume":"19","author":"KB Li","year":"2003","unstructured":"Li KB: ClustalW-MPI: ClustalW analysis using distributed and parallel computing.\n                           Bioinformatics 2003, 19: 1585\u20131586. 10.1093\/bioinformatics\/btg192","journal-title":"Bioinformatics"},{"key":"244_CR22","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.\n                           Applied Mathematics Letters 2002, 15: 11\u201316. 10.1016\/S0893-9659(01)00085-4","journal-title":"Applied Mathematics Letters"},{"key":"244_CR23","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).\n                           Lecture Notes in Computer Science 2001, 2066: 1\u201311.","journal-title":"Lecture Notes in Computer Science"},{"key":"244_CR24","unstructured":"Morgenstern B, Prohaska SJ, Werner N, Weyer-Menkhoff J, Schneider I, Subramanian AR, Stadler PF: Multiple sequence alignment with user-defined constraints.\n                           In Proceedings GCB'04, Lecture Notes in Informatics P-53, 25\u201336"},{"key":"244_CR25","doi-asserted-by":"publisher","first-page":"GC45","DOI":"10.1016\/S0378-1119(98)00097-3","volume":"211","author":"J Stoye","year":"1998","unstructured":"Stoye J: Multiple sequence alignment with the divide-and-conquer method.\n                           Gene 1998, 211: GC45-GC56. 10.1016\/S0378-1119(98)00097-3","journal-title":"Gene"},{"key":"244_CR26","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS: A linear space algorithm for computing maximal common subsequences.\n                           Commun ACM 1975, 18: 314\u2013343. 10.1145\/360825.360861","journal-title":"Commun ACM"},{"key":"244_CR27","volume-title":"Tech. Rep. CS-94-230, Computer Science Department, University of Tennessee, Knoxville, TN","author":"Message Passing Interface Forum","year":"1994","unstructured":"Message Passing Interface Forum: MPI: A Message-Passing Interface Standard.\n                           Tech. Rep. CS-94\u2013230, Computer Science Department, University of Tennessee, Knoxville, TN 1994."},{"key":"244_CR28","volume-title":"Tech. rep., Computer Science Department, University of Tennessee, Knoxville, TN","author":"Message Passing Interface Forum","year":"1997","unstructured":"Message Passing Interface Forum: MPI-2: Extensions to the Message-Passing Interface.\n                           Tech. rep., Computer Science Department, University of Tennessee, Knoxville, TN 1997."},{"key":"244_CR29","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.\n                           Nucleic Acids Research 1999, 27: 2682\u20132690. 10.1093\/nar\/27.13.2682","journal-title":"Nucleic Acids Research"},{"key":"244_CR30","first-page":"483","volume-title":"In AFIPS Conference Proceedings 30","author":"GM Amdahl","year":"1967","unstructured":"Amdahl GM: Validity of the single processor approach to achieve large-scale computing capabilities.\n                           In AFIPS Conference Proceedings 30 AFIPS Press 1967, 483."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-128.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-5-128\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-128.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:17:24Z","timestamp":1728303444000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-5-128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9,9]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2004,12]]}},"alternative-id":["244"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-5-128","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2004,9,9]]},"assertion":[{"value":"23 March 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2004","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2004","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"128"}}