Some remarks on the translocation distance

Maria Constantin, Alexandru Popa

Research output: Contribution to journalConference article

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 languageEnglish
Pages (from-to)1757-1766
Number of pages10
JournalProcedia Computer Science
Volume159
DOIs
Publication statusPublished - Jan 1 2019
Event23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, KES 2019 - Budapest, Hungary
Duration: Sep 4 2019Sep 6 2019

    Fingerprint

Keywords

  • DNA computing
  • genome distances
  • translocation distance
  • uniform translocation

ASJC Scopus subject areas

  • Computer Science(all)

Cite this