Search

Your search keyword '"Alexandrino, Alexsandro Oliveira"' showing total 44 results
Start Over Author "Alexandrino, Alexsandro Oliveira"
44 results on '"Alexandrino, Alexsandro Oliveira"'

1. Varia\c{c}\~oes do Problema de Dist\^ancia de Rearranjos

Author

Alexandrino, Alexsandro Oliveira

Subjects
Computer Science - Data Structures and Algorithms, Quantitative Biology - Quantitative Methods
Abstract

Considering a pair of genomes, the goal of rearrangement distance problems is to estimate how distant these genomes are from each other based on genome rearrangements. Seminal works in genome rearrangements assumed that both genomes being compared have the same set of genes (balanced genomes) and, furthermore, only the relative order of genes and their orientations, when they are known, are used in the mathematical representation of the genomes. In this case, the genomes are represented as permutations, originating the Sorting Permutations by Rearrangements problems. The main problems of Sorting Permutations by Rearrangements considered DCJs, reversals, transpositions, or the combination of both reversals and transpositions, and these problems have their complexity known. Besides these problems, other ones were studied involving the combination of transpositions with one or more of the following rearrangements: transreversals, revrevs, and reversals. Although there are approximation results for these problems, their complexity remained open. Some of the results of this thesis are the complexity proofs for these problems. Furthermore, we present a new 1.375-approximation algorithm, which has better time complexity, for the Sorting Permutations by Transpositions. When considering unbalanced genomes, it is necessary to use insertions and deletions to transform one genome into another. In this thesis, we studied Rearrangement Distance problems on unbalanced genomes considering only gene order and their orientations (when they are known), as well as Intergenic Rearrangement Distance problems, which incorporate the information regarding the size distribution of intergenic regions, besides the use of gene order and their orientations (when they are known). We present complexity proofs and approximation algorithms for problems that include reversals and transpositions., Comment: PhD Dissertation, in Portuguese, presented at the Institute of Computing - Unicamp in March 2024

Published
2024

3. Maximum Alternating Balanced Cycle Decomposition and Applications in Sorting by Intergenic Operations Problems

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Siqueira, Gabriel, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Scornavacca, Celine, editor, and Hernández-Rosales, Maribel, editor

Published
2024
Full Text
View/download PDF

5. Algorithms for the Maximum Eulerian Cycle Decomposition Problem

Author

Pinheiro, Pedro O., Alexandrino, Alexsandro Oliveira, Oliveira, Andre R., de Souza, Cid C., and Dias, Zanoni

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Given an Eulerian graph G, in the Maximum Eulerian Cycle Decomposition problem, we are interested in finding a collection of edge-disjoint cycles {E_1, E_2, ..., E_k} in G such that all edges of G are in exactly one cycle and k is maximum. We present an algorithm to solve the pricing problem of a column generation Integer Linear Programming (ILP) model introduced by Lancia and Serafini (2016). Furthermore, we propose a greedy heuristic, which searches for minimum size cycles starting from a random vertex, and a heuristic based on partially solving the ILP model. We performed tests comparing the three approaches in relation to the quality of solutions and execution time, using distinct sets of Eulerian graphs, each set grouping graphs with different numbers of vertices and edges. Our experimental results show that the ILP based heuristic outperforms the other methods.

Published
2022

6. On the Complexity of Some Variations of Sorting by Transpositions

Author

Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, and Dias, Zanoni

Subjects
Computer Science - Computational Complexity, F.2.0, G.2.1
Abstract

One of the main challenges in Computational Biology is to find the evolutionary distance between two organisms. In the field of comparative genomics, one way to estimate such distance is to find a minimum cost sequence of rearrangements (large scale mutations) needed to transform one genome into another, which is called the rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. The complexity of the problems involving reversals, transpositions, and both rearrangements is known, even though the hardness proof for the problem combining reversals and transpositions was recently given. In this paper, we enhance the knowledge for these problems by proving that models involving transpositions alongside reversals, transreversals, and revrevs are NP-hard, considering weights w1 for reversals and w2 for the other rearrangements such that w2/w1 is less than or equal to 1.5. In addition, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function with some restrictions, is NP-hard for transpositions and the combination of reversals and transpositions.

Published
2022
Full Text
View/download PDF

8. Block Interchange and Reversal Distance on Unbalanced Genomes

Author

Alexandrino, Alexsandro Oliveira, Siqueira, Gabriel, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Reis, Marcelo S., editor, and de Melo-Minardi, Raquel C., editor

Published
2023
Full Text
View/download PDF

10. A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Scherer, Nicole M., editor, and de Melo-Minardi, Raquel C., editor

Published
2022
Full Text
View/download PDF

12. Heuristics for Cycle Packing of Adjacency Graphs for Genomes with Repeated Genes

Author

Siqueira, Gabriel, Oliveira, Andre Rodrigues, Alexandrino, Alexsandro Oliveira, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Stadler, Peter F., editor, Walter, Maria Emilia M. T., editor, Hernandez-Rosales, Maribel, editor, and Brigido, Marcelo M., editor

Published
2021
Full Text
View/download PDF

13. Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Martín-Vide, Carlos, editor, Vega-Rodríguez, Miguel A., editor, and Wheeler, Travis, editor

Published
2021
Full Text
View/download PDF

14. Reversals Distance Considering Flexible Intergenic Regions Sizes

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Martín-Vide, Carlos, editor, Vega-Rodríguez, Miguel A., editor, and Wheeler, Travis, editor

Published
2021
Full Text
View/download PDF

17. Sorting by Reversals and Transpositions with Proportion Restriction

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Setubal, João C., editor, and Silva, Waldeyr Mendes, editor

Published
2020
Full Text
View/download PDF

18. Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems

Author

Pinheiro, Pedro Olímpio, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, de Souza, Cid Carvalho, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Setubal, João C., editor, and Silva, Waldeyr Mendes, editor

Published
2020
Full Text
View/download PDF

25. Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations

Author

Alexandrino, Alexsandro Oliveira, Lintzmayer, Carla Negri, Dias, Zanoni, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Jansson, Jesper, editor, Martín-Vide, Carlos, editor, and Vega-Rodríguez, Miguel A., editor

Published
2018
Full Text
View/download PDF

26. Sorting -Operations

Author

Miranda, Guilherme Henrique Santos, Alexandrino, Alexsandro Oliveira, Negri Lintzmayer, Carla, Dias, Zanoni, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, and Alves, Ronnie, editor

Published
2018
Full Text
View/download PDF

40. Reversal and Indel Distance With Intergenic Region Information

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, and Dias, Zanoni

Abstract

Recent works on genome rearrangements have shown that incorporating intergenic region information along with gene order in models provides better estimations for the rearrangement distance than using gene order alone. The reversal distance is one of the main problems in genome rearrangements. It has a polynomial time algorithm when only gene order is used to model genomes, assuming that repeated genes do not exist and that gene orientation is known, even when the genomes have distinct gene sets. The reversal distance is NP-hard and has a 2-approximation algorithm when incorporating intergenic regions. However, the problem has only been studied assuming genomes with the same set of genes. In this work, we consider the variation that incorporates intergenic regions and that allows genomes to have distinct sets of genes, a scenario that leads us to include indels operations (insertions and deletions). We present a 2.5-approximation algorithm using the labeled intergenic breakpoint graph, which is based on the well-known breakpoint graph structure. We also present an experimental analysis of the proposed algorithm using simulated data, which showed that the practical approximation factor is considerably less than 2.5. Furthermore, we used the algorithm in real genomes to construct a phylogenetic tree.

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results