{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:13:47Z","timestamp":1773274427735,"version":"3.50.1"},"reference-count":27,"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 introduce a novel approach to multiple alignment that is based on an algorithm for rapidly checking whether single matches are consistent with a partial multiple alignment. This leads to a sequence annealing algorithm, which is an incremental method for building multiple sequence alignments one match at a time. Our approach improves significantly on the standard progressive alignment approach to multiple alignment.<\/jats:p><jats:p>Results: The sequence annealing algorithm performs well on benchmark test sets of protein sequences. It is not only sensitive, but also specific, drastically reducing the number of incorrectly aligned residues in comparison to other programs. The method allows for adjustment of the sensitivity\/specificity tradeoff and can be used to reliably identify homologous regions among protein sequences.<\/jats:p><jats:p>Availability: An implementation of the sequence annealing algorithm is available at<\/jats:p><jats:p>Contact: sariel@cs.berkeley.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl311","type":"journal-article","created":{"date-parts":[[2007,1,19]],"date-time":"2007-01-19T18:51:12Z","timestamp":1169232672000},"page":"e24-e29","source":"Crossref","is-referenced-by-count":59,"title":["Multiple alignment by sequence annealing"],"prefix":"10.1093","volume":"23","author":[{"given":"Ariel","family":"S. Schwartz","sequence":"first","affiliation":[{"name":"EECS, Computer Science Division, University of California 1 \u00a0 1 \u00a0 \u00a0 Berkeley, CA 94720, USA"}]},{"given":"Lior","family":"Pachter","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California 2 \u00a0 2 \u00a0 \u00a0 Berkeley, CA 94720, USA"}]}],"member":"286","published-online":{"date-parts":[[2007,1,15]]},"reference":[{"key":"2023041107141094000_","article-title":"An o(n2.75) algorithm for online topological ordering","author":"Ajwani","year":"2006"},{"key":"2023041107141094000_","first-page":"32","article-title":"Incremental evaluation of computational circuits","author":"Alpern","year":"1990"},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1093\/bib\/6.1.6","article-title":"The many faces of sequence alignment","volume":"6","author":"Batzoglou","year":"2005","journal-title":"Brief. Bioinform."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/nar\/28.1.254","article-title":"The ASTRAL compendium for protein structure and sequence analysis","volume":"28","author":"Brenner","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023041107141094000_","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":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0893-9659(98)00054-8","article-title":"The number of standard and of effective multiple alignments","volume":"11","author":"Dress","year":"1998","journal-title":"Appl. Math. Lett."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis. Probablistic models of proteins and nucleic acids","author":"Durbin","year":"1998"},{"key":"2023041107141094000_","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":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive alignment of amino acid sequences as a prerequisite to correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol."},{"key":"2023041107141094000_","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":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","article-title":"Dynamic programming alignment accuracy","volume":"5","author":"Holmes","year":"1998","journal-title":"J. Comput. Biol."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","DOI":"10.1145\/1159892.1159896","article-title":"Online topological ordering","author":"Katriel","year":"2006","journal-title":"ACM Trans. Algorithm."},{"key":"2023041107141094000_","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":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(96)00075-0","article-title":"Maintaining a topological order under edge insertions","volume":"59","author":"Marchetti-Spaccarnela","year":"1996","journal-title":"Inform. Process. Lett."},{"key":"2023041107141094000_","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":"2023041107141094000_","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":"2023041107141094000_","article-title":"Consistent equivalence relations: a set-theoretical framework for multiple sequence alignment","volume-title":"Technical Report Materialien und Preprints 133","author":"Morgenstern","year":"1999"},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/S0022-2836(05)80134-2","article-title":"SCOP: a structural classification of proteins database for the investigation of sequences and structures","volume":"247","author":"Murzin","year":"1995","journal-title":"J. Mol. Biol."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel method for multiple sequence alignments","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023041107141094000_","first-page":"383","article-title":"A dynamic algorithm for topologically sorting directed acyclic graphs","author":"Pearce","year":"2004"},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"2336","DOI":"10.1101\/gr.2657504","article-title":"A novel method for multiple alignment of sequences with repeated and shuffled elements","volume":"14","author":"Raphael","year":"2004","journal-title":"Genome Res."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1002\/(SICI)1097-0134(20000701)40:1<6::AID-PROT30>3.0.CO;2-7","article-title":"Large-scale comparison of protein sequence alignment algorithms with structure alignments","volume":"40","author":"Sauder","year":"2000","journal-title":"Proteins"},{"key":"2023041107141094000_","article-title":"Alignment metric accuracy","author":"Schwartz","year":"2006"},{"key":"2023041107141094000_","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 alignment","volume":"6","author":"Subramanian","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTALW: 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":"2023041107141094000_","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1093\/bioinformatics\/bth493","article-title":"SABmark\u2014a benchmark for sequence alignment that covers the entire known fold space","volume":"21","author":"Van Walle","year":"2005","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e24\/49820373\/bioinformatics_23_2_e24.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e24\/49820373\/bioinformatics_23_2_e24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T09:38:45Z","timestamp":1707557925000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/e24\/202846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,15]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl311","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":[[2007,1,15]]}}}