Limites para distância e diâmetro em rearranjo de genomas por transposições - Cunha, Luis Felipe; de Figueiredo, Celina; Kowada, Luis Antonio (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2014: Anais do XXVII Concurso de Teses e Dissertações, 2014)
Ordenação por tranposições é um clássico problema em rearranjo de genomas, provado ser NP-difícil. Historicamente tem sido considerado o estudo de permutações candidatas a serem diametrais. O diâmetro de transposição é assim relacionado ao problema de ordenação, em aberto, bastante desafiador. Avançamos em ambos problemas. Apresentamos limites justos para distância de famílias de permutações solitárias, estabelecemos o limite inferior para o diâmetro, e apresentamos famílias que por uniões de permutações solitárias atingem este limite. Além disso apresentamos uma estratégia que possivelmente aumentará o limite inferior.