An O(n2) algorithm for signed translocation

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

27 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)284-299
Journal / PublicationJournal of Computer and System Sciences
Volume70
Issue number3
Publication statusPublished - May 2005

Abstract

Genome rearrangement is an important area in computational biology. There are three basic operations, reversal, translocation and transposition. Here we study the translocation operations. Multi-chromosomal genomes frequently evolve by translocation events that exchange genetic material between two chromosomes. We focus on the signed case, where the direction of each gene is known. The signed translocation problem asks to find the minimum number of translocation operations as well as the sequence of translocation operations to transform one genome into the other. A linear-time algorithm that computes the minimum number of translocation operations was given in a linear-time algorithm for computing translocation distance between signed genomes [16]. However, that algorithm cannot give the optimum sequence of translocation operations. The best known algorithm that can give the optimum sequence of translocation operations for signed translocation problem runs in O(n2logn) time. In this paper, we design an O(n2) algorithm. © 2005 Elsevier Inc. All rights reserved.

Research Area(s)

  • Algorithm, Genome rearrangement, Signed translocation

Citation Format(s)

An O(n2) algorithm for signed translocation. / Wang, Lusheng; Zhu, Daming; Liu, Xiaowen; Ma, Shaohan.

In: Journal of Computer and System Sciences, Vol. 70, No. 3, 05.2005, p. 284-299.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review