Sorting lambda-Permutations by lambda-Operations

Author(s)

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

• Document type: Journal article
• Source: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018; v. 11228, p. 13-pg., 2018-01-01.

Abstract

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)

• FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
• Grantee: Anderson de Rezende Rocha
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
• Grantee: Munir Salomao Skaf
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 17/16246-0 - Sensitive media analysis through deep learning architectures
• Grantee: Sandra Eliza Fontes de Avila
• Support Opportunities: Regular Research Grants
• FAPESP's process: 17/16871-1 - Problems of sorting permutations by fragmentation-weighted operations
• Grantee: Alexsandro Oliveira Alexandrino
• Support Opportunities: Scholarships in Brazil - Master