Abstract
The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies [1]. The xor-genotype data is a cheaply obtainable type of data distinguishing heterozygous from homozygous sites without identifying the homozygous alleles. In this paper we propose a formulation based on a well known model used in haplotype inference: pure parsimony. We exhibit exact solutions of the problem by providing polynomial-time algorithms for some restricted cases and a fixed-parameter algorithm for the general case. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Moreover we propose a heuristic and produce an experimental analysis showing that it scales to real-world instances taken from the HapMap project.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barzuza, T., Beckmann, J.S., Shamir, R., Pe’er, I.: Computational problems in perfect phylogeny haplotyping: Xor-genotypes and tag SNPs. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 14–31. Springer, Heidelberg (2004)
Barzuza, T., Beckmann, J.S., Shamir, R., Pe’er, I.: Computational problems in perfect phylogeny haplotyping: Typing without calling the allele. IEEE/ACM Trans. on Comput. Biol. and Bioinform. 5(1), 101–109 (2008)
Bitner, J.R., Ehrlich, G., Reingold, E.M.: Efficient generation of the binary reflected Gray code and its applications. Comm. of the ACM 19(9), 517–521 (1976)
Bixby, R.E., Wagner, D.K.: An almost linear-time algorithm for graph realization. Mathematics of Operations Research 13, 99–123 (1988)
Brown, D.G., Harrower, I.M.: Integer programming approaches to haplotype inference by pure parsimony. IEEE/ACM Trans. on Comput. Biol. and Bioinform. 3(2), 141–154 (2006)
Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2005)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)
Fredkin, E.: Trie memory. Comm. of the ACM 3(9), 490–499 (1960)
Fujishige, S.: An efficient PQ-graph algorithm for solving the graph realization problem. J. of Computer and System Science 21, 63–86 (1980)
Gusfield, D.: Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In: Proc. 6th RECOMB, pp. 166–175 (2002)
Gusfield, D.: Haplotyping by pure parsimony. In: Baeza-Yates, R., Chávez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 144–155. Springer, Heidelberg (2003)
Lancia, G., Pinotti, M.C., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS J. Comp. 16(4), 348–359 (2004)
Savage, C.: A survey of combinatorial Gray codes. SIAM Rev. 39(4), 605–629 (1997)
The International HapMap Consortium. A haplotype map of the human genome. Nature 437(7063), 1299–1320 (2005)
Tutte, W.T.: An algorithm for determining whether a given binary matroid is graphic. Proc. of the American Mathematical Society 11(6), 905–917 (1960)
van Iersel, L., Keijsper, J., Kelk, S., Stougie, L.: Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems. IEEE/ACM Trans. on Comput. Biol. and Bioinform. 5(2), 301–312 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonizzoni, P., Della Vedova, G., Dondi, R., Pirola, Y., Rizzi, R. (2009). Pure Parsimony Xor Haplotyping. In: Măndoiu, I., Narasimhan, G., Zhang, Y. (eds) Bioinformatics Research and Applications. ISBRA 2009. Lecture Notes in Computer Science(), vol 5542. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01551-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-01551-9_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01550-2
Online ISBN: 978-3-642-01551-9
eBook Packages: Computer ScienceComputer Science (R0)