{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T10:10:02Z","timestamp":1748599802026,"version":"3.41.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"The Research Grants Council of the Hong","award":["CityU 122511"],"award-info":[{"award-number":["CityU 122511"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00453-015-0057-z","type":"journal-article","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T14:40:46Z","timestamp":1441032046000},"page":"65-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Polynomial Time Approximation Scheme for the Closest Shared Center Problem"],"prefix":"10.1007","volume":"77","author":[{"given":"Weidong","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjuan","family":"Cui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,1]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1038\/ng786","volume":"30","author":"G Abecasis","year":"2002","unstructured":"Abecasis, G., Cherny, S., Cookson, W., Cardon, L.: Merlin-rapid analysis of dense genetic maps using sparse gene flow trees. Nat. Genet. 30, 97\u2013101 (2002)","journal-title":"Nat. Genet."},{"key":"57_CR2","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1038\/75514","volume":"25","author":"D Gudbjartsson","year":"2000","unstructured":"Gudbjartsson, D., Jonasson, K., Frigge, M., Kong, A.: Allegro, a new computer program for multipoint linkage analysis. Nat. Genet. 25, 12\u201313 (2000)","journal-title":"Nat. Genet."},{"key":"57_CR3","doi-asserted-by":"crossref","first-page":"2363","DOI":"10.1073\/pnas.84.8.2363","volume":"84","author":"E Lander","year":"1987","unstructured":"Lander, E., Green, P.: Construction ofmultilocus genetic linkage maps in humans. Proc. Natl. Acad. Sci. 84, 2363\u20132367 (1987)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"57_CR4","first-page":"1347","volume":"58","author":"L Kruglyak","year":"1995","unstructured":"Kruglyak, L., Daly, M., Reeve-Daly, M., Lander, E.: Parametric and nonparametric linkage analysis: a unified multipoint approach. Am. J. Hum. Genet. 58, 1347\u20131363 (1995)","journal-title":"Am. J. Hum. Genet."},{"issue":"11","key":"57_CR5","doi-asserted-by":"crossref","first-page":"3443","DOI":"10.1073\/pnas.81.11.3443","volume":"81","author":"G Lathrop","year":"1984","unstructured":"Lathrop, G., Lalouel, J., Julier, C., Ott, J.: Strategies for multilocus linkage analysis in humans. Proc. Natl. Acad. Sci. 81(11), 3443\u20133446 (1984)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"57_CR6","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1471-2156-6-7","volume":"6","author":"I Leykin","year":"2005","unstructured":"Leykin, I., Hao, K., Cheng, J., Meyer, N., Pollak, M., Smith, R., Wong, W., Rosenow, C., Li, C.: Comparative linkage analysis and visualization of high-density oligonucleotide SNP array data. BMC Genet. 6, 7 (2005)","journal-title":"BMC Genet."},{"key":"57_CR7","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1186\/1471-2105-10-115","volume":"10","author":"Z Cai","year":"2009","unstructured":"Cai, Z., Sabaa, H., Wang, Y., Goebel, R., Wang, Z., Xu, J., Stothard, P., Lin, G.: Most parsimonious haplotype allele sharing determination. BMC Bioinform. 10, 115 (2009)","journal-title":"BMC Bioinform."},{"issue":"1","key":"57_CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1093\/bioinformatics\/btm552","volume":"24","author":"G Lin","year":"2008","unstructured":"Lin, G., Wang, Z., Wang, L., Lau, Y.-L., Yang, W.: Identification of linked regions using high-density SNP genotype data in linkage analysis. Bioinformatics 24(1), 86\u201393 (2008)","journal-title":"Bioinformatics"},{"key":"57_CR9","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1186\/1471-2105-10-216","volume":"10","author":"L Wang","year":"2009","unstructured":"Wang, L., Wang, Z., Yang, W.: Linked region detection using high-density SNP genotype data via theminimum recombinantmodel of pedigree haplotype inference. BMC Bioinform. 10, 216 (2009)","journal-title":"BMC Bioinform."},{"issue":"6","key":"57_CR10","doi-asserted-by":"crossref","first-page":"1434","DOI":"10.1086\/340610","volume":"70","author":"D Qian","year":"2002","unstructured":"Qian, D., Beckmann, L.: Minimum-recombinant haplotyping in pedigrees. Am. J. Hum. Genet. 70(6), 1434\u20131445 (2002)","journal-title":"Am. J. Hum. Genet."},{"key":"57_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1159\/000022890","volume":"50","author":"P Tapadar","year":"2000","unstructured":"Tapadar, P., Ghosh, S., Majumder, P.: Haplotyping in pedigrees via a genetic algorithm. Hum. Hered. 50, 43\u201356 (2000)","journal-title":"Hum. Hered."},{"key":"57_CR12","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1093\/bioinformatics\/bth388","volume":"21","author":"L Zhang","year":"2005","unstructured":"Zhang, L., Sun, F., Zhao, H.: HAPLORE: a program for haplotype reconstruction in general pedigrees without recombination. Bioinformatics 21, 90\u2013103 (2005)","journal-title":"Bioinformatics"},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"Doi, L., Li, J., Jiang, T.: Minimum recombinant haplotype configuration on tree pedigrees. In: Proceedings of Workshop on Algorithms in Bioinformatics (WABI), pp. 339\u2013353 (2003)","DOI":"10.1007\/978-3-540-39763-2_25"},{"issue":"6","key":"57_CR14","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1089\/cmb.2005.12.719","volume":"12","author":"J Li","year":"2005","unstructured":"Li, J., Jiang, T.: Computing theminimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer linear programming. J. Comput. Biol. 12(6), 719\u2013739 (2005)","journal-title":"J. Comput. Biol."},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"Li, J., Jiang, T.: An exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming. In: Proceedings of the Eighth Annual International Conference on Resaerch in Computational Molecular Biology (RECOMB), San Diego, California, USA, pp. 20\u201329 (2004)","DOI":"10.1145\/974614.974618"},{"key":"57_CR16","unstructured":"Xiao, J., Liu, L., Xia, L., Jiang, T.: Fast elimination of redundant linear equations and reconstruction of recombination-freemendelian inheritance on a pedigree. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana USA, pp. 655\u2013664 ( 2007)"},{"issue":"2","key":"57_CR17","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1109\/TCBB.2011.137","volume":"9","author":"W Ma","year":"2012","unstructured":"Ma, W., Yang, Y., Chen, Z., Wang, L.: Mutation region detection for closely related individuals without a known pedigree using high-density genotype data. IEEE ACM Trans. Comput. Biol. Bioinform. 9(2), 372\u2013384 (2012)","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"key":"57_CR18","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1186\/1471-2105-13-146","volume":"13","author":"W Cui","year":"2012","unstructured":"Cui, W., Wang, L.: Identifying mutation regions for closely related individuals without a known pedigree. BMC Bioinform. 13, 146 (2012)","journal-title":"BMC Bioinform."},{"issue":"2","key":"57_CR19","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-012-9730-7","volume":"69","author":"Z Chen","year":"2014","unstructured":"Chen, Z., Ma, W., Wang, L.: The parameterized complexity of the shared center problem. Algorithmica 69(2), 269\u2013293 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"57_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1089\/10665270152530863","volume":"8","author":"D Gusfield","year":"2001","unstructured":"Gusfield, D.: Inference of haplotypes from samples of diploid populations: complexity and algorithms. J. Comput. Biol. 8(3), 305\u2013323 (2001)","journal-title":"J. Comput. Biol."},{"key":"57_CR21","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Haplotype inference by pure parsimony. In: Combinatorial Pattern Matching. Springer, Morelia, Michocan Mexico, pp. 144\u2013155 (2003)","DOI":"10.1007\/3-540-44888-8_11"},{"issue":"14","key":"57_CR22","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","volume":"19","author":"L Wang","year":"2003","unstructured":"Wang, L., Xu, Y.: Haplotype inference by maximum parsimony. Bioinformatics 19(14), 1773\u20131780 (2003)","journal-title":"Bioinformatics"},{"key":"57_CR23","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.ajhg.2011.07.023","volume":"89","author":"J Roach","year":"2011","unstructured":"Roach, J., Glusman, G., Hubley, R., Montsaroff, S., Holloway, A., Mauldin, D., Srivastava, D., Garg, V., Pollard, K., Galas, D., Hood, L., Smit, A.: Chromosomal haplotypes by genetic phasing of human families. Am. J. Hum. Genet. 89, 382\u2013397 (2011)","journal-title":"Am. J. Hum. Genet."},{"key":"57_CR24","doi-asserted-by":"crossref","first-page":"i153","DOI":"10.1093\/bioinformatics\/btn298","volume":"24","author":"V Bansal","year":"2008","unstructured":"Bansal, V., Bafna, V.: HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics 24, i153 (2008)","journal-title":"Bioinformatics"},{"key":"57_CR25","doi-asserted-by":"crossref","first-page":"1938","DOI":"10.1093\/bioinformatics\/btt349","volume":"29","author":"Z Chen","year":"2013","unstructured":"Chen, Z., Deng, F., Wang, L.: Exact algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 29, 1938\u20131945 (2013)","journal-title":"Bioinformatics"},{"key":"57_CR26","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM 49, 157\u2013171 (2002)","journal-title":"J. ACM"},{"key":"57_CR27","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"57_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"57_CR29","doi-asserted-by":"crossref","unstructured":"Gillman, D.: A Chernoff bound for randomwalks on expanders. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 680\u2013691 (1993)","DOI":"10.1109\/SFCS.1993.366819"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0057-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0057-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0057-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0057-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T09:36:40Z","timestamp":1748597800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0057-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["57"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0057-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,9,1]]}}}