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 [10.1007/978-3-642-01551-9_19].

Pure parsimony xor haplotyping

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;PIROLA, YURI;
2009

Abstract

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
No
paper
Scientifica
haplotyping
English
ISBRA - International Symposium on Bioinformatics Research and Applications - May 13-16
978-3-642-01550-2
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 [10.1007/978-3-642-01551-9_19].
Bonizzoni, P; DELLA VEDOVA, G; Dondi, R; Pirola, Y; Rizzi, R
File in questo prodotto:
File Dimensione Formato  
conf-paper-09-isbra.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 227.68 kB
Formato Adobe PDF
227.68 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/6280
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact