Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/24886| Type: | TCC |
| Title: | Modelos de Programação Linear Inteira para o Problema de Rearranjo de Genomas por Transposição |
| Authors: | Alexandrino, Alexsandro Oliveira |
| Advisor: | Souza, Críston Pereira de |
| Co-advisor: | Freitas, Lucas Ismaily B. |
| Keywords: | Programação linear;Programação inteira;Biologia computacional;Otimização combinatória |
| Issue Date: | 2016 |
| Citation: | ALEXANDRINO, Alexsandro Oliveira. Modelos de programação linear inteira para o problema de rearranjo de genomas por transposição. 2016. TCC (graduação em Engenharia de Software) - Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2016. |
| Abstract in Brazilian Portuguese: | A evolução biológica é o conjunto de mudanças nas características hereditárias de uma população no decorrer do tempo. Um problema na área de biologia computacional é calcular a distância evolucionária entre espécies, sendo que na distância evolucionária consideramos apenas conjuntos de mutações que alteram pedaços do genoma, ao qual chamamos de rearranjos de genomas (SETUBAL; MEIDANIS, 1997). Na literatura estudada, os dois tipos de rearranjo mais observados são os de reversão e transposição. Este trabalho tem o objetivo de criar um novo modelo de programação linear inteira para o problema de rearranjo de genomas por transposição, e o de comparar com os modelos existentes na literatura. Também são propostas desigualdades válidas com o objetivo de melhorar a eficiência dos modelos, e aplicada a técnica de relaxação lagrangeana na tentativa de melhorar os limites inferiores. Concluímos que o modelo definido por Lancia, Rinaldi e Serafini (2015) possui melhores resultados práticos. As propostas de melhorias não trazem melhoras significativas aos modelos. |
| Abstract: | The biological evolution is the set of changes in the heritable characteristics in a population over time. A problem in computational biology is to calculate the evolutionary distance among species, being that the evolutionary distance considers only sets of mutations that updates pieces of the genome, which we call genome rearrangements (SETUBAL; MEIDANIS, 1997). In the studied literature, the two most observed kinds of genome rearrangements are reversal and transposition. This study aims to create a new integer linear programming model for the genome rearrangement problem, and to compare it with the current models in literature. It is also proposed the addition of valid inequalities to improve the efficiency of the models, and it is applied the lagrangian relaxation to improve the lower bounds. We conclude that the model defined by Lancia, Rinaldi and Serafini (2015) has better practical results. The proposed improvements do not bring significant improvements to the models. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/24886 |
| Appears in Collections: | ENGENHARIA DE SOFTWARE - QUIXADÁ - TCC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2016_tcc_aoalexandrino.pdf | 802,39 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.