The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies [1]. The xorgenotype 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
Bonizzoni, P., Della Vedova, G., Dondi, R., Pirola, Y., & Rizzi, R. (2009). Pure Parsimony Xor Haplotyping. In Bioinformatics Research and Applications, 5th International Symposium (pp.186-197). Springer Verlag.
Citazione: | Bonizzoni, P., Della Vedova, G., Dondi, R., Pirola, Y., & Rizzi, R. (2009). Pure Parsimony Xor Haplotyping. In Bioinformatics Research and Applications, 5th International Symposium (pp.186-197). Springer Verlag. |
Tipo: | paper |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | Pure Parsimony Xor Haplotyping |
Autori: | Bonizzoni, P; Della Vedova, G; Dondi, R; Pirola, Y; Rizzi, R |
Autori: | |
Data di pubblicazione: | 2009 |
Lingua: | English |
Nome del convegno: | ISBRA - International Symposium on Bioinformatics Research and Applications - May 13-16 |
ISBN: | 978-3-642-01550-2 |
Serie: | LECTURE NOTES IN COMPUTER SCIENCE |
Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
conf-paper-09-isbra.pdf | Articolo principale | N/A | Administrator Richiedi una copia |