Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies. Pedigrees allow to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In this work, we define a new HI problem on pedigrees, called MINIMUM-CHANGE HAPLOTYPE CONFIGURATION (MCHC) problem, that allows two types of genetic variation events: recombinations and mutations. Our new formulation extends the MINIMUM-RECOMBINANT HAPLOTYPE CONFIGURATION (MRHC) problem, that has been proposed in the literature to overcome the limitations of classic statistical haplotyping methods. Our contribution is twofold. First, we prove that the MCHC problem is APX-hard under several restrictions. Second, we propose an efficient and accurate heuristic algorithm for MCHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and can take advantage of additional knowledge about the input genotypes. Moreover, the L-reduction proves for the first time that MCHC and MRHC are O(nm/(log nm))-approximable on general pedigrees, where n is the pedigree size and m is the genotype length. Finally, we present an extensive experimental evaluation and comparison of our heuristic algorithm with several other state-of-the-art methods for HI on pedigrees.

Pirola, Y., Bonizzoni, P., Jiang, T. (2012). An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 9(1), 12-25 [10.1109/TCBB.2011.51].

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

PIROLA, YURI
Primo
;
BONIZZONI, PAOLA;
2012

Abstract

Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies. Pedigrees allow to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In this work, we define a new HI problem on pedigrees, called MINIMUM-CHANGE HAPLOTYPE CONFIGURATION (MCHC) problem, that allows two types of genetic variation events: recombinations and mutations. Our new formulation extends the MINIMUM-RECOMBINANT HAPLOTYPE CONFIGURATION (MRHC) problem, that has been proposed in the literature to overcome the limitations of classic statistical haplotyping methods. Our contribution is twofold. First, we prove that the MCHC problem is APX-hard under several restrictions. Second, we propose an efficient and accurate heuristic algorithm for MCHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and can take advantage of additional knowledge about the input genotypes. Moreover, the L-reduction proves for the first time that MCHC and MRHC are O(nm/(log nm))-approximable on general pedigrees, where n is the pedigree size and m is the genotype length. Finally, we present an extensive experimental evaluation and comparison of our heuristic algorithm with several other state-of-the-art methods for HI on pedigrees.
Articolo in rivista - Articolo scientifico
Genetics, L-reduction, Mendelian inheritance, classic statistical haplotyping methods, coding problem, computational challenge, genetic variation events, haplotype inference, heuristic algorithm, minimum-change haplotype configuration problem, minimum-recombinant haplotype configuration problem, pedigree size, population data, state-of-the-art methods
English
12
25
14
Pirola, Y., Bonizzoni, P., Jiang, T. (2012). An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 9(1), 12-25 [10.1109/TCBB.2011.51].
Pirola, Y; Bonizzoni, P; Jiang, T
File in questo prodotto:
File Dimensione Formato  
journ-art-12-tcbb-a.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 1.26 MB
Formato Adobe PDF
1.26 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/25954
Citazioni
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
Social impact