Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

HEURISTICS FOR THE TRANSPOSITION DISTANCE PROBLEM

Texto completo
Autor(es):
Dias, Ulisses [1] ; Dias, Zanoni [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY; v. 11, n. 5 OCT 2013.
Citações Web of Science: 4
Resumo

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 Math 11(2): 224-240, 1998; Elias I, Hartman T, IEEE/ACM Trans Comput Biol Bioinform 3(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 Andre, Brazil, 2008; Walter MEMT, Dias Z, Meidanis J, Proc String Processing and Information Retrieval (SPIRE'2000), pp. 199-208, Coruna, 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. (AU)

Processo FAPESP: 12/01584-3 - Problemas de distâncias de rearranjos de genomas
Beneficiário:Ulisses Martins Dias
Linha de fomento: Bolsas no Brasil - Pós-Doutorado