Heuristics for the transposition distance problem.
J Bioinform Comput Biol
; 11(5): 1350013, 2013 Oct.
Article
em En
| MEDLINE
| ID: mdl-24131057
Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum number of transpositions required to transform one genome into another. Recently, Bulteau et al. [Bulteau L, Fertin G, Rusu U, Automata, Languages and Programming, Vol. 6755 of Lecture Notes in Computer Science, pp. 654-665, Springer Berlin, Heidelberg, 2011] proved that finding the transposition distance is a NP-Hard problem. Some approximation algorithm for this problem have been presented to date [Bafna V, Pevzner PA, SIAM J Discr Math11(2):224-240, 1998; Elias I, Hartman T, IEEE/ACM Trans Comput Biol Bioinform3(4):369-379, 2006; Mira CVG, Dias Z, Santos HP, Pinto GA, Walter ME, Proc 3rd Brazilian Symp Bioinformatics (BSB'2008), pp. 115-126, Santo André, Brazil, 2008; Walter MEMT, Dias Z, Meidanis J, Proc String Processing and Information Retrieval (SPIRE'2000), pp. 199-208, Coruña, Spain, 2000]. Here we focus on developing heuristics to provide an improved approximated solution. Our approach outperforms other algorithms on small sized permutations. We also show that our algorithm keeps the good performance on longer permutations.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Elementos de DNA Transponíveis
/
Modelos Genéticos
Tipo de estudo:
Evaluation_studies
/
Prognostic_studies
/
Risk_factors_studies
Idioma:
En
Revista:
J Bioinform Comput Biol
Assunto da revista:
BIOLOGIA
/
INFORMATICA MEDICA
Ano de publicação:
2013
Tipo de documento:
Article
País de afiliação:
Brasil
País de publicação:
Singapura