Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Title:||Constraint Programming Models For Transposition Distance Problem|
|Abstract:||Genome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal with transposition events, which are events that change the position of two contiguous block of genes in the same chromosome. The transposition event generates the transposition distance problem, that is to find the minimum number of transposition that transform one genome (or chromosome) into another. Although some tractables instances were found [20,14], it is not known if an exact polynomial time algorithm exists. Recently, Dias and Souza  proposed polynomial-sized Integer Linear Programming (ILP) models for rearrangement distance problems where events are restricted to reversals, transpositions or a combination of both. In this work we devise a slight different approach. We present some Constraint Logic Programming (CLP) models for transposition distance based on known bounds to the problem. © 2009 Springer Berlin Heidelberg.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.