Enumeração de Soluções de
Distância de Rearranjo e
Alinhamento de Sequências
utilizando Eventos de Rearranjo
Christian Baudet
Zanoni Dias (Orientador)
Instituto de Computação – Unicamp
Campinas, 05 de Setembro de 2008
Roteiro

Motivação

Conceitos

Descrição do Projeto

Estágio no Exterior

Cronograma de Atividades
Motivação

Importância da pesquisa genômica

Rearranjo de genomas

Mecanismos de evolução
Rearranjo de Genomas

Eventos de rearranjos
Transformam o genoma das espécies
 Grande influência na evolução
 Espécies próximas

 Diferenças
na ordem dos genes
Reversões
 Transposições
 Translocações

Reversões

Inversão na direção de um trecho do
cromossomo:
Reversões

Permutações não orientadas
Problema NP-Completo (Caprara, 1999)
 Berman, Hannehalli e Karpinski, 2002

 Algoritmo

de aproximação com fator 1.375
Permutações orientadas

Tempo polinomial
 O(n4)
– Hannenhalli e Pevzner, 1995
 O(n2) – Bergeron, 2001

Apenas cálculo de d()
 O(n)
– Bader, Moret e Yan, 2001
Transposições

Troca de posições entre dois blocos
consecutivos no cromossomo:
Transposições

Ordenação por transposições


Problema em aberto
Bafna e Pevzner, 1995
Primeiro algortimo de aproximação
 O(n2) e fator 1.5


Christie, 1996


Block-interchange – Algoritmo O(n2)
Elias e Hartman, 2005

Algoritmo de aproximação com fator 1.375
Translocações

Trocas entre prefixos/sufixos de dois
cromossomos diferentes:
Translocações

Permutações não orientadas
Problema em aberto
 Kececioglu e Ravi, 1995

 Algoritmo

de aproximação com fator 2
Permutações orientadas
O(n3) – Hannehalli, 1996
 O(n2) – Wang et al., 2005
 Apenas cálculo de distância de translocação

 O(n)
– Li et al., 2002
Enumeração de Soluções de
Distância de Reversão

Braga et al.
The Solution Space of Sorting by Reversals
(2007)
 Exploring the Solution Space of Sorting by
Reversals, with Experiments and an
Application to Evolution (2008)


Enumeração de todas as soluções

Utilização do conceito de traces
Traces

Relação de equivalência


Classes de equivalências


Se ρ e θ são reversões e não se sobrepõem,
então ρθ e são θρ equivalentes
Relação acima é aplicada às soluções do
problema de distância de reversão
Traces têm a propriedade de “compactar” o
enorme conjunto de soluções

Resultados mais representativos
Traces – Forma Normal

Decomposição: s = u1|...|um




Todo par de elementos da sub-palavra ui comutam
entre si
Para todo elemento ρ de uma sub-palavra ui (i > 1),
existe ao menos um elemento θ da palavra ui-1 tal
que ρ e θ não comutam
Toda palavra ui é uma palavra crescente não vazia
com relação à ordem lexográfica induzida por A
Teorema – Cartier e Foata, 1969

Todo trace possui uma única forma normal
Enumeração de Soluções de
Distância de Reversão

Siepel, 2003



Algoritmo iterativo


Optimal i-sequence : s= ρ1 ρ2... ρi
 d( ρ1 ρ2... ρi) = d() – i
Obtém todas optimal 1-sequences em tempo O(n3)
Calcular todas i-sequences a partir de todas as
(i-1)-sequences
Braga et al. 2007

Calcular todos i-traces a partir de todos os
(i-1)-traces
Enumeração de Soluções de
Distância de Reversão

Braga et al. 2007 e 2008
Algoritmo que enumera todos os traces das
soluções do problema de distância de
reversão
 Algoritmo exponencial

 Altas
complexidades de tempo e de espaço
 Limitado a permutações pequenas (n < 20)

Adição de restrições biológicas para reduzir
o espaço de soluções
Alinhamento de Sequências
com Reversões

Vellozo et. al


Alignment with Non-overlapping Inversions
in O(n3)-Time (2006)
Alinhamento de sequências
Inversões que não se sobrepõem
 Complexidade de tempo O(n3)
 Complexidade de espaço O(n2)

Alinhamento de Sequências
com Reversões

Grafo de edição
Alinhamento de Sequências
com Reversões

Grafo de edição estendido
Alinhamento de Sequências
com Reversões


Alinhamento de Sequências
com Reversões

Matriz B


Cada célula (i,j) mantém o peso do caminho
ótimo de (0,0) até (i,j)
Diversas matrizes e vetores auxiliares
Alinhamento de Sequências
com Reversões

Vellozo et. al, 2006

Algoritmo utiliza espaço quadrático

Não utiliza pontuação afim

Peso de reversão constante
Projeto

Enumeração de Soluções

Aplicar o algoritmo ao gênero Wolbachia

Reduzir consumo de memória

Combinar conceitos: Traces + Transposição
 Algoritmo
de aproximação de fator 1.375
para o problema de distância de transposição
Projeto

Alinhamento com eventos de rearranjo

Estender algoritmo para utilização de
pontuação afim

Função que penalize as reversões conforme
os seus tamanhos

Transposição
 Algoritmo
que realize alinhamento utilizando
eventos de transposição
Estágio no exterior

Estágio em Lyon – França
Professora Marie-France Sagot
 Grupo BAMBOO-BAOBAB
 Visita em Fevereiro/2007


Braga e Vellozo trabalham no laboratório

Intercâmbio com pessoas familiarizadas com
os problemas que serão abordados no
projeto
Cronograma
Disciplinas
2. Revisão Bibliográfica
3. Visita ao grupo BAOBAB
4. Preparação para o Exame de
Qualificação Específico
1.
Cronograma
5.
6.
Aplicar algoritmo de enumeração de
soluções de distância de reversão ao
gênero Wolbachia
Incorporação de pontuação afim ao
algoritmo de alinhamento de sequências
com reversões
Cronograma
7.
Estágio no Exterior
Redução de consumo de memória do
algoritmo de enumeração
b. Redução de consumo de memória do
algoritmo de alinhamento
c. Adição de função de peso para as
reversões ao algoritmo de alinhamento
a.
Cronograma
Algoritmo de alinhamento de sequências
usando transposições
9. Algoritmo de enumeração de soluções de
distância de transposição
10. Conclusão da escrita da tese
11. Defesa
12. Entrega da versão final
8.