Generalization of string partition problems

• Grant number: 21/13824-8
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: June 01, 2022
• End date: February 28, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Gabriel Henriques Siqueira
• 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
• Associated scholarship(s): 22/13555-0 - Rearrangement distances in unbalanced genomes considering intergenic regions, BE.EP.DR

Abstract

The problem of minimum common string partition is a combinatorial optimization problem of fundamental importances given its theorical and practical aspect. Such problem has the goal of finding the minimum number of substrings necessary to compose two distinct strings changing only the order in which the substrings are concatenated. Many relations were established between variations of this problem and genome rearrangement problems. In more recent studies, rearrangement problems have been incorporating information regarding intergenic regions, that motivates the use of such structures in the partition problems. Besides, most know results for partition problems assume that both strings used as input for the problem are composed of the same characters, but there is a more general version of the problem that assumes strings with distinct sets of characters, there is, it is possible to exist characters present in only one of the strings. The goal of this work is to study the variation of minimum common string partition problems considering the generalizations involving intergenic region information and the presence of characters in only one of the strings. (AU)

Scientific publications

(4)

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

SIQUEIRA, GABRIEL; ALEXANDRINO, ALEXSANDRO OLIVEIRA; DIAS, ZANONI. Signed rearrangement distances considering repeated genes, intergenic regions, and indels. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 46, n. 2, p. 36-pg., 2023-09-01. (21/13824-8, 13/08293-7, 17/12646-3, 15/11937-9)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; SIQUEIRA, GABRIEL; BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Block Interchange and Reversal Distance on Unbalanced Genomes. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2023, v. 13954, p. 13-pg., 2023-01-01. (15/11937-9, 21/13824-8, 13/08293-7, 22/13555-0, 19/27331-3)

SIQUEIRA, GABRIEL; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ZANONI. Approximating Rearrangement Distances with Replicas and Flexible Intergenic Regions. BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2023, v. 14248, p. 14-pg., 2023-01-01. (13/08293-7, 21/13824-8, 22/13555-0)

SIQUEIRA, GABRIEL; OLIVEIRA, ANDRE RODRIGUES; ALEXANDRINO, ALEXSANDRO OLIVEIRA; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ZANONI. Assignment of orthologous genes in unbalanced genomes using cycle packing of adjacency graphs. Journal of Heuristics, v. 30, n. 5-6, p. 21-pg., 2024-05-31. (21/13824-8, 13/08293-7, 15/11937-9, 22/13555-0)