Bioinformatics and Stringology
Genome Rearrangements is a branch of comparative genomics in bioinformatics.
We focus on genomes represented as sets of linear chromosomes and composed of sequences of unoriented genes. The structural rearrangements of chromosomal segments, such as inversions, translocations and transpositions can change the location (with respect to the chromosome), the order of genes.
We consider a model in which chromosomes are permutations of integers.
We are interested in the following problems: Sorting, Closest, Median and others.
Regarding string, related to Information Theory, our focus is on the Jumbled Pattern Matching problem, presented as follows: We are given a binary string w and asked to determine whether there exists a substring of size r and q 1s. Such substring could be represented by a Parikh vector of w, something that appears frequently in computational biology, as do jumbled patterns in the context of graphs and other structures.
We develop exact and approximation algorithms, NP-completeness proofs and FPT-tractability.
Graph Theory
Graphs are mathematical structures employed to model pairwise relations between objects. We investigate several problems, some of which are driven by practical motivations and some of which are motivated by their combinatorial relevance. Some of the problems we have contributions are:
Tree t-spanners: A tree t-spanner of a graph G is a spanning tree T of G in which any two adjacent vertices of G have distance at most t in T. We are interested in determining the smallest t for which G has a tree t-spanner.
We developed NP-completeness proofs for some graph classes, structural characterizations and efficient algorithms for variations and general related problems.
Yutsis Graphs: The Yutsis property of a simple, connected, and undirected graph is the property of partitioning its vertex set into two induced trees. Despite the fact that recognizing Yutsis graphs is NP-complete even on planar graphs, it is still possible to consider two even more challenging problems: (i) the recognition of k-Yutsis graphs, which are graphs that have their vertex sets partitioned into k induced trees, for a fixed k> 1; (ii) to find the minimum number of vertex-disjoint induced trees that cover all vertices of a graph G.
Tessellation Cover number: The tessellation cover number on graphs is an NP-hard optimization problem important to model staggered walks in quantum computation. A tessellation is a partition of the vertices of a graph into vertex disjoint cliques. The tessellation cover problem aims to determine the minimum number t of tessellations that covers all edges of a given graph G.
We present realtionship between this problem and well known coloring problems on graphs. Such as, vertex coloring, edge coloring and total coloring. Furthermore, we present a series of NP-completeness and efficient algorithms when restricting to graph classes.
Quantum Computing on optmization problems
Quantum Annealing (QA) is an instance of adiabatic computation that is relevant in the current Noisy Intermediate-Scale Quantum (NISQ) era. QA has been applied to combinatorial optimization problems that can be modeled as Quadratic Unconstrained Binary Optimization (QUBO) problems. In the last decade, QA has gained momentum due to the development of quantum hardware, such as D-Wave quantum computers and also by dedicated classical devices created by companies such as Fujitsu, Toshiba, and Fixstars Amplify. These systems are known as Ising Machines because they can solve problems stated as Hamiltonians in the Ising model. They are designed to solve a wide range of combinatorial problems, including several with industrial applications. In addition to being solvable on quantum annealing computers, problems formulated as QUBO instances are also of great theoretical interest, as several works developing QUBO formulations for problems in graph theory, such as coloring problems and maximum clique problem. We develop QUBO formulations for the following NP-hard problems: the determination of the maximum induced star on G, which yields a lower bound on the Tessellation Cover number, T(G); the determination of the chromatic number of the clique graph of G and the chromatic index of G, which yield upper bounds on T(G); the determination of T(G), by transforming t-tessellability to integer programming and then to QUBO.
Publications
Journals:
1. Cunha, Luís; SANTIAGO, LEANDRO ; SOUZA, FELIPE . Graph admissibility: Case generation and analysis by learning models. Journal of Computational Science, v. 78, p. 102281-102281, 2024.2. Cunha, Luís; MARCIANO, ERIKY ; MORAES, ANDERSON ; SANTIAGO, LEANDRO ; SANTOS, CARLOS . New parallelism and heuristic approaches for generating tree t-spanners in graphs. CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, v. 1, p. 1-36, 2024.
3. Couto, Fernanda ; CUNHA, L. F. I. ; JUVENTUDE, DANIEL ; SANTIAGO, LEANDRO . Strategies for generating tree spanners: Algorithms, heuristics and optimal graph classes. INFORMATION PROCESSING LETTERS, v. 177, p. 106265, 2022. Citações:1|1
4. ABREU, ALEXANDRE ; Cunha, Luís ; FIGUEIREDO, CELINA ; MARQUEZINO, FRANKLIN ; Posner, Daniel ; PORTUGAL, RENATO . Total tessellation cover: Bounds, hardness, and applications. DISCRETE APPLIED MATHEMATICS, v. 323, p. 149-161, 2022.
5. Couto, Fernanda ; CUNHA, LUÍS FELIPE I. . Hardness and efficiency on t-admissibility for graph operations. DISCRETE APPLIED MATHEMATICS, v. 304, p. 342-348, 2021. Citações:1|1
6. ABREU, A. ; CUNHA, L. ; DE FIGUEIREDO, C. ; KOWADA, L. ; MARQUEZINO, F. ; POSNER, D. ; PORTUGAL, R. . The graph tessellation cover number: Chromatic bounds, efficient algorithms and hardness. THEORETICAL COMPUTER SCIENCE, v. 801, p. 175-191, 2020. Citações:4|4
7. Couto, Fernanda ; CUNHA, LUÍS FELIPE I. . Hardness and efficiency on minimizing maximum distances in spanning trees. THEORETICAL COMPUTER SCIENCE, v. 00, p. 1-20, 2020. Citações:1|2
8. ABREU, A. S. ; Cunha, Luís ; Figueiredo, C.M.H. ; Kowada, Luis ; Marquezino, F. L. ; PORTUGAL, RENATO ; POSNER, D. . A Computational Complexity Comparative Study of Graph Tessellation Problems. THEORETICAL COMPUTER SCIENCE, v. 1, p. 1-17, 2020. Citações:1|1
9. Couto, Fernanda ; CUNHA, LUÍS FELIPE I. . Hardness and Efficiency on Minimizing Maximum Distances for Graphs With Few P4's and (k,l)-graphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 355-367, 2019. Citações:3
10. CUNHA, L. F. I.; FEIJÃO, PEDRO ; DOS SANTOS, VINÍCIUS F. ; KOWADA, LUIS ANTONIO B. ; FIGUEIREDO, C. M. H. . On the computational complexity of closest genome problems. DISCRETE APPLIED MATHEMATICS, p. 26-34, 2019. Citações:2|3
11. CUNHA, LUÍS FELIPE I.; PROTTI, FÁBIO . Genome Rearrangements on Multigenomic Models: Applications of Graph Convexity Problems. Journal of Computational Biology, v. 26, p. 1214-1222, 2019.
12. CUNHA, L. F. I.; PROTTI, F. . Closure of genomic sets: applications of graph convexity to genome rearrangement problems. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, v. 69, p. 285-292, 2018. Citações:2
13. CUNHA, L. F. I.; SANTOS, V. F. ; KOWADA, L. A. B. ; DE FIGUEIREDO, CELINA M. H. . Short block-move-CPP is NP-complete. MATEMATICA CONTEMPORANEA, v. 45, p. 134-142, 2017.
14. ABREU, A. S. ; CUNHA, L. F. I. ; FERNANDES, T. ; Figueiredo, C.M.H. ; KOWADA, L. A. B. ; Marquezino, F. L. ; POSNER, D. ; PORTUGAL, RENATO . Bounds and Complexity for the Tessellation Problem. MATEMATICA CONTEMPORANEA, v. 45, p. 22-30, 2017.
15. CUNHA, L. F. I.; KOWADA, L. A. B. ; FIGUEIREDO, C. M. H. . Sorting Separable permutations by restricted multi-break rearrangements. Matematica Contemporanea, v. 44, p. 1-10, 2015. Citações:1
16. CUNHA, LUÍS FELIPE I.; KOWADA, LUIS ANTONIO B. ; HAUSEN, RODRIGO DE A. ; DE FIGUEIREDO, CELINA M.H. . A Faster 1.375-Approximation Algorithm for Sorting by Transpositions. Journal of Computational Biology, v. 22, p. 1044-1056, 2015. Citações:4|3
17. CUNHA, LUÍS FELIPE I.; KOWADA, LUIS ANTONIO B. ; DE A. HAUSEN, RODRIGO ; DE FIGUEIREDO, CELINA M. H. . Advancing the Transposition Distance and Diameter through Lonely Permutations. SIAM Journal on Discrete Mathematics (Print), v. 27, p. 1682-1709, 2013. Citações:5|5
18. CUNHA, L. F. I.; KOWADA, L. A. B. . Upper bounds and exact values on transposition distance of permutations. Matematica Contemporanea, v. 39, p. 77-84, 2010.
Conferences:
2. SOUZA, F. ; SANTIAGO, L. ; CUNHA, L. . Gerando base de grafos não isomorfos com seus índices de extensão. In: Simpósio Brasileiro de Pesquisa Operacional, 2023, São José dos Campos. Anais do Simpósio Brasileiro de Pesquisa Operacional, 2023.
3. LOPES, T. ; PROTTI, F. ; SANTIAGO, L. ; CUNHA, L. . Paralelismo e Heurísticas para o problema da mediana por swap. In: Simpósio Brasileiro de Pesquisa Operacional, 2023, São José dos Campos. Anais do Simpósio Brasileiro de Pesquisa Operacional, 2023.
4. SANTOS, C. ; ZUDIO, A. ; SANTIAGO, L. ; CUNHA, L. . Heuristics for t-admissibility with complex network approach. In: Simpósio Brasileiro de Pesquisa Operacional, 2023, São José dos Campos. Anais do Simpósio Brasileiro de Pesquisa Operacional, 2023.
5. Couto, Fernanda ; CUNHA, L. ; BRITO, I. . Prismas complementares de cografos: uma classe 4-admissível sem exemplares 3-admissíveis. In: Simpósio Brasileiro de Pesquisa Operacional, 2020, João Pessoa. Simpósio Brasileiro de Pesquisa Operacional, 2020. p. 1-8.
6. MARINHO, A. R. A. F. ; Cunha, Luís ; NOGUEIRA, L. T. ; SOUZA, U. S. . Partitioning split graphs into two trees. In: Simpósio Brasileiro de Pesquisa Operacional, 2020, João Pessoa. Simpósio Brasileiro de Pesquisa Operacional, 2020. p. 1-8.
7. Couto, Fernanda ; Cunha, Luís ; POSNER, D. . Edge Tree Spanners. In: Cologne-Twente Workshop on Graphs and Combinatorial Optimization - CTW 2020, 2020, Online. Graphs and Combinatorial Optimization: from Theory to Applications - AIRO Springer Series. Cham: Springer, 2020. v. 5. p. 195-207.
8. JUVENTUDE, D. ; Couto, Fernanda ; CUNHA, LUÍS FELIPE I. . Uma análise experimental sobre a t-admissibilidade em grafos. In: LI Simpósio Brasileiro de Pesquisa Operacional, 2019, Limeira. LI Simpósio Brasileiro de Pesquisa Operacional, 2019. v. 2. p. 1-8.
9. Couto, Fernanda ; Cunha, Luís . Tree t-Spanners of a Graph: Minimizing Maximum Distances Efficiently. In: International Conference on Combinatorial Optimization and Applications - COCOA 2018, 2018, Atlanta. Lecture Notes in Computer Science. Cham: Springer, 2018. v. 11346. p. 46-61.
10. Cunha, Luís; DIEKMANN, Y. ; KOWADA, L. A. B. ; STOYE, J. . Identifying Maximal Perfect Haplotype Blocks. In: Brazilian Symposium on Bioinformatics - BSB 2018, 2018, Niterói. Advances in Bioinformatics and Computational Biology - Lecture Notes in Computer Science. Cham: Springer, 2018. v. 11228. p. 26-37.
11. ABREU, ALEXANDRE ; Cunha, Luís ; FERNANDES, T. ; FIGUEIREDO, C. M. H. ; KOWADA, L. A. B. ; MARQUEZINO, F. L. ; POSNER, D. ; PORTUGAL, RENATO . The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness. In: Latin American Symposium on Theoretical Informatics - LATIN 2018, 2018, Buenos Aires. LATIN 2018: Theoretical Informatics - Lecture Notes in Computer Science. Cham: Springer, 2018. v. 10807. p. 1-13.
12. CUNHA, L. F. I.; DANTAS, S. ; GAGIE, T. ; WITTLER, R. ; KOWADA, L. A. B. ; STOYE, J. . Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings. In: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017, Varsóvia. 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Dagstuhl, Germany: Leibniz International Proceedings in Informatics (LIPIcs), 2017. v. 78. p. 19:1-19:9.
13. CUNHA, L. F. I.. Limites para distância e diâmetro em rearranjo de genomas por transposições. In: XVII Concurso de Teses e Dissertações da SCB / Anais do Congresso da Sociedade Brasileira de Computação, 2014, Brasília. Anais do Congresso da Sociedade Brasileira de Computação, 2014.
14. Cunha, Luís; KOWADA, L. A. B. ; Rodrigo hausen ; Figueiredo, C.M.H. . A Faster 1.375-Approximation Algorithm for Sorting by Transpositions. In: International Workshop on Algorithms in Bioinformatics - WABI 2014, 2014, Wroclaw. Algorithms in Bioinformatics. WABI 2014 - Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2014. v. 8701. p. 26-37.
15. Cunha, Luís; KOWADA, L. A. B. ; Rodrigo hausen ; FIGUEIREDO, C. M. H. . On the 1.375-Approximation Algorithm for Sorting by Transpositions in O(n logn) Time. In: Brazilian Symposium on Bioinformatics - BSB 2013, 2013, Pernambuco. Advances in Bioinformatics and Computational Biology - Lecture Notes in Computer Science. Cham: Springer, 2013. v. 8213. p. 126-135.
16. CUNHA, L.; KOWADA, L. A. B. ; Rodrigo hausen ; FIGUEIREDO, C. M. H. . Transposition Diameter and Lonely Permutations. In: Brazilian Symposium on Bioinformatics - BSB 2012, 2012, Campo Grande. Advances in Bioinformatics and Computational Biology - Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2012. v. 7409. p. 1-12.
If you are interested in any of my research topics and would like to do your IC, TCC, Master's or PhD studies under my supervision, please, fell free to send me an email.
Se você tem interesse em algum dos meus tópicos de pesquisa e gostaria de fazer IC, TCC, Mestrado ou o Doutorado sob minha orientação, por favor, sinta-se à vontade para me enviar um email.
#algorithms #combinatorics #graphtheory #bioinformatics #strings #qubo #quantumcomputing #optimizationproblems