{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:28:58Z","timestamp":1758266938272},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Recently, the concept of the constrained sequence alignment was proposed to incorporate the knowledge of biologists about structures\/functionalities\/consensuses of their datasets into sequence alignment such that the user-specified residues\/nucleotides are aligned together in the computed alignment. The currently developed programs use the so-called progressive approach to efficiently obtain a constrained alignment of several sequences. However, the kernels of these programs, the dynamic programming algorithms for computing an optimal constrained alignment between two sequences, run in \ud835\udcaa(\u03b3n2) memory, where \u03b3 is the number of the constraints and n is the maximum of the lengths of sequences. As a result, such a high memory requirement limits the overall programs to align short sequences~only.<\/jats:p>\n               <jats:p>Results: We adopt the divide-and-conquer approach to design a memory-efficient algorithm for computing an optimal constrained alignment between two sequences, which greatly reduces the memory requirement of the dynamic programming approaches at the expense of a small constant factor in CPU time. This new algorithm consumes only \ud835\udcaa(\u03b1n) space, where \u03b1 is the sum of the lengths of constraints and usually \u03b1 \u226a n in practical applications. Based on this algorithm, we have developed a memory-efficient tool for multiple sequence alignment with constraints.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/genome.life.nctu.edu.tw\/MUSICME<\/jats:p>\n               <jats:p>Contact: \u00a0cllu@mail.nctu.edu.tw<\/jats:p>","DOI":"10.1093\/bioinformatics\/bth468","type":"journal-article","created":{"date-parts":[[2004,9,17]],"date-time":"2004-09-17T00:13:37Z","timestamp":1095380017000},"page":"20-30","source":"Crossref","is-referenced-by-count":15,"title":["A memory-efficient algorithm for multiple sequence alignment with constraints"],"prefix":"10.1093","volume":"21","author":[{"given":"Chin Lung","family":"Lu","sequence":"first","affiliation":[{"name":"Department of Biological Science and Technology, National Chiao Tung University Hsinchu 300, Taiwan, Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yen Pin","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Biological Science and Technology, National Chiao Tung University Hsinchu 300, Taiwan, Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2004,8,12]]},"reference":[{"key":"2023013107193889800_B1","unstructured":"Bafna, V., Lawler, E.L., Pevzner, P.A. 1997Approximation algorithms for multiple sequence alignment. Theoret. Comput. Sci.182233\u2013244"},{"key":"2023013107193889800_B2","unstructured":"Bonizzoni, P. and Vedova, G.D. 2001The complexity of multiple sequence alignment with SP-score that is a metric. Theoret. Comput. Sci.25963\u201379"},{"key":"2023013107193889800_B3","doi-asserted-by":"crossref","unstructured":"Carrillo, H. and Lipman, D. 1988The multiple sequence alignment problem in biology. SIAM J. Appl. Math.481073\u20131082","DOI":"10.1137\/0148063"},{"key":"2023013107193889800_B4","unstructured":"Chan, S.C., Wong, A.K.C., Chiu, D.K.Y. 1992A survey of multiple sequence comparison methods. Bull. Math. Biol.54563\u2013598"},{"key":"2023013107193889800_B5","unstructured":"Chao, K.M., Hardison, R.C., Miller, W. 1994Recent developments in linear-space alignment methods: a survey. J. Comput. Biol.1271\u2013291"},{"key":"2023013107193889800_B6","unstructured":"Chin, F.Y.L., Ho, N.L., Lamy, T.W., Wong, P.W.H., Chan, M.Y. 2003Efficient constrained multiple sequence alignment with performance guarantee. Proceedings of the IEEE Computer Society Bioinformatics Conference (CSB 2003) , Los Alamitos, CA  IEEE,  pp. pp. 337\u2013346"},{"key":"2023013107193889800_B7","doi-asserted-by":"crossref","unstructured":"Corpet, F. 1988Multiple sequence alignment with hierarchical clustering. Nucleic Acids Res.1610881\u201310890","DOI":"10.1093\/nar\/16.22.10881"},{"key":"2023013107193889800_B8","unstructured":"Deiman, B. and Pleij, C.W.A. 1997Pseudoknots: a vital feature in viral RNA. Semin. Virol.8166\u2013175"},{"key":"2023013107193889800_B9","doi-asserted-by":"crossref","unstructured":"Depiereux, E. and Feytmans, E. 1992MATCH-BOX: a fundamentally new algorithm for the simultaneous alignment of several protein sequences. Comput. Appl. Biosci.8501\u2013509","DOI":"10.1093\/bioinformatics\/8.5.501"},{"key":"2023013107193889800_B10","unstructured":"Feng, D.F. and Doolittle, R.F. 1987Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol.25351\u2013360"},{"key":"2023013107193889800_B11","unstructured":"Gusfield, D. 1993Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol.55141\u2013154"},{"key":"2023013107193889800_B12","doi-asserted-by":"crossref","unstructured":"Gusfield, D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology1997, NY  Cambridge University Press","DOI":"10.1017\/CBO9780511574931"},{"key":"2023013107193889800_B13","doi-asserted-by":"crossref","unstructured":"Higgins, D. and Sharpe, P. 1988CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene73,  pp. 237\u2013244","DOI":"10.1016\/0378-1119(88)90330-7"},{"key":"2023013107193889800_B14","doi-asserted-by":"crossref","unstructured":"Hirschberg, D.S. 1975A linear space algorithm for computing maximal common subsequences. Commun. ACM18341\u2013343","DOI":"10.1145\/360825.360861"},{"key":"2023013107193889800_B15","unstructured":"Ikeda, T. and Imai, H. 1994Fast A* algorithms for multiple sequence alignment. Proceedings of the Genome Informatics Workshop , Tokyo  Universal Academy Press,  pp. pp. 90\u201399"},{"key":"2023013107193889800_B16","doi-asserted-by":"crossref","unstructured":"Ikeda, T. and Imai, H. 1999Enhanced A* algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases. Theoret. Comput. Sci.210341\u2013374","DOI":"10.1016\/S0304-3975(98)00093-0"},{"key":"2023013107193889800_B17","doi-asserted-by":"crossref","unstructured":"Kececioglu, J.D. 1993The maximum weight trace problem in multiple sequence alignment. Proceedings of the Fourth Annual Symposium on Combinatorial Pattern Matching (CPM 2004) , Heidelberg, Germany  LNCS Springer-Verlag 684,  pp. pp. 106\u2013119","DOI":"10.1007\/BFb0029800"},{"key":"2023013107193889800_B18","unstructured":"Kobayashi, H. and Imai, H. 1999Improvement of the A* algorithm for multiple sequence alignment. Proceedings of the Genome Informatics Workshop , Tokyo  Universal Academy Press,  pp. pp. 120\u2013130"},{"key":"2023013107193889800_B19","unstructured":"Lermen, M. and Reinert, K. 2000The practical use of the A* algorithm for exact multiple sequence alignment. J. Comput. Biol.7655\u2013672"},{"key":"2023013107193889800_B20","doi-asserted-by":"crossref","unstructured":"Li, M., Ma, B., Wang, L. 2000Near optimal multiple alignment within a band in polynomial time. Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing (STOC 2000) , Portland, OR  ACM Presspp. 425\u2013434","DOI":"10.1145\/335305.335354"},{"key":"2023013107193889800_B21","unstructured":"McClure, M.A., Vasi, T.K., Fitch, W.M. 1994Comparative analysis of multiple protein-sequence alignment methods. Mol. Biol. Evol.11571\u2013592"},{"key":"2023013107193889800_B22","doi-asserted-by":"crossref","unstructured":"Morgenstern, B. 1999DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment.  Bioinformatics15211\u2013218","DOI":"10.1093\/bioinformatics\/15.3.211"},{"key":"2023013107193889800_B23","unstructured":"Myers, E.W. and Miller, W. 1988Optimal alignment in linear space. Comput. Appl. Biosci.411\u201317"},{"key":"2023013107193889800_B24","doi-asserted-by":"crossref","unstructured":"Myers, G., Selznick, S., Zhang, Z., Miller, W. 1996Progressive multiple alignment with constraints. J. Comput. Biol.3563\u2013572","DOI":"10.1145\/267521.267758"},{"key":"2023013107193889800_B25","unstructured":"Nicholas, H.B., Ropelewski, A.J., Deerfield, D.W. 2002Strategies for multiple sequence alignment. Biotechniques32592\u2013603"},{"key":"2023013107193889800_B26","unstructured":"Notredame, C. 2002Recent progresses in multiple sequence alignment: a survey. Pharmacogenomics3131\u2013144"},{"key":"2023013107193889800_B27","unstructured":"Notredame, C., Higgins, D.G., Heringa, J. 2000T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol.302205\u2013217"},{"key":"2023013107193889800_B28","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A. 1992Multiple alignment, communication cost, and graph matching. SIAM J. Appl. Math.521763\u20131779","DOI":"10.1137\/0152101"},{"key":"2023013107193889800_B29","unstructured":"Pleij, C.W.A. 1994RNA pseudoknots. Curr. Opin. Struct. Biol.4337\u2013344"},{"key":"2023013107193889800_B30","doi-asserted-by":"crossref","unstructured":"Sammeth, M., Morgenstern, B., Stoye, J. 2003Divide-and-conquer multiple alignment with segment-based constraints. Bioinformatics19ii189\u2013ii195","DOI":"10.1093\/bioinformatics\/btg1077"},{"key":"2023013107193889800_B31","unstructured":"Schuler, G.D., Altschul, S.F., Lipman, D.J. 1991A workbench for multiple alignment construction and analysis. Proteins9180\u2013190"},{"key":"2023013107193889800_B32","doi-asserted-by":"crossref","unstructured":"Stoye, J. 1998Multiple sequence alignment with the divide-and-conquer method. Gene211GC45\u2013GC56","DOI":"10.1016\/S0378-1119(98)00097-3"},{"key":"2023013107193889800_B33","unstructured":"Stoye, J., Moultony, V., Dress, A.W.M. 1997DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment. Comput. Appl. Biosci.13625\u2013626"},{"key":"2023013107193889800_B34","doi-asserted-by":"crossref","unstructured":"Stoye, J., Perrey, S.W., Dress, A.W.M. 1997Improving the divide-and-conquer approach to sum-of-pairs multiple sequence alignment. Appl. Math. Lett.1067\u201373","DOI":"10.1016\/S0893-9659(97)00013-X"},{"key":"2023013107193889800_B35","doi-asserted-by":"crossref","unstructured":"Tang, C.Y., Lu, C.L., Chang, M.D.T., Tsai, Y.T., Sun, Y.J., Chao, K.M., Chang, J.M., Chiou, Y.H., Wu, C.M., Chang, H.T., Chou, W.I. 2003Constrained multiple sequence alignment tool development and its application to RNase family alignment. J. Bioinform. Comput. Biol.1267\u2013287","DOI":"10.1142\/S0219720003000095"},{"key":"2023013107193889800_B36","unstructured":"Taylor, W.R. 1987Multiple sequence alignment by a pairwise algorithm. Comput. Appl. Biosci.381\u201387"},{"key":"2023013107193889800_B37","unstructured":"Taylor, W.R. 1994Motif-biased protein sequence alignment. J. Comput. Biol.1297\u2013310"},{"key":"2023013107193889800_B38","doi-asserted-by":"crossref","unstructured":"Thompson, J.D., Higgs, D.G., Gibson, T.J. 1994CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties, and weight matrix choice. Nucleic Acids Res.224673\u20134680","DOI":"10.1093\/nar\/22.22.4673"},{"key":"2023013107193889800_B39","doi-asserted-by":"crossref","unstructured":"Thompson, J.D., Plewniak, F., Thierry, J.-C., Poch, O. 2000DbClustal: rapid and reliable global multiple alignments of protein sequences detected by database searches. Nucleic Acids Res.282919\u20132926","DOI":"10.1093\/nar\/28.15.2919"},{"key":"2023013107193889800_B40","doi-asserted-by":"crossref","unstructured":"T\u00f6nges, U., Perrey, S.W., Stoye, J., Dress, A.W.M. 1996A general method for fast multiple sequence alignment. Gene172GC33\u2013GC41","DOI":"10.1016\/0378-1119(96)00123-0"},{"key":"2023013107193889800_B41","doi-asserted-by":"crossref","unstructured":"Tsai, Y.T., Huang, Y.P., Yu, C.T., Lu, C.L. 2004MuSiC: a tool for multiple sequence alignment with constraints. Bioinformatics  (in press)","DOI":"10.1093\/bioinformatics\/bth220"},{"key":"2023013107193889800_B42","unstructured":"Wang, L. and Jiang, T. 1994On the complexity of multiple sequence alignment. J. Comput. Biol.1337\u2013348"},{"key":"2023013107193889800_B43","unstructured":"Williams, G.D., Chang, R.-Y., Brian, D.A. 1999A phylogenetically conserved hairpin-type 39 untranslated region pseudoknot functions in coronavirus RNA replication. J. Virol.738349\u20138355"},{"key":"2023013107193889800_B44","unstructured":"Yu, C.T. 2003Efficient algorithms for constrained sequence alignment problems.   Master's Thesis, Department of Computer Science and Information Management, Providence University"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/1\/20\/48961954\/bioinformatics_21_1_20.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/1\/20\/48961954\/bioinformatics_21_1_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T09:57:58Z","timestamp":1675159078000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/1\/20\/212551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8,12]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bth468","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,1,1]]},"published":{"date-parts":[[2004,8,12]]}}}