{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:35:54Z","timestamp":1773272154157,"version":"3.50.1"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p> Given two sequences S<jats:sub>1<\/jats:sub>, S<jats:sub>2<\/jats:sub>, and a constrained sequence C, a longest common subsequence of S<jats:sub>1<\/jats:sub>, S<jats:sub>2<\/jats:sub> with restriction to C is called a constrained longest common subsequence of S<jats:sub>1<\/jats:sub> and S<jats:sub>2<\/jats:sub> with C. At the same time, an optimal alignment of S<jats:sub>1<\/jats:sub>, S<jats:sub>2<\/jats:sub> with restriction to C is called a constrained pairwise sequence alignment of S<jats:sub>1<\/jats:sub> and S<jats:sub>2<\/jats:sub> with C. Previous algorithms have shown that the constrained longest common subsequence problem is a special case of the constrained pairwise sequence alignment problem, and that both of them can be solved in O(rnm) time, where r, n, and m represent the lengths of C, S<jats:sub>1<\/jats:sub>, and S<jats:sub>2<\/jats:sub>, respectively. In this paper, we extend the definition of constrained pairwise sequence alignment to a more flexible version, called weighted constrained pairwise sequence alignment, in which some constraints might be ignored. We first give an O(rnm)-time algorithm for solving the weighted constrained pairwise sequence alignment problem, then show that our extension can be adopted to solve some constraint-related problems that cannot be solved by previous algorithms for the constrained longest common subsequence problem or the constrained pairwise sequence alignment problem. Therefore, in contrast to previous results, our extension is a new and suitable model for sequence analysis. <\/jats:p>","DOI":"10.1142\/s012905411000712x","type":"journal-article","created":{"date-parts":[[2010,2,7]],"date-time":"2010-02-07T20:27:08Z","timestamp":1265574428000},"page":"51-59","source":"Crossref","is-referenced-by-count":17,"title":["AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS"],"prefix":"10.1142","volume":"21","author":[{"given":"YUNG-HSING","family":"PENG","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHANG-BIAU","family":"YANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KUO-TSUNG","family":"TSENG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KUO-SI","family":"HUANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.07.005"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003674"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.008"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.04.007"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.028"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.11.006"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.09.008"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth468"},{"key":"rf16","unstructured":"R. M.\u00a0Schwartz and M. O.\u00a0Dayhoff, Atlas of Protein Sequence and Structure\u00a05, ed. M.\u00a0Dayhoff (National Biomedical Research Foundation, Washington, DC, 1979)\u00a0pp. 353\u2013358."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720003000095"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.001"},{"key":"rf19","first-page":"51","volume":"3","author":"Tseng K.-T.","journal-title":"Journal of Computers"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1093\/ietisy\/e91-d.3.789"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1080\/02533839.1987.9677028"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411000712X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:32:30Z","timestamp":1565123550000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411000712X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":16,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1142\/S012905411000712X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411000712x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]}}}