Alinhamento múltiplo de sequências utilizando ant colony optimization e chaotic jump
Carregando...
Arquivos
Data
2021-09-08
Autores
Orientador
Zafalon, Geraldo Francisco Donegá 
Coorientador
Pós-graduação
Ciência da Computação - FC/FCT/IBILCE/IGCE 33004153073P2
Curso de graduação
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Tipo
Dissertação de mestrado
Direito de acesso
Acesso aberto
Resumo
Resumo (português)
Alinhamento múltiplo de sequências é uma das técnicas mais relevantes no contexto de bioinformática. Os sequenciadores modernos produzem um grande volume de dados que são posteriormente analisados por biólogos, biomédicos e profissionais da área genética. Devido a esse grande volume, estratégias computacionais são necessárias para auxiliar na análise dos dados, como por exemplo, os alinhamentos de sequências. A tarefa de alinhar sequências é um desafio computacional e biológico. Do ponto de vista biológico, os modelos são incompletos e não levam em consideração todos os aspectos estruturais e evolutivos das espécies. Além disso, do ponto de vista computacional, com os hardwares atuais, soluções exatas podem não ser obtidas em um tempo hábil. A alternativa prática é a utilização de heurísticas e modelos probabilísticos para se obter resultados com significância biológica, dentro de um tempo factível. Entretanto, heurísticas possuem a característica de se fixarem em pontos de máximo ou mínimo local e, deste modo, as soluções tornam-se sub-ótimas. Para amenizar esse problema recorre-se à utilização de estratégias híbridas e aplicação de estado caótico no algoritmo para deslocar a solução de um ponto no espaço de busca para outro. Portanto, o presente trabalho desenvolveu-se um novo método que, por meio de uma combinação entre as ferramentas KAlign e Clustal Ômega, produz um alinhamento inicial e efetua seu refinamento com otimização por colônia de formigas e chaotic jump. Houve a obtenção de 100% de melhores resultados quando comparados com a ferramenta MSA-GA e pelo menos 50% de melhores resultados quando comparados com as ferramentas KAlign e Clustal Ômega, para todas as famílias do benchmark utilizadas.
Resumo (inglês)
Multiple sequence alignment is one of the most relevant techniques in the bioinformatics field. The next generation sequencing technologies produces a large volume of data that is later analised by biologists, biomedicals and geneticists. Due to this huge volume, computational effort are necessary to aid in the data analisys, as an example, for sequence alignment. The sequence alignment task is a both a computational and biological challenge. From the biological perspective, the abstract models are incomplete and it does not take into consideration every structural and evolutionary aspect of the species. Besides, from the computational perspective, with currently available hardwares, exact solutions cannot be found in reasonable time. The practical alternative is to use heuristics and probabilistic models to reach results with biological meaning in a feasible time. However, heuristics has a particular characteristic of falling in local maxima or local minima and therefore the solutions that are found could be suboptimal. In order to ease this problem, one can appel to the usage of hybrid strategies and the application of chaotic state in the algorithm to jump the solution in the search space from one point to another. Thus, this works aims to intruduce a novel method that combines the KAlign and Clustal Omega tools in order to produce a seed alignment that will later be refined by Ant Colony Optimization and Chaotic Jump. The results showed us that for every test the ACO produced better alignments than the MSA-GA tool and at least for 50% of tests the proposed method was able to improved the initial alignments produced by the KAlign and Clustal Omega tools.
Descrição
Idioma
Português