M.Sc. Manuel Cáceres defends his doctoral thesis "Parameterized and Safe & Complete Graph Algorithms for Bioinformatics" on Tuesday the 3rd of October 2023 at 13 o'clock in the University of Helsinki Physicum building, Auditorium E204 (Gustaf Hällströmin katu 2, 2nd floor). His opponent is Professor Christian Komusiewicz (Friedrich Schiller University Jena, Germany) and custos Associate Professor Alexandru I. Tomescu (University of Helsinki). The defence will be held in English.
The thesis of Manuel Cáceres is a part of research done in the Department of Computer Science and in the Graph Algorithms team of the Algorithmic Bioinformatics group. His supervisor has been Associate Professor Alexandru I. Tomescu (University of Helsinki).
Parameterized and Safe & Complete Graph Algorithms for Bioinformatics
Given their versatility, nowadays graphs are a popular choice in Bioinformatics to model data, as in the case of pan-genomics, and to model problems, as in the case of multi-assembly. On the one hand, the increasing amount of data forming the pan-genome, constrains the running time of solutions to problems solved on them. On the other hand, there is a lack of theoretical tools intended to improve the quality of multi-assembly solutions when compared to their successful use in the classical genome-assembly problem.
In this thesis, we develop faster and more sophisticated solutions to graph problems used in Bioinformatics. We obtain our results by using the lens of parameterized algorithms and safe & complete algorithms.
In the first two papers, we propose the first parameterized linear time solutions for the problems of maximum antichain and minimum path cover. The algorithms use the width as the parameter, which has been observed to be small in pan-genomics. As such, for constant values of this parameter the running time of our solutions is optimal.
In the last two papers, we use the safe & complete framework on problems whose solution corresponds to a set of paths. Specifically, we present efficient safe & complete algorithms for the problems of path cover and flow decomposition, and provide proof-of-concept implementations showing the quality improvement obtained by our approach.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-9433-6.
Printed copies will be available on request from Manuel Cáceres: manuel.caceresreyes@helsinki.fi.