Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/106528
Type: Artigo de evento
Title: Transposition Distance Based On The Algebraic Formalism
Author: Mira C.V.G.
Dias Z.
Santos H.P.
Pinto G.A.
Walter M.E.M.T.
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.
Editor: 
Rights: fechado
Identifier DOI: 10.1007/978-3-540-85557-6_11
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-51849118862&partnerID=40&md5=95ff3d43ec3d8ae34d0e1889d421d3a9
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-51849118862.pdf191.86 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.