Sorting lambda-Permutations by lambda-Operations

Autor(es)

Santos Miranda, Guilherme Henrique ; Alexandrino, Alexsandro Oliveira ; Lintzmayer, Carla Negri ; Dias, Zanoni ; Alves, R

• Tipo de documento: Artigo Científico
• Fonte: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018; v. 11228, p. 13-pg., 2018-01-01.

Resumo

The understanding of how different two organisms are is one of the challenging tasks of modern science. A well accepted way to estimate the evolutionary distance between two organisms is estimating the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. If we represent genomes as permutations, we can represent one as the identity permutation and so we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of operations. In this work, we study the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value lambda, the problem now is how to sort a lambda-permutation, which is a permutation where all elements are less than lambda positions away from their correct places (regarding the identity), by applying the minimum number of operations. Each lambda-operation must have size at most. and, when applied over a lambda-permutation, the result should also be a lambda-permutation. We present algorithms with approximation factors of O(lambda(2)), O(lambda), and O(1) for the problems of Sorting lambda-Permutations by lambda-Reversals, by lambda-Transpositions and by both operations. (AU)

• Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
• Beneficiário: Anderson de Rezende Rocha
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
• Beneficiário: Munir Salomao Skaf
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
• Beneficiário: Sandra Eliza Fontes de Avila
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 17/16871-1 - Problemas de ordenação de permutações por operações ponderadas pelo número de fragmentações
• Beneficiário: Alexsandro Oliveira Alexandrino
• Modalidade de apoio: Bolsas no Brasil - Mestrado