Full text
| |
| Author(s): |
Lucas Peres Oliveira
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2022-12-05 |
| Examining board members: |
João Meidanis;
Fábio Henrique Viduani Martinez;
Guilherme Pimentel Telles
|
| Advisor: | João Meidanis |
| Abstract | |
Under a computational perspective, genomes can be modelled as a collection of oriented segments, commonly known as synteny blocks, that represent conserved regions throughout evolution. Such regions are susceptible to large-scale mutations --- known as genome rearrangements --- that permute the synteny blocks in different configurations. Throughout the years, many rearrangement-based distance models were devised to calculate the evolutionary distance between genomes efficiently. Among them, the rank distance is based on modelling genomes as matrices and using the rank as a distance measure. The rank distance is the successor of the algebraic distance, a distance model that represents genomes as permutations and is grounded in the theory of permutation groups. Recently, the rank distance was extended to encompass insertion and deletion events --- indels. Although there exist algorithms to compute the rank efficiently in this context, many results in the matrix theory for genome rearrangements are still grounded in notions from the theory of permutation groups. In addition, the majority of the results are still theoretical, and little is known about the biological applicability of this extension of the rank distance. In this work, we consolidated and expanded the recent results regarding the extension of the rank distance that considers indel events. In particular, we introduce a data structure known as the column graph in order to devise simpler formulas to compute the rank in linear-time. This toolset allowed us to simplify the matrix theory for genome rearrangements and derived algorithms considerably. In addition, we performed experiments in phylogenetic inference using simulated data and real genomes to assess the biological applicability of the rank distance. Our results show that the rank distance is competitive when compared against the DCJ-Indel distance, a state-of-the-art method in genome rearrangements. Finally, we present a contribution to the study of enumeration of sorting scenarios under the rank distan (AU) | |
| FAPESP's process: | 20/00740-8 - Rank distance extensions and counting of sorting scenarios |
| Grantee: | Lucas Peres Oliveira |
| Support Opportunities: | Scholarships in Brazil - Master |