Algoritmos para problemas de ordenação por reversões ou transposições, com aplicações em rearranjo de genomas

Author(s)

Gustavo Rodrigues Galvão

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2015-02-10

Examining board members

Zanoni Dias; Maria Emilia Machado Telles Walter; Yoshiko Wakabayashi; Eduardo Candido Xavier; Guilherme Pimentel Telles

• Advisor: Zanoni Dias

Abstract

During evolution, rearrangement events may alter the order and the orientation of the genes in a genome. The problem of finding the minimum sequence of rearrangements that transforms one genome into another is a well-studied problem that finds application in comparative genomics. Representing genomes as permutations, in which genes appear as elements, that problem can be reduced to the combinatorial problem of sorting a permutation using a minimum number of rearrangements. Such combinatorial problem, referred to as rearrangement sorting problem, varies according to the types of rearrangements considered. In this thesis, we focus on two types of rearrangements: reversals and transpositions. Many variants of the rearrangement sorting problem involving these rearrangements have been tackled in the literature and, for most of them, the best known algorithms are approximations or heuristics. For this reason, we present a tool, called GRAAu, to aid in the evaluation of the results produced by these algorithms. In addition, we present a general heuristic that can be used to improve the solutions provided by any non-optimal algorithm. Besides presenting GRAAu and the improvement heuristic, which have a more general appeal, we present contributions regarding specific variants of the rearrangement sorting problem. First, we consider the problem of sorting by transpositions and we present experimental and theoretical results regarding three approximation algorithms based on alternative approaches to the cycle graph, which is a standard tool for attacking the rearrangement sorting problem. Then, we turn our attention to variants involving short rearrangements. More precisely, we study five variants: (i) the problem of sorting a signed linear permutation by super short reversals, (ii) the problem of sorting a signed circular permutation by super short reversals, (iii) the problem of sorting a signed linear permutation by short reversals, (iv) the problem of sorting a signed linear permutation by super short rearrangements, and (v) the problem of sorting a signed linear permutation by short rearrangements. We present polynomial-time algorithms for problems (i), (ii) and (iv), a 5-approximation algorithm for problem (iii), and a 3-approximation algorithm for problem (v). We use the algorithm developed for problem (ii) to reconstruct the phylogeny of Yersinia genomes and compare the result with the phylogenies presented in previous works (AU)

• FAPESP's process: 14/04718-6 - Algorithms for rearrangement sorting problem
• Grantee: Gustavo Rodrigues Galvão
• Support Opportunities: Scholarships in Brazil - Doctorate