Dynamic programming and DNA sequence alignment algorithms

Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2019, Director: Miquel Bosch Gual[en] The goal of this work is to present dynamic programming, which is a mathematical field that solves optimisation problems based on multistage decisionmaking processes. First, its mathematical foundations are gradually built up based on the theorem of optimality, the functional equation and the principle of optimality. Next, the basic elements of the computational procedure are presented, including its most remarkable advantages and drawbacks in comparison to other more exhaustive computational methods. Finally, several up-to-date problems in bioinformatics are introduced in order to compare DNA and protein sequences, which is useful to find out unknown gene functions and compare the genome of different species. Computer algorithms to solve these problems have been written and attached to this work