Problems of sorting permutations by fragmentation-weighted operations

• Grant number: 17/16871-1
• Support Opportunities: Scholarships in Brazil - Master
• Start date: December 01, 2017
• End date: February 28, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Alexsandro Oliveira Alexandrino
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Calculating the evolutionary distance between species is an important problem in Computational Biology, and for this we consider sets of mutations that alter large stretches of the genome, which we call genome rearrangements. A genome is represented as a permutation of integers, where each element corresponds to a conserved block (region of high similarity between the genomes to be compared). Due to algebraic properties of permutations, the problem of transforming one genome into another is equivalent to the problem of sorting permutations by rearrangement operations. The most common approach considers that all rearrangements have the same cost, so the goal is to find a minimal sequence of rearrangements that sorts the permutation. However, studies indicate that some rearrangement operations are more likely to occur than others, making approaches in which operations have different costs more realistic. In this weighted approach, the goal is to find a sequence that sorts the permutation, such that the sum of the rearrangements' costs of this sequence is minimal. This project presents a new version for the problem of sorting permutations by weighted operations, where the cost of an operation corresponds to the amount of fragmentation that the operation causes in the permutation. (AU)

Scientific publications

(11)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Sorting permutations by fragmentation-weighted operations. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 18, n. 2, APR 2020. (17/12646-3, 17/16871-1, 17/16246-0, 15/11937-9)

OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI; ALVES, R. Super Short Reversals on Both Gene Order and Intergenic Sizes. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018, v. 11228, p. 12-pg., 2018-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

OLIVEIRA, ANDRE RODRIGUES; BRITO, KLAIRTON LIMA; DIAS, ZANONI; DIAS, ULISSES; ALVES, R. Sorting by Weighted Reversals and Transpositions. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018, v. 11228, p. 12-pg., 2018-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

PEIXOTO, BRUNO MALVEIRA; AVILA, SANDRA; DIAS, ZANONI; ROCHA, ANDERSON; ACM. Breaking down violence: A deep-learning strategy to model and classify violence in videos. 13TH INTERNATIONAL CONFERENCE ON AVAILABILITY, RELIABILITY AND SECURITY (ARES 2018), v. N/A, p. 7-pg., 2019-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

RODRIGUES, CAROLINE MAZINI; PEREIRA, LUIS; ROCHA, ANDERSON; DIAS, ZANONI; IEEE. Image Semantic Representation for Event Understanding. 2019 IEEE INTERNATIONAL WORKSHOP ON INFORMATION FORENSICS AND SECURITY (WIFS), v. N/A, p. 6-pg., 2019-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 18/16548-9, 18/16214-3, 17/16871-1)

PEIXOTO, BRUNO; LAVI, BAHRAM; PEREIRA MARTIN, JOAO PAULO; AVILA, SANDRA; DIAS, ZANONI; ROCHA, ANDERSON; IEEE. TOWARD SUBJECTIVE VIOLENCE DETECTION IN VIDEOS. 2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), v. N/A, p. 5-pg., 2019-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

RODRIGUES, CAROLINE MAZINI; SORIANO-VARGAS, AUREA; LAVI, BAHRAM; ROCHA, ANDERSON; DIAS, ZANONI. Manifold Learning for Real-World Event Understanding. IEEE Transactions on Information Forensics and Security, v. 16, p. 2957-2972, 2021. (18/16548-9, 18/16214-3, 17/16246-0, 15/11937-9, 18/05668-3, 13/08293-7, 17/12646-3, 17/16871-1)

MIRANDA, GUILHERME HENRIQUE SANTOS; ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Approximation Algorithms for Sorting lambda-Permutations by lambda-Operations. ALGORITHMS, v. 14, n. 6, JUN 2021. (13/08293-7, 15/11937-9, 17/16871-1, 17/12646-3, 17/16246-0)

SANTOS MIRANDA, GUILHERME HENRIQUE; ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI; ALVES, R. Sorting lambda-Permutations by lambda-Operations. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018, v. 11228, p. 13-pg., 2018-01-01. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI; JANSSON, J; MARTINVIDE, C; VEGARODRIGUEZ, MA. Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations. ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018), v. 10849, p. 12-pg., 2018-01-01. (17/12646-3, 16/14132-4, 15/11937-9, 13/08293-7, 17/16871-1)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; SANTOS MIRANDA, GUILHERME HENRIQUE; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Approximation Algorithms for Sorting Permutations by Length-Weighted Short Rearrangements. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 12-pg., 2019-08-30. (17/12646-3, 15/11937-9, 13/08293-7, 17/16246-0, 17/16871-1)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

ALEXANDRINO, Alexsandro Oliveira. Sorting permutations by weighted operations. 2019. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.