Rearrangement distances in unbalanced genomes considering intergenic regions
| Full text | |
| Author(s): |
Siqueira, Gabriel
[1]
;
Alexandrino, Alexsandro Oliveira
[1]
;
Oliveira, Andre Rodrigues
[1]
;
Dias, Zanoni
[1]
Total Authors: 4
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | Algorithms for Molecular Biology; v. 16, n. 1 OCT 13 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
The rearrangement distance is a method to compare genomes of different species. Such distance is the number of rearrangement events necessary to transform one genome into another. Two commonly studied events are the transposition, which exchanges two consecutive blocks of the genome, and the reversal, which reverts a block of the genome. When dealing with such problems, seminal works represented genomes as sequences of genes without repetition. More realistic models started to consider gene repetition or the presence of intergenic regions, sequences of nucleotides between genes and in the extremities of the genome. This work explores the transposition and reversal events applied in a genome representation considering both gene repetition and intergenic regions. We define two problems called Minimum Common Intergenic String Partition and Reverse Minimum Common Intergenic String Partition. Using a relation with these two problems, we show a Theta(k)-approximation for the Intergenic Transposition Distance, the Intergenic Reversal Distance, and the Intergenic Reversal and Transposition Distance problems, where k is the maximum number of copies of a gene in the genomes. Our practical experiments on simulated genomes show that the use of partitions improves the estimates for the distances. (AU) | |
| FAPESP's process: | 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events |
| Grantee: | Anderson de Rezende Rocha |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| 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 |
| FAPESP's process: | 19/27331-3 - Sorting by genome rearrangements problems |
| Grantee: | André Rodrigues Oliveira |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |