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
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: https://hdl.handle.net/10281/6280
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact