Approximation Algorithms for Sorting lambda-Permutations by lambda-Operations

Autor(es)

Miranda, Guilherme Henrique Santos ^[1] ; Alexandrino, Alexsandro Oliveira ^[1] ; Lintzmayer, Carla Negri ^[2] ; Dias, Zanoni ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, BR-13083970 Campinas, SP - Brazil

^[2] Fed Univ ABC, Ctr Math Computat & Cognit, BR-09210580 Santo Andre, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: ALGORITHMS; v. 14, n. 6 JUN 2021.
• Citações Web of Science: 0

Resumo

Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented 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 rearrangements. This work investigates 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 whose elements are less than lambda positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each lambda-rearrangement must have size, at most, lambda, and, when applied to 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: 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: 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: 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
• 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: 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