Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.unb.br/handle/10482/44748
Files in This Item:
File Description SizeFormat 
2022_LuizAugustoGarciadaSilva.pdf918,54 kBAdobe PDFView/Open
Title: Um novo algoritmo 1.375-aproximativo baseado em grupos de permutações para o Problema da Ordenação por Transposições
Authors: Silva, Luiz Augusto Garcia da
Orientador(es):: Walter, Maria Emília Machado Telles
Assunto:: Problema da ordenação por transposições
Sorting by transpositions
Ordenação por transposições
Rearranjos de genomas
Algoritmos de aproximação
Grupos de permutações
Issue Date: 9-Sep-2022
Citation: SILVA, Luiz Augusto Garcia da. Um novo algoritmo 1.375-aproximativo baseado em grupos de permutações para o Problema da Ordenação por Transposições. 2022. xiii, 67 f., il. Tese (Doutorado em Informática) — Universidade de Brasília, Brasília, 2022.
Abstract: O Problema da Ordenação por Transposições (SBT, sigla dos termos em língua inglesa Sorting By Transpositions) é um problema clássico em rearranjos de genoma. Em 2012, Bulteau, Fertin e Rusu provaram que o SBT é N P-difícil e o melhor algoritmo de aproximação com uma razão de 1.375 foi proposto em 2006 por Elias e Hartman. Seu algoritmo emprega simplificação, uma técnica usada para transformar uma permutação de entrada π em uma permutação simples πˆ, presumivelmente mais fácil de lidar. A permutação πˆ é obtida inserindo novos símbolos em π de forma que o limite inferior da distância de transposição de π seja mantido em πˆ. A simplificação garantidamente mantém o limite inferior, mas não a distância de transposição. A sequência de transposições que ordena πˆ pode ser “imitada” para ordenar π. Nesta tese, primeiro, mostramos que o algoritmo de Elias e Hartman (Algoritmo EH) pode requerer uma transposição extra acima da razão de aproximação de 1.375, dependendo de como a permutação de entrada é simplificada. Em seguida, usando uma abordagem algébrica, propomos um novo limite superior para a distância de transposição e um novo algoritmo de aproximação de 1.375 para o SBT, que não emprega simplificação e que garante a razão de aproximação de 1.375 para todo o grupo simétrico Sn. Implementamos o Algoritmo EH e o algoritmo proposto nesta tese. Em relação à implementação do Algoritmo EH, duas novas falhas foram identificadas e precisaram ser corrigidas. Testamos ambos os algoritmos com todas as permutações de tamanho n, 2 ≤ n ≤ 12. Os resultados mostraram que o Algoritmo EH excede a razão de aproximação de 1.375 para permutações com tamanho maior que 7. Em seguida, investigamos o desempenho de ambas as implementações em permutações longas de comprimento máximo 500. Por fim, apresentamos os resultados obtidos de uma investigação visando encontrar uma solução aproximada para o SBT, com razão inferior a 1.375. Ao procurar por resultados que permitissem o desenvolvimento de uma solução 1.33¯3-aproximativa, apenas não foram encontradas sequências de transposições, proporcionando essa razão, para 11 casos, de um universo de ≈ 545.000. A conclusão da investigação foi de que, para baixar a razão de aproximação 1.375, será necessário buscar por sequências de transposições muito longas, o que pode ser impraticável, dependendo dos recursos computacionais disponíveis e da técnica utilizada.
Abstract: Sorting by Transpositions (SBT) is a classical problem in genome rearrangements. In 2012, Bulteau, Fertin e Rusu have proven that the SBT is N P-hard, and the best approximation algorithm with a 1.375 ratio was proposed in 2006 by Elias and Hartman. Their algorithm employs simplification, a technique used to transform an input permutation π into a simple permutation πˆ, presumably easier to handle with. The permutation πˆ is obtained by inserting new symbols into π in a way that the lower bound of the transposition distance of π is kept on πˆ. The simplification is guaranteed to keep the lower bound, not the transposition distance. A sequence of operations sorting πˆ can be mimicked to sort π. In this thesis, we first show that the algorithm of Elias and Hartman (EH algorithm) may require one extra transposition above the approximation ratio of 1.375, depending on how the input permutation is simplified. Next, using an algebraic approach, we propose a new upper bound for the transposition distance and a new 1.375-approximation algorithm to solve SBT skipping simplification and ensuring the approximation ratio of 1.375 for all symmetric group Sn. We implemented our algorithm and EH’s. Regarding the implementation of the EH algorithm, two issues needed to be fixed. We tested both algorithms against all permutations of size n, 2 ≤ n ≤ 12. The results showed that the EH algorithm exceeds the approximation ratio of 1.375 for permutations with a size greater than 7. Next, we investigate the performance of both implementations on long permutations of maximum length 500. Finally, we present the results obtained from an investigation aimed at finding an approximate solution for SBT with an approximation ratio lower than 1.375. When looking for results that would allow the development of a 1.33¯3-approximate solution, we only have not found transposition sequences, providing this ratio, for 11 cases, out of an universe of ≈ 545, 000. The conclusion of the investigation was that, in order to lower the approximation ratio of 1.375, it will be necessary to search for very long transposition sequences, which may be impractical, depending on the available computational resources and the technique used.
Description: Tese (doutorado) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2022.
Licença:: A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
Appears in Collections:CIC - Doutorado em Informática (Teses)

Show full item record Recommend this item " class="statisticsLink btn btn-primary" href="/handle/10482/44748/statistics">



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.