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.)

SCJ: A Breakpoint-Like Distance that Simplifies Several Rearrangement Problems

Texto completo
Autor(es):
Feijao, Pedro [1] ; Meidanis, Joao [1, 2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Scylla Bioinformat, Campinas, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 8, n. 5, p. 1318-1329, SEP-OCT 2011.
Citações Web of Science: 35
Resumo

The breakpoint distance is one of the most straightforward genome comparison measures. Surprisingly, when it comes to defining it precisely for multichromosomal genomes with both linear and circular chromosomes, there is more than one way to go about it. Pevzner and Tesler gave a definition in a 2003 paper, Tannier et al. defined it differently in 2008, and in this paper we provide yet another alternative, calling it SCJ for single-cut-or-join, in analogy to the popular double cut and join (DCJ) measure. We show that several genome rearrangement problems, such as median and halving, become easy for SCJ, and provide linear and higher polynomial time algorithms for them. For the multichromosomal linear genome median problem, this is the first polynomial time algorithm described, since for other distances this problem is NP-hard. In addition, we show that small parsimony under SCJ is also easy, and can be solved by a variant of Fitch's algorithm. In contrast, big parsimony is NP-hard under SCJ. This new distance measure may be of value as a speedily computable, first approximation to distances based on more realistic rearrangement models. (AU)

Processo FAPESP: 09/09307-6 - WABI 2009: 9th Workshop on Algorithms in Bioinformatics
Beneficiário:João Meidanis
Modalidade de apoio: Auxílio à Pesquisa - Reunião - Exterior