We study the computational complexity of the following haplotyping problem. Given a set of genotypes G, find a minimum cardinality set of haplotypes which explains G. Here, a genotype g is an n-ary string over the alphabet {A,B,-} and an haplotype h is an n-ary string over the alphabet {A,B}. A set of haplotypes H is said to explain G if for every g in G there are h_1, h_2 in H such that h_1 + h_2 = g. The position-wise sum h_1 + h_2 indicates the genotype which has a '-' in the positions where h_1 and h_2 disagree, and the same value as h_1 and h_2 where they agree. We show the APX-hardness of the problem even in the case the number of '-' symbols is at most 3 for every g in G. We give a $\sqrt{|G|}$-approximation algorithm for the general case, and a $2^{k-1}$-approximation algorithm when the number of '-' symbols is at most k for every g in G.

Haplotyping Populations: Complexity and Approximations / Lancia, Giuseppe; Rizzi, Romeo; Pinotti, Maria Cristina. - ELETTRONICO. - (2002), pp. 1-12.

### Haplotyping Populations: Complexity and Approximations

#### Abstract

We study the computational complexity of the following haplotyping problem. Given a set of genotypes G, find a minimum cardinality set of haplotypes which explains G. Here, a genotype g is an n-ary string over the alphabet {A,B,-} and an haplotype h is an n-ary string over the alphabet {A,B}. A set of haplotypes H is said to explain G if for every g in G there are h_1, h_2 in H such that h_1 + h_2 = g. The position-wise sum h_1 + h_2 indicates the genotype which has a '-' in the positions where h_1 and h_2 disagree, and the same value as h_1 and h_2 where they agree. We show the APX-hardness of the problem even in the case the number of '-' symbols is at most 3 for every g in G. We give a $\sqrt{|G|}$-approximation algorithm for the general case, and a $2^{k-1}$-approximation algorithm when the number of '-' symbols is at most k for every g in G.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Haplotyping Populations: Complexity and Approximations / Lancia, Giuseppe; Rizzi, Romeo; Pinotti, Maria Cristina. - ELETTRONICO. - (2002), pp. 1-12.
Lancia, Giuseppe; Rizzi, Romeo; Pinotti, Maria Cristina
File in questo prodotto:
File
80.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Dimensione 963.32 kB
Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358642
• ND
• ND
• ND