Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Title:||Transposition Distance Based On The Algebraic Formalism|
|Abstract:||In computational biology, genome rearrangements is a field in which we study mutational events affecting large portions of a genome. One such event is the transposition, that changes the position of contiguous blocks of genes inside a chromosome. This event generates the problem of transposition distance, that is to find the minimal number of transpositions transforming one chromosome into another. It is not known whether this problem is -hard or has a polynomial time algorithm. Some approximation algorithms have been proposed in the literature, whose proofs are based on exhaustive analysis of graphical properties of suitable cycle graphs. In this paper, we follow a different, more formal approach to the problem, and present a 1.5-approximation algorithm using an algebraic formalism. Besides showing the feasibility of the approach, the presented algorithm exhibits good results, as our experiments show. © 2008 Springer-Verlag Berlin Heidelberg.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.