{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T06:45:21Z","timestamp":1722753921794},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p>While full-sibling group reconstruction from microsatellite data is a well-studied problem, reconstruction of half-sibling groups is much less studied, theoretically challenging, and computationally demanding. In this paper, we present a formulation of the half-sibling reconstruction problem and prove its APX-hardness. We also present exact solutions for this formulation and develop heuristics. Using biological and synthetic datasets we present experimental results and compare them with the leading alternative software COLONY. We show that our results are competitive and allow half-sibling group reconstruction in the presence of polygamy, which is prevalent in nature.<\/jats:p>","DOI":"10.1142\/s0219720010004793","type":"journal-article","created":{"date-parts":[[2010,4,16]],"date-time":"2010-04-16T08:05:38Z","timestamp":1271405138000},"page":"337-356","source":"Crossref","is-referenced-by-count":11,"title":["COMBINATORIAL RECONSTRUCTION OF HALF-SIBLING GROUPS FROM MICROSATELLITE DATA"],"prefix":"10.1142","volume":"08","author":[{"given":"SAAD I.","family":"SHEIKH","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M\/C 152), Chicago, IL 60607, USA"}]},{"given":"TANYA Y.","family":"BERGER-WOLF","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M\/C 152), Chicago, IL 60607, USA"}]},{"given":"ASHFAQ A.","family":"KHOKHAR","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M\/C 152), Chicago, IL 60607, USA"}]},{"given":"ISABEL C.","family":"CABALLERO","sequence":"additional","affiliation":[{"name":"Department of Biological Sciences, University of Illinois at Chicago, SEL 1031 M\/C 067, 840 West Taylor Street, Chicago, IL 60607, USA"}]},{"given":"MARY V.","family":"ASHLEY","sequence":"additional","affiliation":[{"name":"Department of Biological Sciences, University of Illinois at Chicago, SEL 1031 M\/C 067, 840 West Taylor Street, Chicago, IL 60607, USA"}]},{"given":"WANPRACHA","family":"CHAOVALITWONGSE","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Rutgers University, CoRE Building, 96 Frelinghuysen Rd., Piscataway, NJ 08854, USA"}]},{"given":"CHUN-AN","family":"CHOU","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Rutgers University, CoRE Building, 96 Frelinghuysen Rd., Piscataway, NJ 08854, USA"}]},{"given":"BHASKAR","family":"DASGUPTA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M\/C 152), Chicago, IL 60607, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.2307\/2409206"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-5347(03)00225-8"},{"key":"rf3","first-page":"1231","volume":"8","author":"Queller D. C.","journal-title":"Mol. Ecol."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1046\/j.1365-294X.2003.01886.x"},{"key":"rf5","first-page":"1968","volume":"166","author":"Wang J.","journal-title":"Genetics"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.2307\/1400594"},{"key":"rf7","volume":"63","author":"Almudevar A.","journal-title":"Theoretical Population Biology"},{"key":"rf8","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1017\/S0016672302005669","volume":"79","author":"Thomas S. C.","journal-title":"Genetics. Res."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1080\/10556780600881829"},{"key":"rf11","author":"Chaovalitwongse W. A.","journal-title":"INFORMS Journal On Computing"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm219"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-294X.2006.02946.x"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1534\/genetics.108.100214"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1111\/j.1471-8286.2004.00796.x"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0044-8486(98)00479-7"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1017\/S0016672302006055"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"1961","DOI":"10.1093\/genetics\/155.4.1961","volume":"155","author":"Thomas S. C.","journal-title":"Genetics"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.002"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-294X.2005.02556.x"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1007\/s10641-006-9170-9"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00263-0"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720010004793","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T05:08:37Z","timestamp":1635224917000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720010004793"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":22,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S0219720010004793"],"URL":"https:\/\/doi.org\/10.1142\/s0219720010004793","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}