Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies, such as functional genomics, pharmacogenetics and population genetics. Pedigrees have been shown a valuable data that allows us to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In order to overcome the limitations of classic statistical haplotyping methods, a combinatorial formulation of the HI problem on pedigrees has been proposed in the literature, called Minimum-Recombinant Haplotype Configuration (MRHC) problem, that allows a single type of genetic variation events, namely recombinations. In this work, we define a new problem, called Minimum-Change Haplotype Configuration (MRHC), that extends the MRHC formulation by allowing also a second type of natural variation events: mutations. We propose an efficient and accurate heuristic algorithm for MRHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and it can take advantage of additional knowledge about the input genotypes, such as the presence of recombination hotspots and different rates of recombinations and mutations. 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 under several simulated scenarios. © 2010 Springer-Verlag.

Pirola, Y., Bonizzoni, P., Jiang, T. (2010). Haplotype Inference on Pedigrees with Recombinations and Mutations. In Algorithms in Bioinformatics, 10th International Workshop, WABI 2010, Liverpool, UK, September 6-8, 2010. Proceedings (pp.148-161). Springer [10.1007/978-3-642-15294-8_13].

Haplotype Inference on Pedigrees with Recombinations and Mutations

PIROLA, YURI
Primo
;
BONIZZONI, PAOLA;
2010

Abstract

Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies, such as functional genomics, pharmacogenetics and population genetics. Pedigrees have been shown a valuable data that allows us to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In order to overcome the limitations of classic statistical haplotyping methods, a combinatorial formulation of the HI problem on pedigrees has been proposed in the literature, called Minimum-Recombinant Haplotype Configuration (MRHC) problem, that allows a single type of genetic variation events, namely recombinations. In this work, we define a new problem, called Minimum-Change Haplotype Configuration (MRHC), that extends the MRHC formulation by allowing also a second type of natural variation events: mutations. We propose an efficient and accurate heuristic algorithm for MRHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and it can take advantage of additional knowledge about the input genotypes, such as the presence of recombination hotspots and different rates of recombinations and mutations. 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 under several simulated scenarios. © 2010 Springer-Verlag.
Si
paper
algorithms, haplotype inference, pedigree, recombinations, linear equations
English
International Workshop on Algorithms in Bioinformatics (WABI)
9783642152931
Pirola, Y., Bonizzoni, P., Jiang, T. (2010). Haplotype Inference on Pedigrees with Recombinations and Mutations. In Algorithms in Bioinformatics, 10th International Workshop, WABI 2010, Liverpool, UK, September 6-8, 2010. Proceedings (pp.148-161). Springer [10.1007/978-3-642-15294-8_13].
Pirola, Y; Bonizzoni, P; Jiang, T
File in questo prodotto:
File Dimensione Formato  
conf-paper-10-wabi.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 239.45 kB
Formato Adobe PDF
239.45 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/17146
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact