Defesa de Dissertação de Mestrado de Thiago Lopes Nascimento, 27/03/26, 15h, na sala 310 do Instituto de Computção
On the Complexity of Distance and Consensus in Computational Biology under 𝜎k and Subtree Movement
Resumo:
Biologia computacional é um campo interdisciplinar que combina modelos matemáticos, simulações e desenvolvimento de algoritmos para prover melhores explicações para sistemas biológicos complexos.
Esse campo é baseado em conseguir modelar problemas biológicos por meio de problemas computacionais, permitindo assim o uso da literatura relacionada à computação para resolver questões teóricas e exploratórias em biologia.
Esta dissertação tem como foco estudar três problemas distintos, todos relacionados à métricas em problemas envolvendo biologia computacional.
O estudo aborda temas como a determinação da complexidade de problemas de distância, além do desenvolvimento de algoritmos e experimentos.
Dois dos problemas estão relacionados à comparação de genomas, ou seja, métodos para quantificar quão próximos dois genomas estão entre si.
O primeiro deles busca determinar, por meio de uma redução polinomial, as complexidades da distância 𝜎k, variando o valor de k, considerando diferentes tipos de genomas, lineares, circulares, e mistos.
A distância de 𝜎k está relacionadas com outras métricas da área, tais como breakpoint e DCJ, sendo equivalente a 𝜎2 e 𝜎∞, respectivamente.
O segundo problema busca resolver instâncias mais genéricas envolvendo três ou mais genomas.
Para isso, consideram-se os problemas da Mediana e de Closest, que são interpretados como encontrar um genoma ancestral comum dado um conjunto de genomas como entrada.
Nesse caso ainda é utilizada a distância de 𝜎k, variando tanto o valor de k quanto a quantidade de genomas utilizados como entrada.
Para o último problema, o estudo muda a sua unidade comparativa de genomas para árvores de mutação.
Árvores de mutação, além de serem empregadas para análise da evolução de espécies e de vírus, também possuem um amplo uso no estudo da evolução de tumores.
Para isso, é desenvolvida uma operação chamada subtree movement (SBM), que visa metrificar a distância entre duas árvores de mutações.
Sobre essa operação, é feito um estudo sobre a sua complexidade, empregando novamente uma redução polinomial, além de desenvolver algoritmos polinomiais para determinar árvores que possam resumir determinado conjunto de entrada.
Por fim, foram feitos experimentos para validar as técnicas teóricas propostas.
Abstract:
Computational biology is a field that combines mathematical models, simulations, and algorithms to provide a better explanation of complex biological systems.
It aims to represent biological problems as computational problems, allowing for the use of the literature of computer science to address theoretical and exploratory questions in biology.
This dissertation aims to study three distinct problems, all related to metrics in computational biology.
The study addresses the distance complexity of the metrics used, as well as the development of algorithms and experiments.
Two problems involve answering questions related to comparative genomics, i.e., to quantify the distance between two genomes.
The first problem aims to determine, by applying a polynomial reduction, the complexity regarding the 𝜎k distance, assuming different values of $k$, as well as different types of genomes, such as, linear, circular, and mixed.
The 𝜎k distance is related to other metrics in this field, such as breakpoint and DCJ, which are equal to 𝜎2 and 𝜎∞, respectively.
The second problem aims at more general instances, involving three or more genomes.
Therefore, it considers the Median and Closest problems, which can be interpreted as finding an ancestral genome for the input genomes.
The distance measure considered for this problem remains the 𝜎k, assuming different values of k as well as a different number of input genomes.
For the last problem, the comparative unit changes from genomes to cell trees.
Cell trees, besides their functions for the analyses of species and virus evolution, it also has come to play an important role in tumour evolution.
In this dissertation, an operation called Subtree Movement (SBM) is developed, which aims to quantify the distance between two cell trees.
Furthermore, another polynomial reduction is applied to determine the complexity of SBM.
To conclude, algorithms were developed to determine consensus trees under this operation, as well as practical experiments to validate the proposed theoretical methods.
Banca examinadora:
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Luis Antonio Brasil Kowada, UFF
Dr. Alexsander Andrade de Melo, Mendelics Análise Genômica