{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:18:15Z","timestamp":1764688695858},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Many multiple sequence alignment tools have been developed in the past, progressing either in speed or alignment accuracy. Given the importance and wide-spread use of alignment tools, progress in both categories is a contribution to the community and has driven research in the field so far.<\/jats:p>\n               <jats:p>Results: We introduce a graph-based extension to the consistency-based, progressive alignment strategy. We apply the consistency notion to segments instead of single characters. The main problem we solve in this context is to define segments of the sequences in such a way that a graph-based alignment is possible. We implemented the algorithm using the SeqAn library and report results on amino acid and DNA sequences. The benefit of our approach is threefold: (1) sequences with conserved blocks can be rapidly aligned, (2) the implementation is conceptually easy, generic and fast and (3) the consistency idea can be extended to align multiple genomic sequences.<\/jats:p>\n               <jats:p>Availability: The segment-based multiple sequence alignment tool can be downloaded from http:\/\/www.seqan.de\/projects\/msa.html. A novel version of T-Coffee interfaced with the tool is available from http:\/\/www.tcoffee.org. The usage of the tool is described in both documentations.<\/jats:p>\n               <jats:p>Contact: \u00a0rausch@inf.fu-berlin.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn281","type":"journal-article","created":{"date-parts":[[2008,8,9]],"date-time":"2008-08-09T13:08:02Z","timestamp":1218287282000},"page":"i187-i192","source":"Crossref","is-referenced-by-count":44,"title":["Segment-based multiple sequence alignment"],"prefix":"10.1093","volume":"24","author":[{"given":"Tobias","family":"Rausch","sequence":"first","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]},{"given":"Anne-Katrin","family":"Emde","sequence":"additional","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]},{"given":"David","family":"Weese","sequence":"additional","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]},{"given":"Andreas","family":"D\u00f6ring","sequence":"additional","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]},{"given":"Cedric","family":"Notredame","sequence":"additional","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[{"name":"1 International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, 14195 Berlin, Germany, 2Algorithmische Bioinformatik, Institut f\u00fcr Informatik, Takustr. 9, 14195 Berlin, Germany and 3Comparative Bioinformatics Group, Center for Genomic Regulation, Dr Aiguader 88, 08003 Barcelona, Spain"}]}],"member":"286","published-online":{"date-parts":[[2008,8,9]]},"reference":[{"key":"2023020210501728200_B1","first-page":"1","article-title":"Multiple genome alignment: chaining methods revisited","author":"Abouelhoda","year":"2003"},{"key":"2023020210501728200_B2","first-page":"4","article-title":"Multiple sequence alignment with arbitrary gap costs: computing an optimal solution using polyhedral combinatorics","author":"Althaus","year":"2002"},{"key":"2023020210501728200_B3","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s10107-005-0659-3","article-title":"A branch-and-cut algorithm for multiple sequence alignment","volume":"105","author":"Althaus","year":"2006","journal-title":"Math. Prog"},{"key":"2023020210501728200_B4","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023020210501728200_B5","article-title":"The multiple sequence alignment problem in biology","volume":"48","author":"Carrillo","year":"1988","journal-title":"SIJAM: SIAM Journal on Applied Mathematics"},{"key":"2023020210501728200_B6","volume-title":"Introduction to Algorithms.","author":"Cormen","year":"2001"},{"key":"2023020210501728200_B7","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","article-title":"Alignment of whole genomes","volume":"27","author":"Delcher","year":"1999","journal-title":"Nucl. Acids. Res"},{"key":"2023020210501728200_B8","first-page":"703","article-title":"ProbCons: probabilistic consistency-based multiple alignment of amino acid sequences","volume-title":"AAAI.","author":"Chuong","year":"2004"},{"key":"2023020210501728200_B9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1471-2105-9-11","article-title":"SeqAn - an efficient, generic C++ library for sequence analysis","volume":"9","author":"D\u00f6ring","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020210501728200_B10","volume-title":"Dynamic Data Structures for Orthogonal Intersection Queries. Technical Report F59.","author":"Edelsbrunner","year":"1980"},{"key":"2023020210501728200_B11","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020210501728200_B12","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisite to correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol"},{"key":"2023020210501728200_B13","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","journal-title":"J. Mol. Biol"},{"key":"2023020210501728200_B14","article-title":"Consistency of optimal sequence alignments","volume":"52","author":"Gotoh","year":"1990","journal-title":"BMB"},{"key":"2023020210501728200_B15","first-page":"126","article-title":"Segment match refinment and applications. In","volume-title":"Proceedings of the 2nd Workshop on Algorithms Bioinformatics (WABI-02).","author":"Halpern","year":"2002"},{"key":"2023020210501728200_B16","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":"2023020210501728200_B17","first-page":"52","article-title":"Heaviest increasing\/common subsequence problems. In","author":"Jacobson","year":"1992"},{"key":"2023020210501728200_B18","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1093\/nar\/gkf436","article-title":"MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform","volume":"30","author":"Katoh","year":"2002","journal-title":"Nucleic Acids Res"},{"key":"2023020210501728200_B19","first-page":"106","article-title":"The maximum weight trace problem in multiple sequence alignment. In","author":"Kececioglu","year":"1993"},{"key":"2023020210501728200_B20","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1093\/bioinformatics\/15.3.203","article-title":"An exact solution for the segment-to-segment multiple sequence alignment problem","volume":"15","author":"Lenhof","year":"1999","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B21","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1089\/106652701446134","article-title":"The practical use of the A* algorithm for exact multiple sequence alignment","volume":"7","author":"Lermen","year":"2000","journal-title":"J. Comp. Biol"},{"key":"2023020210501728200_B22","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","article-title":"A tool for multiple sequence alignment","volume":"86","author":"Lipman","year":"1989","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020210501728200_B23","first-page":"38","article-title":"Chaining multiple-alignment fragments in sub-quadratic time. In","author":"Myers","year":"1995"},{"key":"2023020210501728200_B24","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Molecular Biol"},{"key":"2023020210501728200_B25","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol"},{"key":"2023020210501728200_B26","doi-asserted-by":"crossref","first-page":"4364","DOI":"10.1093\/nar\/gkl514","article-title":"MUMMALS: multiple sequence alignment improved by using hidden Markov models with local structural information","volume":"34","author":"Pei","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023020210501728200_B27","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1093\/bioinformatics\/btm017","article-title":"PROMALS: towards accurate multiple sequence alignments of distantly related proteins","volume":"23","author":"Pei","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B28","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1093\/bioinformatics\/16.9.808","article-title":"An iterative methods for faster sum-of-pairs multiple sequence alignment","volume":"16","author":"Reinert","year":"2000","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B29","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol"},{"key":"2023020210501728200_B30","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison.","author":"Sankoff","year":"1983"},{"key":"2023020210501728200_B31","doi-asserted-by":"crossref","first-page":"e24","DOI":"10.1093\/bioinformatics\/btl311","article-title":"Multiple alignment by sequence annealing","volume":"23","author":"Schwartz","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B32","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"Univ. Kansas Sci. Bull"},{"key":"2023020210501728200_B33","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1186\/1471-2105-6-66","article-title":"DIALIGN-T: an improved algorithm for segment-based multiple sequence alignment","volume":"6","author":"Subramanian","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023020210501728200_B34","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1093\/bioinformatics\/btl112","article-title":"AuberGene\u2013a sensitive genome alignment tool","volume":"22","author":"Szklarczyk","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B35","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res"},{"key":"2023020210501728200_B36","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins"},{"key":"2023020210501728200_B37","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","article-title":"BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs","volume":"15","author":"Thompson","year":"1999","journal-title":"Bioinformatics"},{"key":"2023020210501728200_B38","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1093\/nar\/gkl091","article-title":"M-Coffee: combining multiple sequence alignment methods with T-Coffee","volume":"34","author":"Wallace","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2023020210501728200_B39","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol"},{"key":"2023020210501728200_B40","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","article-title":"Anew algorithm for best subsequence alignments with application to tRNA-rRNA comparisons","volume":"197","author":"Waterman","year":"1987","journal-title":"J. Mol. Biol"},{"key":"2023020210501728200_B41","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1093\/bioinformatics\/btm226","article-title":"Multiple alignment by aligning alignments","volume":"23","author":"Wheeler","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/16\/i187\/49053222\/bioinformatics_24_16_i187.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/16\/i187\/49053222\/bioinformatics_24_16_i187.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:49:28Z","timestamp":1675342168000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/16\/i187\/200409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,9]]},"references-count":41,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2008,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn281","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,8,15]]},"published":{"date-parts":[[2008,8,9]]}}}