Abstract
An important area of computational biology consists in problems inspired by genome evolution that can be solved using combinatorial algorithms. One of these problems is to calculate the evolutionary distance between two genomes of different organisms by determining the minimum number of genome rearrangements needed to obtain one from the other. The aim of our work is to propose a new algorithm for determining the evolutionary distance by translocations. We represent the chromosomes in a genome as a set of strings over the DNA alphabet {A, T,C,G}. Given two strings, the translocation operation is defined as swapping two prefixes between these strings such that two new strings are obtained. When all the strings are swapping equal length prefixes, the translocation distance is called uniform. The uniform translocation distance was initially introduced by Martín-Vide and Mitrana [7]. Starting from their work, we introduce a new polynomial time exact algorithm to compute the translocation distance for a target set of size two.
Original language | English |
---|---|
Pages (from-to) | 1757-1766 |
Number of pages | 10 |
Journal | Procedia Computer Science |
Volume | 159 |
DOIs | |
Publication status | Published - Jan 1 2019 |
Event | 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, KES 2019 - Budapest, Hungary Duration: Sep 4 2019 → Sep 6 2019 |
Keywords
- DNA computing
- genome distances
- translocation distance
- uniform translocation
ASJC Scopus subject areas
- Computer Science(all)