The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. 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. Furthermore, we show that the problem has a polynomial time k-approximation, where k is the maximum number of xor-genotypes containing a given single nucleotide polymorphisms (SNP). Finally, we propose a heuristic and produce an experimental analysis showing that it scales to real-world large instances taken from the HapMap project

Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Pirola, Y., Rizzi, R. (2010). Pure parsimony xor haplotyping. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 7(4), 598-610 [10.1109/TCBB.2010.52].

Pure parsimony xor haplotyping

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

Abstract

The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. 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. Furthermore, we show that the problem has a polynomial time k-approximation, where k is the maximum number of xor-genotypes containing a given single nucleotide polymorphisms (SNP). Finally, we propose a heuristic and produce an experimental analysis showing that it scales to real-world large instances taken from the HapMap project
Articolo in rivista - Articolo scientifico
Algorithms; approximation algorithms; graph representation.; haplotype resolution; pure parsimony;
English
598
610
13
Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Pirola, Y., Rizzi, R. (2010). Pure parsimony xor haplotyping. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 7(4), 598-610 [10.1109/TCBB.2010.52].
Bonizzoni, P; DELLA VEDOVA, G; Dondi, R; Pirola, Y; Rizzi, R
File in questo prodotto:
File Dimensione Formato  
journ-art-10-tcbb.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 1.46 MB
Formato Adobe PDF
1.46 MB 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/19834
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
Social impact