Reconstructing phylogenies from genotype sequence collections: Merging the Pure Parsimony Haplotyping problem with the Haplotype Phylogeny problem

The information provided by haplotype and phylogenetic estimation methods is of central importance e.g., in the diagnosis of the genetic causes associated to major human diseases as well as in the design of new therapeutical targets and personalized treatments. Hence, the scientific community has devoted in recent times increasing research efforts on the development of more and more capable predictive models for haplotyping and phylogeny estimation. So far, the usual approach to the modeling of haplotyping and phylogeny estimation consisted in considering both problems separately and one (haplotyping) after the other (phylogeny estimation). This thesis investigates how to improve this approach by considering both problems simultaneously. In particular, in a first attempt we will focus on the merging of both problems with respect to the parsimony criterion of haplotype and phylogeny estimation and we will propose some alternative integer linear programming models to solve this new merged problem. We compare the performances of these formulations on a set of small real instances of both problems and we analyze the corresponding results. Our analysis shows that the proposed merging constitutes a viable way to carry out the analysis of fine-scale genetic data and definitely warrants additional research efforts.