{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:30:37Z","timestamp":1725579037225},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_39","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T04:03:12Z","timestamp":1300075392000},"page":"404-415","source":"Crossref","is-referenced-by-count":0,"title":["Regular Language Constrained Sequence Alignment Revisited"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Kucherov","sequence":"first","affiliation":[]},{"given":"Tamar","family":"Pinhas","sequence":"additional","affiliation":[]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"39_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1016\/j.jda.2007.01.003","volume":"5","author":"A. Arslan","year":"2007","unstructured":"Arslan, A.: Regular expression constrained sequence alignment. Journal of Discrete Algorithms\u00a05(4), 647\u2013661 (2007)","journal-title":"Journal of Discrete Algorithms"},{"issue":"6","key":"39_CR2","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.ipl.2007.04.007","volume":"103","author":"Y. Chung","year":"2007","unstructured":"Chung, Y., Lu, C., Tang, C.: Efficient algorithms for regular expression constrained sequence alignment. Information Processing Letters\u00a0103(6), 240\u2013246 (2007)","journal-title":"Information Processing Letters"},{"issue":"1","key":"39_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. Smith","year":"1981","unstructured":"Smith, T., Waterman, M.: Identification of common molecular subsequences. Journal of Molecular Biology\u00a0147(1), 195\u2013197 (1981)","journal-title":"Journal of Molecular Biology"},{"issue":"6","key":"39_CR4","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"A. Arslan","year":"2005","unstructured":"Arslan, A., Egecioglu, O.: Algorithms for the constrained longest common subsequence problems. International Journal of Foundations of Computer Science\u00a016(6), 1099\u20131110 (2005)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"39_CR5","unstructured":"Chen, Y., Chao, K.: On the generalized constrained longest common subsequence problems. Journal of Combinatorial Optimization, 1\u201310 (2009)"},{"issue":"1","key":"39_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2007.09.008","volume":"106","author":"C. Iliopoulos","year":"2008","unstructured":"Iliopoulos, C., Rahman, M.: New efficient algorithms for the LCS and constrained LCS problems. Information Processing Letters\u00a0106(1), 13\u201318 (2008)","journal-title":"Information Processing Letters"},{"key":"39_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-30500-2_22","volume-title":"Implementation and Application of Automata","author":"Z. Peng","year":"2005","unstructured":"Peng, Z., Ting, H.: Time and space efficient algorithms for constrained sequence alignment. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 237\u2013246. Springer, Heidelberg (2005)"},{"issue":"4","key":"39_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"Y. Tsai","year":"2003","unstructured":"Tsai, Y.: The constrained longest common subsequence problem. Information Processing Letters\u00a088(4), 173\u2013176 (2003)","journal-title":"Information Processing Letters"},{"issue":"13","key":"39_CR9","doi-asserted-by":"publisher","first-page":"3097","DOI":"10.1093\/nar\/21.13.3097","volume":"21","author":"A. Bairoch","year":"1993","unstructured":"Bairoch, A.: The PROSITE dictionary of sites and patterns in proteins, its current status. Nucleic Acids Research\u00a021(13), 3097 (1993)","journal-title":"Nucleic Acids Research"},{"issue":"2","key":"39_CR10","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0219720003000095","volume":"1","author":"C. Tang","year":"2003","unstructured":"Tang, C., Lu, C., Chang, M., Tsai, Y., Sun, Y., Chao, K., Chang, J., Chiou, Y., Wu, C., Chang, H., et al.: Constrained multiple sequence alignment tool development and its application to RNase family alignment. Journal of Bioinformatics and Computational Biology\u00a01(2), 267\u2013287 (2003)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"issue":"4","key":"39_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Information Processing Letters\u00a032(4), 171\u2013176 (1989)","journal-title":"Information Processing Letters"},{"issue":"3","key":"39_CR12","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1137\/S0097539704371353","volume":"35","author":"W. Shi","year":"2006","unstructured":"Shi, W., Su, C.: The rectilinear Steiner arborescence problem is NP-complete. SIAM Journal on Computing\u00a035(3), 729\u2013740 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"43-49","key":"39_CR13","first-page":"299","volume":"3","author":"L. Foulds","year":"1982","unstructured":"Foulds, L., Graham, R.: The Steiner problem in phylogeny is NP-complete. Advances in Applied Mathematics\u00a03(43-49), 299 (1982)","journal-title":"Advances in Applied Mathematics"},{"key":"39_CR14","first-page":"1625","volume":"E87-D","author":"W. Jia","year":"2004","unstructured":"Jia, W., Han, B., Au, P., He, Y., Zhou, W.: Optimal multicast tree routing for cluster computing in hypercube interconnection networks. IEICE Transactions on Information and Systems\u00a0E87-D, 1625\u20131632 (2004)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"10","key":"39_CR15","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1109\/71.246072","volume":"4","author":"X. Lin","year":"1993","unstructured":"Lin, X., Ni, L.: Multicast communication in multicomputer networks. IEEE Transactions on Parallel and Distributed Systems\u00a04(10), 1105\u20131117 (1993)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"1","key":"39_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jpdc.2000.1668","volume":"61","author":"S. Sheu","year":"2001","unstructured":"Sheu, S., Yang, C.: Multicast algorithms for hypercube multiprocessors. Journal of Parallel and Distributed Computing\u00a061(1), 137\u2013149 (2001)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"39_CR17","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics\u00a0162(1), 439\u2013486 (2005)","journal-title":"Annals of Mathematics"},{"issue":"2","key":"39_CR18","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1080\/14786446708639914","volume":"34","author":"J. Sylvester","year":"1867","unstructured":"Sylvester, J.: Thoughts on inverse orthogonal matrices simultaneous sign successions, and tessellated pavements in two or more colors, with applications to Newton\u2019s rule, ornamental tile-work and the theory of numbers. Phil. Mag.\u00a034(2), 461\u2013475 (1867)","journal-title":"Phil. Mag."},{"key":"39_CR19","unstructured":"Seberry, J., Yamada, M.: Hadamard matrices, sequences, and block designs. Contemporary Design Theory: A Collection of Surveys, 431\u2013560 (1992)"},{"issue":"2","key":"39_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1137\/0203011","volume":"3","author":"J. Savage","year":"1974","unstructured":"Savage, J.: An algorithm for the computation of linear forms. SIAM J. Comput.\u00a03(2), 150\u2013158 (1974)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"39_CR21","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J. Hromkovi\u011bc","year":"2001","unstructured":"Hromkovi\u011bc, J., Seibert, S., Wilke, T.: Translating regular expressions into small \u03b5-free nondeterministic finite automata. Journal of Computer and System Sciences\u00a062(4), 565\u2013588 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G. Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFAs without epsilon-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, p. 432. Springer, Heidelberg (2006)"},{"issue":"3","key":"39_CR23","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/S0022-0000(03)00036-9","volume":"66","author":"V. Geffert","year":"2003","unstructured":"Geffert, V.: Translation of binary regular expressions into nondeterministic \u03b5-free automata with O(n logn) transitions. Journal of Computer and System Sciences\u00a066(3), 451\u2013472 (2003)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:28:18Z","timestamp":1558420098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}