{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:24Z","timestamp":1759639044313},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,5,29]],"date-time":"2009-05-29T00:00:00Z","timestamp":1243555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s10878-009-9233-x","type":"journal-article","created":{"date-parts":[[2009,5,28]],"date-time":"2009-05-28T18:22:33Z","timestamp":1243534953000},"page":"307-318","source":"Crossref","is-referenced-by-count":27,"title":["On recovering syntenic blocks from comparative maps"],"prefix":"10.1007","volume":"18","author":[{"given":"Zhixiang","family":"Chen","sequence":"first","affiliation":[]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,29]]},"reference":[{"key":"9233_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda R, Halld\u00f3rsson MM, Naor JS, Shachnai H, Shapira I (2006) Scheduling split intervals. SIAM J Comput 36:1\u201315","journal-title":"SIAM J Comput"},{"key":"9233_CR2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.tcs.2007.07.002","volume":"385","author":"G Blin","year":"2007","unstructured":"Blin G, Fertin G, Vialette S (2007) Extracting constrained 2-interval subsets in 2-interval sets. Theor Comput Sci 385:241\u2013263","journal-title":"Theor Comput Sci"},{"key":"9233_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-73437-6_14","volume-title":"Proceedings of the 18th annual symposium on combinatorial pattern matching (CPM\u201907)","author":"Z Chen","year":"2007","unstructured":"Chen Z, Fu B, Yang B, Xu J, Zhao Z, Zhu B (2007) Non-breaking similarity of genomes with gene repetitions. In: Proceedings of the 18th annual symposium on combinatorial pattern matching (CPM\u201907). LNCS, vol 4580. Springer, Berlin, pp 119\u2013130"},{"key":"9233_CR4","doi-asserted-by":"crossref","unstructured":"Chen J, Huang X, Kanj I, Xia G (2004) Linear FPT reductions and computational lower bounds. In: Proceedings of the 36th ACM symposium on theory of computing (STOC\u201904), pp 212\u2013221","DOI":"10.1145\/1007352.1007391"},{"key":"9233_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10878-006-9030-8","volume":"13","author":"E Chen","year":"2007","unstructured":"Chen E, Yang L, Yuan H (2007) Improved algorithms for largest cardinality 2-interval pattern problem. J\u00a0Comb Optim 13:263\u2013275","journal-title":"J\u00a0Comb Optim"},{"key":"9233_CR6","doi-asserted-by":"crossref","unstructured":"Choi V, Zheng C, Zhu Q, Sankoff D (2007) Algorithms for the extraction of synteny blocks from comparative maps. In: Proceedings of the 7th international workshop on algorithms in bioinformatics (WABI\u201907), pp 277\u2013288","DOI":"10.1007\/978-3-540-74126-8_26"},{"key":"9233_CR7","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.tcs.2008.01.007","volume":"395","author":"M Crochemore","year":"2008","unstructured":"Crochemore M, Hermelin D, Landau GM, Rawitz D, Vialette S (2008) Approximating the 2-interval pattern problem. Theor Comput Sci 395:283\u2013297","journal-title":"Theor Comput Sci"},{"key":"9233_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R Downey","year":"1999","unstructured":"Downey R, Fellows M (1999) Parameterized complexity. Springer, Berlin"},{"key":"9233_CR9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s10878-006-9024-6","volume":"13","author":"M Jiang","year":"2007","unstructured":"Jiang M (2007a) A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem. J\u00a0Comb Optim 13:217\u2013221","journal-title":"J\u00a0Comb Optim"},{"key":"9233_CR10","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-540-72870-2_38","volume-title":"Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM\u201907)","author":"M Jiang","year":"2007","unstructured":"Jiang M (2007b) Improved approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. In: Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM\u201907). LNCS, vol 4508. Springer, Berlin, pp 399\u2013410"},{"key":"9233_CR11","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-540-73556-4_39","volume-title":"Proceedings of the 1st annual international conference on combinatorial optimization and applications (COCOA\u201907)","author":"M Jiang","year":"2007","unstructured":"Jiang M (2007c) A PTAS for the weighted 2-interval pattern problem over the preceding-and-crossing model. In: Proceedings of the 1st annual international conference on combinatorial optimization and applications (COCOA\u201907). LNCS, vol 4616. Springer, Berlin, pp 378\u2013387"},{"key":"9233_CR12","doi-asserted-by":"crossref","unstructured":"Lyngs\u00f8 RB (2004) Complexity of pseudoknot prediction in simple models. In: Proceedings of the 31st international colloquium on automata, languages and programming (ICALP\u201904), pp 919\u2013931","DOI":"10.1007\/978-3-540-27836-8_77"},{"key":"9233_CR13","doi-asserted-by":"crossref","unstructured":"Schaefer T (1978) The complexity of satisfiability problem. In: Proceedings of the 10th ACM symposium on theory of computing (STOC\u201978), pp 216\u2013226","DOI":"10.1145\/800133.804350"},{"key":"9233_CR14","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S Vialette","year":"2004","unstructured":"Vialette S (2004) On the computational complexity of 2-interval pattern matching problems. Theor Comput Sci 312:223\u2013249","journal-title":"Theor Comput Sci"},{"key":"9233_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"G Watterson","year":"1982","unstructured":"Watterson G, Ewens W, Hall T, Morgan A (1982) The chromosome inversion problem. J Theor Biol 99:1\u20137","journal-title":"J Theor Biol"},{"key":"9233_CR16","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","volume":"4","author":"C Zheng","year":"2007","unstructured":"Zheng C, Zhu Q, Sankoff D (2007) Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE\/ACM Trans Comput Biol Bioinform 4:515\u2013522","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9233-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9233-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9233-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9233-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,29]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9233"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9233-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,29]]}}}