Sorting by genome rearrangements problems

• Grant number: 19/27331-3
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: February 01, 2020
• End date: January 22, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: André Rodrigues Oliveira
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

Genome rearrangements are global mutations that affect large portions of the genomes, unlike point mutations that only affect a small number of nucleotides. The number of mutations occurring between genomes can be used as an indicator of the evolutionary distance between them. By the principle of parsimony, we assume that the evolutionary distance between two genomes is given by a minimum sequence of genome rearrangements needed to transform one genome into another. In general, problems involving genome rearrangements are computationally difficult to solve. This postdoctoral project proposes to advance the studies of NP-complete problems related to the area of genome rearrangement, focusing on theoretical applications such as approximation algorithms and heuristics. (AU)

Scientific publications

(22)

(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)

BRITO, KLAIRTON L.; OLIVEIRA, ANDRE R.; ALEXANDRINO, ALEXSANDRO O.; DIAS, ULISSES; DIAS, ZANONI. An improved approximation algorithm for the reversal and transposition distance considering gene order and intergenic sizes. Algorithms for Molecular Biology, v. 16, n. 1, DEC 29 2021. (19/27331-3, 15/11937-9, 17/12646-3, 13/08293-7)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Incorporating intergenic regions into reversal and transposition distances with indels. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 19, n. 6, SI, DEC 2021. (19/27331-3, 17/12646-3, 13/08293-7, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Labeled Cycle Graph for Transposition and Indel Distance. JOURNAL OF COMPUTATIONAL BIOLOGY, NOV 2021. (17/12646-3, 13/08293-7, 15/11937-9, 19/27331-3)

SIQUEIRA, GABRIEL; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ZANONI. Approximation algorithm for rearrangement distances considering repeated genes and intergenic regions. Algorithms for Molecular Biology, v. 16, n. 1, OCT 13 2021. (17/12646-3, 15/11937-9, 13/08293-7, 19/27331-3)

BRITO, KLAIRTON LIMA; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Reversals and transpositions distance with proportion restriction. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 19, n. 4, AUG 2021. (19/27331-3, 17/12646-3, 17/16246-0, 13/08293-7, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Genome Rearrangement Distance with Reversals, Transpositions, and Indels. JOURNAL OF COMPUTATIONAL BIOLOGY, v. 28, n. 3, p. 235-247, MAR 1 2021. (17/16246-0, 19/27331-3, 15/11937-9, 17/12646-3)

BRITO, KLAIRTON LIMA; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI; SETUBAL, JC; SILVA, WM. Sorting by Reversals and Transpositions with Proportion Restriction. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020, v. 12558, p. 12-pg., 2020-01-01. (19/27331-3, 13/08293-7, 17/12646-3, 15/11937-9)

BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; DIAS, ULISSES; DIAS, ZANONI. Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. N/A, p. 30-pg., 2023-04-27. (13/08293-7, 19/27331-3, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Reversal and Indel Distance With Intergenic Region Information. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 20, n. 3, p. 13-pg., 2023-05-01. (13/08293-7, 19/27331-3, 15/11937-9, 17/12646-3)

SIQUEIRA, GABRIEL; OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; DIAS, ZANONI; STADLER, PF; WALTER, MEMT; HERNANDEZ-ROSALES, M; BRIGIDO, MM. Heuristics for Cycle Packing of Adjacency Graphs for Genomes with Repeated Genes. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2021, v. 13063, p. 13-pg., 2021-01-01. (19/27331-3, 17/12646-3, 15/11937-9, 13/08293-7)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI; SCHERER, NM; DEMELO-MINARDI, RC. A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2022, v. 13523, p. 11-pg., 2022-01-01. (19/27331-3, 15/11937-9, 13/08293-7)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI; BANSAL, MS; CAI, Z; MANGUL, S. Transposition Distance Considering Intergenic Regions for Unbalanced Genomes. BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2022, v. 13760, p. 14-pg., 2022-01-01. (19/27331-3, 15/11937-9, 13/08293-7)

BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; DIAS, ULISSES; DIAS, ZANONI; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Reversal and Transposition Distance of Genomes Considering Flexible Intergenic Regions. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., 2021-01-01. (17/12646-3, 19/27331-3, 15/11937-9, 13/08293-7)

PINHEIRO, PEDRO OLIMPIO; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DE SOUZA, CID CARVALHO; DIAS, ZANONI; SETUBAL, JC; SILVA, WM. Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020, v. 12558, p. 12-pg., 2020-01-01. (19/25410-3, 13/08293-7, 19/27331-3, 17/12646-3, 15/11937-9)

BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; DIAS, ULISSES; DIAS, ZANONI; JIN, L; DURAND, D. A New Approach for the Reversal Distance with Indels and Moves in Intergenic Regions. COMPARATIVE GENOMICS (RECOMB-CG 2022), v. 13234, p. 16-pg., 2022-01-01. (19/27331-3, 13/08293-7, 15/11937-9)

OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI. Approximation algorithms for sorting by k-cuts on signed permutations. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 45, n. 1, p. 30-pg., 2023-01-01. (19/27331-3, 13/08293-7, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. On the Complexity of Some Variations of Sorting by Transpositions. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, v. 26, n. 9, p. 1076-1094, 2020. (13/08293-7, 15/11937-9, 19/27331-3, 17/12646-3)

OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI; JIN, L; DURAND, D. Sorting by k-Cuts on Signed Permutations. COMPARATIVE GENOMICS (RECOMB-CG 2022), v. 13234, p. 16-pg., 2022-01-01. (19/27331-3, 15/11937-9, 13/08293-7)

OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; BRITO, KLAIRTON LIMA; DIAS, ULISSES; DIAS, ZANONI. orting Permutations by Intergenic Operation. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 18, n. 6, p. 2080-2093, NOV 1 2021. (19/27331-3, 13/08293-7, 17/12646-3, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI. Reversal and Transposition Distance on Unbalanced Genomes Using Intergenic Information. JOURNAL OF COMPUTATIONAL BIOLOGY, v. 30, n. 8, p. 16-pg., 2023-05-24. (13/08293-7, 19/27331-3, 15/11937-9)

BRITO, KLAIRTON LIMA; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Genome Rearrangement Distance With a Flexible Intergenic Regions Aspect. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 20, n. 3, p. 13-pg., 2023-05-01. (13/08293-7, 19/27331-3, 15/11937-9)

OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; BRITO, KLAIRTON LIMA; BULTEAU, LAURENT; DIAS, ULISSES; DIAS, ZANONI. Sorting Signed Permutations by Intergenic Reversals. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 18, n. 6, p. 2870-2876, NOV 1 2021. (13/08293-7, 19/27331-3, 17/16246-0, 17/12646-3)