{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:06:30Z","timestamp":1792155990703,"version":"4.4.0"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Computational inference of haplotypes from genotypes has attracted a great deal of attention in the computational biology community recently, partially driven by the international HapMap project. In this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree, assuming that the hereditary process was free of mutations (i.e., the Mendelian law of inheritance) and recombinants. The problem has recently been formulated as a system of linear equations over the finite field of $F(2)$ and solved in $O(m^3n^3)$ time by using standard Gaussian elimination, where m is the number of loci (or markers) in a genotype and n the number of individuals in the pedigree. We give a much faster algorithm with running time $O(mn^2+n^3\\log^2n\\log\\log n)$. The key ingredients of our construction are (i) a new system of linear equations based on some spanning tree of the pedigree graph and (ii) an efficient method for eliminating redundant equations in a system of $O(mn)$ linear equations over $O(n)$ variables. Although such a fast elimination method is not known for general systems of linear equations, we take advantage of the underlying pedigree graph structure and recent progress on low-stretch spanning trees.<\/jats:p>","DOI":"10.1137\/070687591","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T19:30:36Z","timestamp":1236195036000},"page":"2198-2219","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations"],"prefix":"10.1137","volume":"38","author":[{"given":"Jing","family":"Xiao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lirong","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1038\/ng786"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.genom.9.081307.164258"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Y. Chan, W. Chan, F. Chin, S. Fung, and M. Kao,\n                      Linear-time haplotype inference on pedigrees without recombinations\n                      , in Proceedings of the 6th Annual Workshop on Algorithms in Bioinformatics (WABI), 2006.","DOI":"10.1007\/11851561_6"},{"key":"R4","unstructured":"F. Chin and Q. Zhang,\n                      Haplotype Inference on Tightly Linked Markers in Pedigree Data\n                      , manuscript, 2005."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"F. Chin, Q. Zhang, and H. Shen,\n                      \n                        k\n                        -recombination haplotype inference in pedigrees\n                      \n                      , in Proceedings of the International Conference on Computational Science (ICCS), Springer, Berlin, 2005, pp. 985\u2013993.","DOI":"10.1007\/11428848_125"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1038\/ng1001-229"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"K. Doi, J. Li, and T. Jiang,\n                      Minimum recombinant haplotype configuration on tree pedigrees\n                      , in Proceedings of the 3rd Annual Workshop on Algorithms in Bioinformatics (WABI), Springer, Berlin, 2003, pp. 339\u2013353.","DOI":"10.1007\/978-3-540-39763-2_25"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"M. Elkin, Y. Emeky, D. A. Spielman, and S. Teng,\n                      Lower-stretch spanning trees\n                      , in Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005, pp. 494\u2013503.","DOI":"10.1145\/1060590.1060665"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"E. Eskin, E. Halperin, and R. M. Karp,\n                      Large scale reconstruction of haplotypes from genotype data\n                      , in Proceedings of the 7th Annual Conference on Research in Computational Molecular Biology (RECOMB), ACM, New York, 2003, pp. 104\u2013113.","DOI":"10.1145\/640075.640088"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1126\/science.1069424"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Giesbrecht, A. Lobo, and B. Saunders,\n                      Certifying inconsistency of sparse linear systems\n                      , in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, New York, 1998, pp. 113\u2013119.","DOI":"10.1145\/281508.281591"},{"key":"R13","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., The John Hopkins University Press, Baltimore, MD, 1996."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1038\/75514"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. Gusfield,\n                      Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions\n                      , in Proceedings of the 6th Annual Conference on Research in Computational Biology (RECOMB), ACM, New York, 2002, pp. 166\u2013175.","DOI":"10.1145\/565196.565218"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"D. Gusfield,\n                      An overview of combinatorial methods for haplotype inference\n                      , in Computational Methods for SNPs and Haplotype Inference, Lecture Notes in Comput. Sci. 2983, Springer, Berlin, 2004, pp. 9\u201325.","DOI":"10.1007\/978-3-540-24719-7_2"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"B. V. Halld\u00f3rsson, V. Bafna, N. Edwards, R. Lippert, S. Yooseph, and S. Istrail,\n                      A survey of computational methods for determining haplotypes\n                      , in Computational Methods for SNPs and Haplotype Inference, Lecture Notes in Comput. Sci. 2983, Springer, Berlin, 2004, pp. 26\u201347.","DOI":"10.1007\/978-3-540-24719-7_3"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1038\/nature02168"},{"key":"R19","first-page":"583","volume":"293","author":"Helmuth L.","year":"2001","journal-title":"3.0, Science"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1038\/hdy.2008.53"},{"key":"R21","first-page":"1347","volume":"58","author":"Kruglyak L.","year":"1996","journal-title":"Am. J. Hum. Genet.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9297","issn-type":"print"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"B. LaMacchia and A. Odlyzko,\n                      Solving large sparse linear systems over finite fields\n                      , in Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, Lecture Notes in Comput. Sci. 537, Springer, Berlin, 1990, pp. 109\u2013133.","DOI":"10.1007\/3-540-38424-3_8"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. Li and T. Jiang,\n                      Efficient rule-based haplotyping algorithm for pedigree data\n                      , in Proceedings of the 7th Annual Conference on Research in Computational Molecular Biology (RECOMB), ACM, New York, 2003, pp. 197\u2013206.","DOI":"10.1145\/640075.640101"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J. Li and T. Jiang,\n                      An exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming\n                      , in Proceedings of the 8th Annual Conference on Research in Computational Biology (RECOMB), ACM, New York, 2004, pp. 20\u201329.","DOI":"10.1145\/974614.974618"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2005.12.719"},{"key":"R26","unstructured":"X. Li, Y. Chen, and J. Li,\n                      An Efficient Algorithm for the Zero-Recombinant Haplotype Configuration Problem\n                      , manuscript, 2006."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"L. Liu, X. Chen, J. Xiao, and T. Jiang,\n                      Complexity and approximation of the minimum recombination haplotype configuration problem\n                      , in Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), Springer, Berlin, 2005, pp. 370\u2013379.","DOI":"10.1007\/11602613_38"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1997.4.535"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2272(2000)19:1+<::AID-GEPI10>3.0.CO;2-G"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1086\/340610"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/s00122-008-0820-5"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1086\/320110"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"E. Sobel, K. Lange, J. O'Connell, and D. Weeks,\n                      Haplotyping algorithms\n                      , in Genetic Mapping and DNA Sequencing, IMA Vol. Math Appl. 81, T. Speed and M. Waterman, eds., Springer, New York, 1996, pp. 89\u2013110.","DOI":"10.1007\/978-1-4612-0751-1_6"},{"key":"R34","first-page":"1323","volume":"58","author":"Sobel E.","year":"1996","journal-title":"Am. J. Hum. Genet.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9297","issn-type":"print"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1159\/000022890"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"R38","first-page":"356","volume":"41","author":"Wijsman E. M.","year":"1987","journal-title":"Am. J. Hum. Genet.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9297","issn-type":"print"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1086\/378205"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070687591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:01Z","timestamp":1787336341000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070687591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070687591"],"URL":"https:\/\/doi.org\/10.1137\/070687591","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}