Paralelismo e heurística para o problema da mediana por Swap

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCunha, Luís Felipe Ignácio-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorAraújo, Leandro Santiago de-
Autor(es): dc.creatorNascimento, Thiago Lopes-
Data de aceite: dc.date.accessioned2024-07-11T17:47:31Z-
Data de disponibilização: dc.date.available2024-07-11T17:47:31Z-
Data de envio: dc.date.issued2024-02-27-
Data de envio: dc.date.issued2024-02-27-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/32468-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/757564-
Descrição: dc.descriptionRearranjo de genomas são eventos em que grandes blocos de DNA trocam pedaços durante a evolução. A análise desse tipo de vento é uma ferramenta para entender evolução genômica, baseado em encontrar o menor número de reordenamento que transformam um genoma em outro. De modo geral, são considerados mais de dois genomas e nós temos novos desafios. Problema da Mediana consiste em, dado três permutações e uma métrica de distância, determinar a permutação s que minimize a soma de todas as distâncias entre s e cada entrada. O conhecimento da mediana determina ancestralidade comum relativamente perto, sendo uma ferramenta útil para reconstrução de árvores filogenéticas. Diversas métricas já foram consideradas, algumas limitadas, como breakpoint, e muitas outras mais gerais em sequências que são muitas genéricas que permutações, como double-cut-and-join ou single-cut-and join nos DNAs. Nós trabalhamos com o problema da mediana por distância de swap em permutações. Visto que sua complexidade computacional ainda está em aberto, nós desenvolvemos e analisamos algoritmos força bruta (sequencial e paralelo) e heurísticas, e provamos condições sobre as permutações solução. Além disso, nós associamos soluções mediana e intervalos de conjuntos convexos, proposto por Cunha e Protti, em Journal of Computational Biology, 2019. O conceito de grafos convexos motiva as seguintes investigações: Uma permutação mediana pertence ao menor caminho entre cada par das permutações de entrada, i.e ela pertence à convexidade geodésica? Todas as permutações mediana assim como o fecho geodésico, formam todos os caminhos induzidos entre os três pares de permutações da entrada? Baseado nos nossos algoritmos propostos, nós somos capazes de responder essas perguntas-
Descrição: dc.descriptionGenome rearrangements are events where large blocks of DNA exchange pieces during evolution. The analysis of such events is a tool for understanding evolutionary genomics, based on finding the minimum number of rearrangements to transform one genome into another. In a general scenario, more than two genomes are considered and we have new challenges. Median problem consists of, given three permutations and a distance metric, determining a permutation s that minimizes the sum of the distances between s and each input. The knowledge of the median determines relatively close common ancestry, being a useful tool to reconstruct phylogenetic trees. Several metrics have been considered, some limited, as breakpoints, and others more general in sequences that are even more general than permutations, as double-cut-and-join or single-cut-or-join in DNAs. We deal with median problem over swap distances in permutations. Since its computational complexity is open, we develop and evaluate brute force (sequential and parallel) and heuristic algorithms, and prove conditions on permutations solution. In addition, we associate median solutions and interval convex sets, proposed by Cunha and Protti, in Journal of Computational Biology, 2019. The concept of graph convexity foments the following investigation: Does a median permutation belong to any shortest path between one of the pairs of input permutations, i.e. does it belong to the geodesic convexity? Do all median permutations along with the geodesic closure, form all induced paths between the three pairs of input permutations? Based on our proposed algorithms, we are able to answer those questions-
Descrição: dc.description34 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectRearranjo de genomas-
Palavras-chave: dc.subjectMediana-
Palavras-chave: dc.subjectSwap-
Palavras-chave: dc.subjectPermutações-
Palavras-chave: dc.subjectConvexidade-
Palavras-chave: dc.subjectBiologia computacional-
Palavras-chave: dc.subjectPermutação (Matemática)-
Palavras-chave: dc.subjectAlgoritmo-
Palavras-chave: dc.subjectMedian-
Palavras-chave: dc.subjectGenome rearrangements-
Palavras-chave: dc.subjectPermutations-
Palavras-chave: dc.subjectConvexity-
Título: dc.titleParalelismo e heurística para o problema da mediana por Swap-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.