{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T01:55:06Z","timestamp":1692323706837},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: We consider the problem of multiple alignment of protein sequences with the goal of achieving a large SP (Sum-of-Pairs) score.<\/jats:p><jats:p>Results: We introduce a new graph-based method. We name our method QOMA (Quasi-Optimal Multiple Alignment). QOMA starts with an initial alignment. It represents this alignment using a K-partite graph. It then improves the SP score of the initial alignment through local optimizations within a window that moves greedily on the alignment. QOMA uses two parameters to permit flexibility in time\/accuracy trade off: (1) The size of the window for local optimization. (2) The sparsity of the K-partite graph. Unlike traditional progressive methods, QOMA is independent of the order of sequences. The experimental results on BAliBASE benchmarks show that QOMA produces higher SP score than the existing tools including ClustalW, Probcons, Muscle, T-Coffee and DCA. The difference is more significant for distant proteins.<\/jats:p><jats:p>Availability: The software is available from the authors upon request.<\/jats:p><jats:p>Contact: tamer@cise.ufl.edu<\/jats:p><jats:p>Supplementary information: Supplementary material is available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl590","type":"journal-article","created":{"date-parts":[[2006,11,23]],"date-time":"2006-11-23T01:24:28Z","timestamp":1164245068000},"page":"162-168","source":"Crossref","is-referenced-by-count":4,"title":["QOMA: quasi-optimal multiple alignment of protein sequences"],"prefix":"10.1093","volume":"23","author":[{"given":"Xu","family":"Zhang","sequence":"first","affiliation":[{"name":"Computer and Information Science and Engineering, University of Florida \u00a0 Gainesville, FL 32611, USA"}]},{"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[{"name":"Computer and Information Science and Engineering, University of Florida \u00a0 Gainesville, FL 32611, USA"}]}],"member":"286","published-online":{"date-parts":[[2006,11,22]]},"reference":[{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"W295","DOI":"10.1093\/nar\/gki406","article-title":"Manipulating multiple sequence alignments via MaM and WebMaM","volume":"33","author":"Alkan","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1101\/gr.1960404","article-title":"MAVID: constrained ancestral alignment of multiple sequences","volume":"14","author":"Bray","year":"2004","journal-title":"Genome Res."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"333","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":"2023041107035686800_","first-page":"114","article-title":"Multiple alignment using hidden Markov models","volume-title":"Proc Int Conf Intell Syst Mol Biol.","author":"Eddy","year":"1995"},{"key":"2023041107035686800_","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":"2023041107035686800_","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","year":"1982","journal-title":"J. Mol. Biol."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1006\/jmbi.1996.0679","article-title":"Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments","volume":"264","author":"Gotoh","year":"1996","journal-title":"J. Mol. Biol."},{"key":"2023041107035686800_","first-page":"94","article-title":"Family-based homology detection via pairwise sequence comparison","author":"Grundy","year":"1998"},{"key":"2023041107035686800_","article-title":"Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment","author":"Gupta","year":"1996","journal-title":"J. Comput. Biol."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","article-title":"Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment","volume":"2","author":"Gupta","year":"1995","journal-title":"J. Comput. Biol."},{"key":"2023041107035686800_","first-page":"649","article-title":"A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given","volume":"6","author":"Hein","year":"1989","journal-title":"Mol. Biol. Evol."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","article-title":"Amino acid substitution matrices from protein blocks","volume":"89","author":"Henikoff","year":"1992","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0196-8858(91)90017-D","article-title":"A time-efficient, linear-space local similarity algorithm","volume":"12","author":"Huang","year":"1991","journal-title":"Adv. Appl. Math."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1006\/jmbi.1999.3091","article-title":"Protein secondary structure prediction based on position-specific scoring matrices","volume":"292","author":"Jones","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023041107035686800_","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":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","article-title":"Multiple sequence alignment using partial order graphs","volume":"18","author":"Lee","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041107035686800_","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":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1093\/bioinformatics\/14.3.290","article-title":"DIALIGN: finding local similarities by multiple sequence alignment","volume":"14","author":"Morgenstern","year":"1998","journal-title":"Bioinformatics"},{"key":"2023041107035686800_","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":"2023041107035686800_","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":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/mpev.2000.0785","article-title":"Multiple sequence alignment in phylogenetic analysis","volume":"16","author":"Phillips","year":"2000","journal-title":"Mol. Phylogene. Evol."},{"key":"2023041107035686800_","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":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"GC45","DOI":"10.1016\/S0378-1119(98)00097-3","article-title":"Multiple sequence alignment with the divide-and-conquer method","volume":"211","author":"Stoye","year":"1998","journal-title":"Gene"},{"key":"2023041107035686800_","first-page":"625","article-title":"DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment","volume":"13","author":"Stoye","year":"1997","journal-title":"Comput. Appl. Biosci."},{"key":"2023041107035686800_","first-page":"204","article-title":"A polynomial time solvable formulation multiple sequence alignment","author":"Sze","year":"2005"},{"key":"2023041107035686800_","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":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023041107035686800_","doi-asserted-by":"crossref","first-page":"1428","DOI":"10.1093\/bioinformatics\/bth116","article-title":"Align-m\u2014a new algorithm for multiple alignment of highly divergent sequences","volume":"20","author":"Van Walle","year":"2004","journal-title":"Bioinformatics"},{"key":"2023041107035686800_","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":"2023041107035686800_","first-page":"339","article-title":"A new approach for alignment of multiple proteins","author":"Zhang","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/162\/49820331\/bioinformatics_23_2_162.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/162\/49820331\/bioinformatics_23_2_162.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T19:58:27Z","timestamp":1683662307000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/162\/205772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11,22]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl590","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2006,11,22]]}}}