Heuristics for determining the flip distance between triangulations
Dual bounds and exact algorithms for minimum dilation problems in geometric graphs
Feature selection and hyperparameters tuning of neural networks applied for wood q...
| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Estadual Campinas, Fac Technol, BR-13484332 Limeira, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 15, n. 2, p. 352-363, MAR-APR 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
Genome Rearrangements are large-scale mutational events that affect genomes during the evolutionary process. Therefore, these mutations differ from punctual mutations. They can move genes from one place to the other, change the orientation of some genes, or even change the number of chromosomes. In this work, we deal with inversion events which occur when a segment of DNA sequence in the genome is reversed. In our model, each inversion costs the number of elements in the reversed segment. We present a new algorithm for this problem based on the metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) that has been routinely used to find solutions for combinatorial optimization problems. In essence, we implemented an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated. Our analysis shows that we outperform any other approach by significant margin. We also use our algorithm to build phylogenetic trees for a subset of species in the Yersinia genus and we compared our trees to other results in the literature. (AU) | |
| FAPESP's process: | 14/19401-8 - Genome rearrangement algorithms |
| Grantee: | Zanoni Dias |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 12/01584-3 - Genome Rearrangement Distance Problems |
| Grantee: | Ulisses Martins Dias |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |