{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T19:59:57Z","timestamp":1711483197236},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Multiple sequence alignments can be constructed on the basis of pairwise local sequence similarities. This approach is rather flexible and can combine the advantages of global and local alignment methods. The restriction to pairwise alignments as building blocks, however, can lead to misalignments since weak homologies may be missed if only pairs of sequences are compared.<\/jats:p>\n               <jats:p>Results: Herein, we propose a graph-theoretical approach to find local multiple sequence similarities. Starting with pairwise alignments produced by DIALIGN, we use a min-cut algorithm to find potential (partial) alignment columns that we use to construct a final multiple alignment. On real and simulated benchmark data, our approach consistently outperforms the standard version of DIALIGN where local pairwise alignments are greedily incorporated into a multiple alignment.<\/jats:p>\n               <jats:p>Availability: The prototype is freely available under GNU Public Licence from E.C.<\/jats:p>\n               <jats:p>Contact: \u00a0ecorel@gwdg.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq082","type":"journal-article","created":{"date-parts":[[2010,2,27]],"date-time":"2010-02-27T01:13:51Z","timestamp":1267233231000},"page":"1015-1021","source":"Crossref","is-referenced-by-count":19,"title":["A <i>min-cut<\/i> algorithm for the consistency problem in multiple sequence alignment"],"prefix":"10.1093","volume":"26","author":[{"given":"Eduardo","family":"Corel","sequence":"first","affiliation":[{"name":"1 Georg-August-Universit\u00e4t, Institut f\u00fcr Mikrobiologie und Genetik, Goldschmidtstra\u00dfe 1, 37077 G\u00f6ttingen, Germany and 2 Partner Institute for Computational Biology, CAS-MPG, 320 Yue Yang Rd, 200031 Shanghai, China"}]},{"given":"Florian","family":"Pitschi","sequence":"additional","affiliation":[{"name":"1 Georg-August-Universit\u00e4t, Institut f\u00fcr Mikrobiologie und Genetik, Goldschmidtstra\u00dfe 1, 37077 G\u00f6ttingen, Germany and 2 Partner Institute for Computational Biology, CAS-MPG, 320 Yue Yang Rd, 200031 Shanghai, China"}]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[{"name":"1 Georg-August-Universit\u00e4t, Institut f\u00fcr Mikrobiologie und Genetik, Goldschmidtstra\u00dfe 1, 37077 G\u00f6ttingen, Germany and 2 Partner Institute for Computational Biology, CAS-MPG, 320 Yue Yang Rd, 200031 Shanghai, China"}]}],"member":"286","published-online":{"date-parts":[[2010,2,25]]},"reference":[{"key":"2023012508075637100_B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-45727-5_1","article-title":"Speeding up the DIALIGN multiple alignment program by using the \u2018greedy alignment of biological sequences library\u2019 (GABIOS-LIB)","volume":"2066","author":"Abdedda\u00efm","year":"2001","journal-title":"Lect. Notes Comput. Sci."},{"key":"2023012508075637100_B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023012508075637100_B3","first-page":"28","article-title":"Fitting a mixture model by expectation maximization to discover motifs in biopolymers","volume-title":"Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology.","author":"Bailey","year":"1994"},{"key":"2023012508075637100_B4","volume-title":"Introduction to Algorithms.","author":"Cormen","year":"2001"},{"key":"2023012508075637100_B5","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"ProbCons: probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res."},{"key":"2023012508075637100_B6","doi-asserted-by":"crossref","DOI":"10.1007\/11732990_15","article-title":"CONTRAlign: discriminative training for protein sequence alignment","volume-title":"Proceedings Research in Computational Molecular Biology '06.","author":"Do","year":"2006"},{"key":"2023012508075637100_B7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1748-7188-3-15","article-title":"Stability of multiple alignments and phylogenetic trees: an analysis of ABC-transporter proteins","volume":"3","author":"Dress","year":"2008","journal-title":"Algorithms Mol. Biol."},{"key":"2023012508075637100_B8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis.","author":"Durbin","year":"1998"},{"key":"2023012508075637100_B9","first-page":"114","article-title":"Fast and sound two-step algorithms for multiple alignment of nucleic sequences","volume-title":"Proceedings of Intelligent Systems for Molecular Biology '95.","author":"Eddy","year":"1995"},{"key":"2023012508075637100_B10","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: multiple sequence alignment with high score accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012508075637100_B11","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.sbi.2006.04.004","article-title":"Multiple sequence alignment","volume":"16","author":"Edgar","year":"2006","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012508075637100_B12","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM"},{"key":"2023012508075637100_B13","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math"},{"key":"2023012508075637100_B14","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF02462264","article-title":"Consistency of optimal sequence alignments","volume":"52","author":"Gotoh","year":"1990","journal-title":"Bull. Math. Biol."},{"key":"2023012508075637100_B15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology.","author":"Gusfield","year":"1997"},{"key":"2023012508075637100_B16","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1093\/nar\/gki198","article-title":"MAFFT version 5: improvement in accuracy of multiple sequence alignment","volume":"33","author":"Katoh","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012508075637100_B17","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0166-218X(00)00194-3","article-title":"A polyhedral approach to sequence alignment problems","volume":"104","author":"Kececioglu","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"2023012508075637100_B18","doi-asserted-by":"crossref","first-page":"2455","DOI":"10.1093\/bioinformatics\/btp452","article-title":"Upcoming challenges for multiple sequence alignment methods in the high-throughput era","volume":"25","author":"Kemena","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508075637100_B19","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/S0014-5793(02)03189-7","article-title":"Quality assessment of multiple alignment programs","volume":"529","author":"Lassmann","year":"2002","journal-title":"FEBS Lett."},{"key":"2023012508075637100_B20","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1186\/1471-2105-6-298","article-title":"Kalign an accurate and fast multiple sequence alignment algorithm","volume":"6","author":"Lassmann","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012508075637100_B21","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":"2023012508075637100_B22","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","article-title":"DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment","volume":"15","author":"Morgenstern","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012508075637100_B23","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1093\/bioinformatics\/16.10.948","article-title":"A space-efficient algorithm for aligning large genomic sequences","volume":"16","author":"Morgenstern","year":"2000","journal-title":"Bioinformatics"},{"key":"2023012508075637100_B24","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0893-9659(01)00085-4","article-title":"A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences","volume":"15","author":"Morgenstern","year":"2002","journal-title":"Appl. Math. Lett."},{"key":"2023012508075637100_B25","doi-asserted-by":"crossref","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","article-title":"Multiple DNA and protein sequence alignment based on segment-to-segment comparison","volume":"93","author":"Morgenstern","year":"1996","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508075637100_B26","doi-asserted-by":"crossref","first-page":"1271","DOI":"10.1093\/bioinformatics\/bti142","article-title":"Multiple sequence alignment with user-defined constraints at GOBICS","volume":"21","author":"Morgenstern","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012508075637100_B27","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/1748-7188-1-6","article-title":"Multiple sequence alignment with user-defined anchor points","volume":"1","author":"Morgenstern","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023012508075637100_B28","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1071\/SB06020","article-title":"Multiple sequence alignment for phylogenetic purposes","volume":"19","author":"Morrison","year":"2006","journal-title":"Aust. Syst. Bot."},{"key":"2023012508075637100_B29","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. Mol. Biol."},{"key":"2023012508075637100_B30","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel algorithm for multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012508075637100_B31","volume-title":"Sequence similarity, motif detection and alignments with N-local decoded anchor points.","author":"Pitschi","year":"2008"},{"key":"2023012508075637100_B32","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012508075637100_B33","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1093\/bioinformatics\/14.2.157","article-title":"Rose: generating sequence families","volume":"14","author":"Stoye","year":"1998","journal-title":"Bioinformatics"},{"key":"2023012508075637100_B34","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":"2023012508075637100_B35","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/1748-7188-3-6","article-title":"DIALIGN-TX: greedy and progressive approaches for the segment-based multiple sequence alignment","volume":"3","author":"Subramanian","year":"2008","journal-title":"Algorithms Mol. Biol."},{"key":"2023012508075637100_B36","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":"2023012508075637100_B37","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 Struct. Funct. Bioinform."},{"key":"2023012508075637100_B38","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0022-2836(91)90871-3","article-title":"Motif recognition and alignment for many sequences by comparison of dot-matrices","volume":"218","author":"Vingron","year":"1991","journal-title":"J. Mol. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/8\/1015\/48856542\/bioinformatics_26_8_1015.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/8\/1015\/48856542\/bioinformatics_26_8_1015.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:11:59Z","timestamp":1674634319000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/8\/1015\/206628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2,25]]},"references-count":38,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq082","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,4,15]]},"published":{"date-parts":[[2010,2,25]]}}}