{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:26:31Z","timestamp":1743049591762,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_20","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"164-176","source":"Crossref","is-referenced-by-count":1,"title":["Hardness and Approximation of the Asynchronous Border Minimization Problem"],"prefix":"10.1007","author":[{"given":"Alexandru","family":"Popa","sequence":"first","affiliation":[]},{"given":"Prudence W. H.","family":"Wong","sequence":"additional","affiliation":[]},{"given":"Fencol C. C.","family":"Yung","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: FOCS, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"issue":"1-2","key":"20_CR2","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(99)00324-2","volume":"259","author":"P. Bonizzoni","year":"2001","unstructured":"Bonizzoni, P., Vedova, G.D.: The complexity of multiple sequence alignment with SP-score that is a metric. TCS\u00a0259(1-2), 63\u201379 (2001)","journal-title":"TCS"},{"key":"20_CR3","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/11851561_30","volume-title":"Algorithms in Bioinformatics","author":"S.A. Carvalho de Jr.","year":"2006","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Improving the Layout of Oligonucleotide Microarrays: Pivot Partitioning. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol.\u00a04175, pp. 321\u2013332. Springer, Heidelberg (2006)"},{"key":"20_CR4","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Microarray layout as quadratic assignment problem. In: Proc. GCB, pp. 11\u201320 (2006)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Improving the design of genechip arrays by combining placement and embedding. In: Proc. 6th CSB, pp. 54\u201363 (2007)","DOI":"10.1142\/9781860948732_0042"},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1158\/0008-5472.CAN-04-2962","volume":"66","author":"M. Chatterjee","year":"2006","unstructured":"Chatterjee, M., Mohapatra, S., Ionan, A., Bawa, G., Ali-Fehmi, R., Wang, X., Nowak, J., Ye, B., Nahhas, F.A., Lu, K., Witkin, S.S., Fishman, D., Munkarah, A., Morris, R., Levin, N.K., Shirley, N.N., Tromp, G., Abrams, J., Draghici, S., Tainsky, M.A.: Diagnostic markers of ovarian cancer by high-throughput antigen cloning and detection on arrays. Cancer Research\u00a066(2), 1181\u20131190 (2006)","journal-title":"Cancer Research"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Cretich, M., Chiari, M.: Peptide Microarrays Methods and Protocols. Methods in Molecular Biology, vol.\u00a0570. Human Press (2009)","DOI":"10.1007\/978-1-60327-394-7"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF01935007","volume":"25","author":"J. Ernvall","year":"1985","unstructured":"Ernvall, J., Katajainen, J., Penttonen, M.: NP-completeness of the hamming salesman problem. BIT Numerical Mathematics\u00a025, 289\u2013292 (1985)","journal-title":"BIT Numerical Mathematics"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC, pp. 448\u2013455 (2003)","DOI":"10.1145\/780606.780608"},{"issue":"1","key":"20_CR10","first-page":"233","volume":"182","author":"D.F. Feng","year":"1987","unstructured":"Feng, D.F., Doolittle, R.F.: Approximation algorithms for multiple sequence alignment. TCS\u00a0182(1), 233\u2013244 (1987)","journal-title":"TCS"},{"issue":"4995","key":"20_CR11","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1126\/science.1990438","volume":"251","author":"S. Fodor","year":"1991","unstructured":"Fodor, S., Read, J., Pirrung, M., Stryer, L., Lu, A., Solas, D.: Light-directed, spatially addressable parallel chemical synthesis. Science\u00a0251(4995), 767\u2013773 (1991)","journal-title":"Science"},{"issue":"5","key":"20_CR12","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/S0968-0004(99)01382-1","volume":"24","author":"D. Gerhold","year":"1999","unstructured":"Gerhold, D., Rushmore, T., Caskey, C.T.: DNA chips: promising toys have become powerful tools. Trends in Biochemical Sciences\u00a024(5), 168\u2013173 (1999)","journal-title":"Trends in Biochemical Sciences"},{"issue":"1","key":"20_CR13","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology\u00a055(1), 141\u2013154 (1993)","journal-title":"Bulletin of Mathematical Biology"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45713-5_1","volume":"77","author":"S. Hannenhalli","year":"2002","unstructured":"Hannenhalli, S., Hubell, E., Lipshutz, R., Pevzner, P.A.: Combinatorial algorithms for design of DNA arrays. Adv. in Biochem. Eng.\/Biotech.\u00a077, 1\u201319 (2002)","journal-title":"Adv. in Biochem. Eng.\/Biotech."},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1093\/bioinformatics\/18.10.1340","volume":"18","author":"L. Kaderali","year":"2002","unstructured":"Kaderali, L., Schliep, A.: Selecting signature oligonucleotides to identify organisms using DNA arrays. Bioinformatics\u00a018, 1340\u20131349 (2002)","journal-title":"Bioinformatics"},{"issue":"2\/3","key":"20_CR16","first-page":"429","volume":"11","author":"A.B. Kahng","year":"2004","unstructured":"Kahng, A.B., Mandoiu, I.I., Pevzner, P.A., Reda, S., Zelikovsky, A.: Scalable heuristics for design of DNA probe arrays. JCB\u00a011(2\/3), 429\u2013447 (2004); Preliminary versions in WABI 2002 and RECOMB 2003","journal-title":"JCB"},{"issue":"2","key":"20_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/TCAD.2005.855940","volume":"25","author":"A.B. Kahng","year":"2006","unstructured":"Kahng, A.B., Mandoiu, I.I., Reda, S., Xu, X., Zelikovsky, A.: Computer-aided optimization of DNA array design and manufacturing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a025(2), 305\u2013320 (2006)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"20","key":"20_CR18","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1093\/nar\/gnf105","volume":"30","author":"S. Kasif","year":"2002","unstructured":"Kasif, S., Weng, Z., Detri, A., Beigel, R., De Lisi, C.: A computational framework for optimal masking in the synthesis of oligonucleotide microarrays. Nucleic Acids Research\u00a030(20), e106 (2002)","journal-title":"Nucleic Acids Research"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Kundeti, V., Rajasekaran, S.: On the hardness of the border length minimization problem. In: BIBE, pp. 248\u2013253 (2009)","DOI":"10.1109\/BIBE.2009.26"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Kundeti, V., Rajasekaran, S., Dinh, H.: On the border length minimization problem (BLMP) on a square array. CoRR, abs\/1003.2839 (2010)","DOI":"10.1145\/1854776.1854796"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-540-79228-4_36","volume-title":"Theory and Applications of Models of Computation","author":"C.Y. Li","year":"2008","unstructured":"Li, C.Y., Wong, P.W.H., Xin, Q., Yung, F.C.C.: Approximating Border Length for DNA Microarray Synthesis. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 410\u2013422. Springer, Heidelberg (2008)"},{"issue":"11","key":"20_CR22","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1093\/bioinformatics\/17.11.1067","volume":"17","author":"F. Li","year":"2001","unstructured":"Li, F., Stormo, G.: Selection of optimal DNA oligos for gene expression arrays. Bioinformatics\u00a017(11), 1067\u20131076 (2001)","journal-title":"Bioinformatics"},{"issue":"12","key":"20_CR23","doi-asserted-by":"publisher","first-page":"4099","DOI":"10.1158\/0008-5472.CAN-03-3807","volume":"64","author":"C. Melle","year":"2004","unstructured":"Melle, C., Ernst, G., Schimmel, B., Bleul, A., Koscielny, S., Wiesner, A., Bogumil, R., M\u00f6ller, U., Osterloh, D., Halbhuber, K.-J., von Eggeling, F.: A technical triade for proteomic identification and characterization of cancer biomarkers. Cancer Research\u00a064(12), 4099\u20134104 (2004)","journal-title":"Cancer Research"},{"issue":"suppl.2","key":"20_CR24","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/bioinformatics\/btg1073","volume":"19","author":"S. Rahmann","year":"2003","unstructured":"Rahmann, S.: The shortest common supersequence problem in a microarray production setting. Bioinformatics\u00a019(suppl.2), 156\u2013161 (2003)","journal-title":"Bioinformatics"},{"issue":"2","key":"20_CR25","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K.-J. R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K.-J.: The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science\u00a016(2), 187\u2013198 (1981)","journal-title":"Theoretical Computer Science"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Reinert, K., Lenhof, H.P., Mutzel, P., Mehlhorn, K., Kececioglu, J.D.: A branch-and-cut algorithm for multiple sequence alignment. In: RECOMB, pp. 241\u2013250 (1997)","DOI":"10.1145\/267521.267845"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Slonim, D.K., Tamayo, P., Mesirov, J.P., Golub, T.R., Lander, E.S.: Class prediction and discovery using gene expression data. In: RECOMB, pp. 263\u2013272 (2000)","DOI":"10.1145\/332306.332564"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Sung, W.K., Lee, W.H.: Fast and accurate probe selection algorithm for large genomes. In: Proc. 2nd CSB, pp. 65\u201374 (2003)","DOI":"10.1109\/CSB.2003.1227305"},{"issue":"6","key":"20_CR29","doi-asserted-by":"publisher","first-page":"3410","DOI":"10.1073\/pnas.0530278100","volume":"100","author":"J. Welsh","year":"2003","unstructured":"Welsh, J., Sapinoso, L., Kern, S., Brown, D., Liu, T., Bauskin, A., Ward, R., Hawkins, N., Quinn, D., Russell, P., Sutherland, R., Breit, S., Moskaluk, C., Frierson Jr., H., Hampton, G.: Large-scale delineation of secreted protein biomarkers overexpressed in cancer tissue and serum. PNAS\u00a0100(6), 3410\u20133415 (2003)","journal-title":"PNAS"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:55:17Z","timestamp":1743044117000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}