AlPha: A Mixed Integer Linear Programming Approach for Genome Haplotyping - Archive ouverte HAL Access content directly
Master Thesis Year : 2020

AlPha: A Mixed Integer Linear Programming Approach for Genome Haplotyping

(1, 2)
1
2

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.
Fichier principal
Vignette du fichier
report_kerian_thuillier.pdf (1.18 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03127775 , version 1 (01-02-2021)

Identifiers

  • HAL Id : hal-03127775 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More