{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:54Z","timestamp":1761620994883,"version":"3.35.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. & Technol."],"published-print":{"date-parts":[[2004,1]]},"DOI":"10.1007\/bf02944784","type":"journal-article","created":{"date-parts":[[2008,9,16]],"date-time":"2008-09-16T01:23:22Z","timestamp":1221528202000},"page":"42-59","source":"Crossref","is-referenced-by-count":19,"title":["The complexity of checking consistency of pedigree information and related problems"],"prefix":"10.1007","volume":"19","author":[{"given":"Luca","family":"Aceto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens A.","family":"Hansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Ing\u00f3lfsd\u00f3ttir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacob","family":"Johnsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Knudsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02944784_CR1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1038\/75514","volume":"20","author":"Daniel Fanner Gudbjartsson","year":"2000","unstructured":"Daniel Fanner Gudbjartsson, K Jonasson, C A Kong. Fast multipoint linkage calculation with Allegro.Nature Genetics, 2000, 20: 12\u201313.","journal-title":"Nature Genetics"},{"key":"BF02944784_CR2","first-page":"1347","volume":"58","author":"Leonid Kruglyak","year":"1996","unstructured":"Leonid Kruglyak, Mark J Daly, Mary Pat Reeve-Daly, Eric S Lander. Parametric and nonparametric linkage analysis: A unified multipoint approach.American Journal of Human Genetics, 1996, 58: 1347\u20131363.","journal-title":"American Journal of Human Genetics"},{"key":"BF02944784_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1038\/ng786","volume":"30","author":"G R Abecasis","year":"2002","unstructured":"Abecasis G R, Cherny S Set al. Merlin: Rapid analysis of dense genetic maps using sparse gene flow trees.Nature Genetics, 2002, 30: 97\u2013101.","journal-title":"Nature Genetics"},{"key":"BF02944784_CR4","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1086\/301904","volume":"63","author":"Jeffrey R O'Connell","year":"1998","unstructured":"Jeffrey R O'Connell, Daniel E Weeks. Pedcheck: A program for identification of genotype incompabibilities in linkage analysis.American Journal of Human Genetics, 1998, 63: 259\u2013266.","journal-title":"American Journal of Human Genetics"},{"key":"BF02944784_CR5","unstructured":"deCode News Center, November 2001. http:\/\/www.decode.com\/news\/releases\/"},{"key":"BF02944784_CR6","unstructured":"William S Klug, Michael R Cummings. Concepts of Genetics. Prentice Hall, 5th Edition, 1997."},{"key":"BF02944784_CR7","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1086\/338920","volume":"70","author":"Eric Sobel","year":"2002","unstructured":"Eric Sobel, Jeanette C Pap, Kenneth Lange Detection and integration of genotyping errors in statistical genetics.American Journal of Human Genetics, 2002, 70: 496\u2013508.","journal-title":"American Journal of Human Genetics"},{"key":"BF02944784_CR8","unstructured":"Jan Dohrmann. M\u0153nd. vil vide. hvem de er far til.Nordjyske, 2002. (In Danish)"},{"key":"BF02944784_CR9","first-page":"33","volume":"2334","author":"Mick Hamer","year":"2002","unstructured":"Mick Hamer. Back to your roots.New Scientist, 2002, 2334: 33\u201336.","journal-title":"New Scientist"},{"key":"BF02944784_CR10","unstructured":"Human Genome Diversity Project, March 2002, http:\/\/www.stanford.edu\/group\/morrinsthgdp.html."},{"key":"BF02944784_CR11","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1086\/302663","volume":"65","author":"Jeffrey R O'Connell","year":"1999","unstructured":"Jeffrey R O'Connell, Daniel E Weeks. An optimal algorithm for automatic genotype elimination.American Journal of Human Genetics, 1999, 65: 1733\u20131740.","journal-title":"American Journal of Human Genetics"},{"key":"BF02944784_CR12","unstructured":"Christos H Papadinitriou.Computational Complexity. Addison Wesley, 1995."},{"key":"BF02944784_CR13","series-title":"Technical Report CSE-99-8","volume-title":"On the complexity of fundamental computational problems in pedigree analysis","author":"Antonio Piccolboni","year":"1999","unstructured":"Antonio Piccolboni, Dan Gusfied. On the complexity of fundamental computational problems in pedigree analysis. Technical Report CSE-99-8, Computer Science Department, University of California, Davis, September 1999. Revised version to appear in theJournal of Computational Biology."},{"key":"BF02944784_CR14","first-page":"250","volume":"40","author":"Kenneth Lange","year":"1987","unstructured":"Kenneth Lange, Tushar Madhu Goaradia. An algorithm for automatic genotype elimination.American Journal of Human Genetics, 1987, 40: 250\u2013256.","journal-title":"American Journal of Human Genetics"},{"key":"BF02944784_CR15","doi-asserted-by":"crossref","unstructured":"Jing Li, Tao Jiang. Efficient rule-based haplotyping algorithms for pedigree data [extended abstract]. InProc. RECOMB'08, Berlin, Germany, ACM, April 10\u201313, 2003, pp.197\u2013206.","DOI":"10.1145\/640075.640101"},{"issue":"1","key":"BF02944784_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/cmb.1998.5.27","volume":"5","author":"Bonnie Berger","year":"1998","unstructured":"Bonnie Berger, Tom Leighton. Protein folding in the hydrophobic-hydrophilic (hp) model is NP-completeJournal of Computational Biology, 1998, 5(1): 27\u201340.","journal-title":"Journal of Computational Biology"},{"key":"BF02944784_CR17","doi-asserted-by":"crossref","unstructured":"Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis. On the complexity of protein folding (extended abstract). InProc. the Thirtieth Annual ACM Symp. Theory of Computing, ACM Press, 1998, pp.597\u2013603.","DOI":"10.1145\/276698.276875"},{"key":"BF02944784_CR18","unstructured":"Jens A Hansen, Jacob Johnsen, John Knudsen. Computational complexity of consistency checking [thesis]. Department of Computer Science, Aalborg University, June 2002. Available at http:\/\/www.cs.auc.dk\/~luca\/PAPERS\/hjk02.ps.gz."},{"key":"BF02944784_CR19","unstructured":"Daniel Fanner Gudbjartsson.Multipoint Linkage Analysis Based on Allele Sharing Models [dissertation]. Institute of Statistics and Decision Sciences, Duke University, 2000."},{"key":"BF02944784_CR20","doi-asserted-by":"crossref","unstructured":"Jurg Ott. Analysis of Human Genetic Linkage. The Johns Hopkins University Press, 3rd Edition, 1999.","DOI":"10.56021\/9780801861406"},{"key":"BF02944784_CR21","unstructured":"Lynn B Jorde, John C Carey, Michael J Bamshad, Raymond L White.Medical Genetics, Mosby, 1999."},{"key":"BF02944784_CR22","unstructured":"Claus B\u00f8ttcher J\u00f8rgensen, Tuesday, April 9, 2002. Personal communication."},{"key":"BF02944784_CR23","unstructured":"Kenneth Lange. Monday. October 28, 2002. Personal communication."},{"key":"BF02944784_CR24","unstructured":"Tom Strachan, Andrew P Read.,Human Molecular Genetics 2 Wiley-Liss, 1999."},{"issue":"8","key":"BF02944784_CR25","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R E Bryant","year":"1986","unstructured":"Bryant R E. Graph-based algorithms for Boolean function manipulation.IEEE Trans. Computers, August 1986, C-35(8): 677\u2013691.","journal-title":"IEEE Trans. Computers"},{"key":"BF02944784_CR26","unstructured":"Jun Gu, Paul W, Purdom, John Franco, Benjamin W Wah. Algorithms for the satisfiability (SAT) problem: A survey. InSatisfiability Problem: Theory and Applications (Piscataway, NJ, 1996), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI, 1997, 35: 19\u2013151."},{"issue":"2","key":"BF02944784_CR27","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L G Valiant","year":"1979","unstructured":"Valiant L G. The complexity of computing the permanent.Theoret Comput. Sci., 1979, 8(2): 189\u2013201.","journal-title":"Theoret Comput. Sci."}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02944784.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02944784\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02944784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T23:09:24Z","timestamp":1738364964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02944784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["BF02944784"],"URL":"https:\/\/doi.org\/10.1007\/bf02944784","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"type":"print","value":"1000-9000"},{"type":"electronic","value":"1860-4749"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}