Skip to Main content Skip to Navigation
Master thesis

AlPha: A Mixed Integer Linear Programming Approach for Genome Haplotyping

Kerian Thuillier 1, 2
2 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Background: Nowadays, biological samples often contain dna of several species or individuals. When sequenced, we loose the origin of each fragments of dna and their position on the molecule. The problem of associating a dna fragment to a version of the genome and to find its position is called the haplotyping problem. Results: In this report, we present two new Mixed Integer Linear Programming (milp) methods based on multicommodity-flow to solve this problem. Unlike previous approaches, the resolution avoid the use of heuristics by using global optimisation. Conclusion: We do not currently known the quality of our results. However, proposed a comparison between the solving time complexity of our two milp models. We also proposed an experimental protocol to test the solution quality.
Document type :
Master thesis
Complete list of metadata

https://hal.inria.fr/hal-03127775
Contributor : Rumen Andonov Connect in order to contact the contributor
Submitted on : Monday, February 1, 2021 - 4:36:27 PM
Last modification on : Wednesday, November 3, 2021 - 8:09:25 AM
Long-term archiving on: : Sunday, May 2, 2021 - 7:47:23 PM

File

report_kerian_thuillier.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03127775, version 1

Citation

Kerian Thuillier. AlPha: A Mixed Integer Linear Programming Approach for Genome Haplotyping. Bioinformatics [q-bio.QM]. 2020. ⟨hal-03127775⟩

Share

Metrics

Les métriques sont temporairement indisponibles