Rearranjamento de Genomas
Motivação...
Em alguns casos, quando comparamos
genes correspondentes em duas ou mais
espécies obtemos menos informação do
que comparações de grandes porções do
genoma, ou mesmo do genoma inteiro,
para inferir relações evolutivas entre
estas espécies.
A teoria de Rearranjamento do
Genoma é utilizada nestas situações.
...
A comparação destas grandes porções
do genoma é feita num “alto nível”. Ao
invés de olharmos para as sequências,
nós comparamos as posições de vários
relacionados genes e tentamos
determinar operações de
rearranjamento de genes que
transformem um genoma no outro.
Nós não estamos interessados em
pontos de mutação tais como
substituições, deleções ou inserções,
mas em grandes mutações . Partes de
cromossomos podem ser permutadas,
movidas ou copiadas para outro lugar, ou
deixar algum cromossomo para entrar
noutro. Tais mudanças são chamadas de
Rearranjamento do Genoma.
Rearranjamento do Genoma
Seus “blocos de construção” são genes e
as estruturas de maior interesse são os
cromossomos, abstraídos em termos da
ordem linear dos genes que contém.
G1, G2, G3
Definições
• Um bloco é uma seção do genoma
contendo possivelmente mais de um
gene, descrito como uma unidade.
• Os blocos podem ter orientação, que é
denotada por uma seta.
• Dois blocos em diferentes genomas são
homólogos se eles contém os mesmos
genes, neste caso devem possuir o
mesmo rótulo.
Contexto
• O estudo do rearranjamento do genoma
pode avaliar diferentes níveis de
estruturas:
• Syntenic structure (pertencer ao mesmo
cromossomo ou não),
• Ordem,
• Polaridade.
Aspectos biológicos
• Cromossomos lineares versos circulares.
• Centrômeros e telômeros.
• Famílias de Multigenes.
Exemplo
• Observe o genoma do cloroplasto da alfafa e
da ervilha.
Distâncias
O problema de calcular distâncias entre
duas ordens lineares ou circulares de
blocos homólogos de genes depende das
operações de edição elementares que
podem ser um subconjunto destas:
• Transposição,
• Inversão,
• Translocação Recíproca.
• Um tipo de rearranjamento é a chamada
reversão ou inversão.
• Sobre blocos orientados:
Ela opera sobre segmentos de blocos
invertendo a ordem destes e ao mesmo
tempo invertendo sua orientação.
• Qual o menor número de inversões
necessárias para transformar um
genoma no outro?
Solução
Solução (não orientados blocos)
Importante
• Assumimos que a natureza sempre
encontra caminhos mínimos de mudança.
• Portanto desejamos encontrar o número
mínimo de inversões para ir de um
genoma a outro.
• No caso orientado existe um algoritmo
em tempo polinomial para esta tarefa. A
versão não orientada tem se mostrado
NP hard.
Breakpoints
Acontece um breakpoint entre dois
rótulos h e g vizinhos no cromossomo
(genoma) dado por A quando no
cromossomo B eles não são vizinhos ou
são vizinhos mas estão em outra posição
relativa. Isto é, não temos um
breakpoint entre hg em A se em B
houver hg ou –g-h.
Notação e definições
Transposição e translocação recíproca
• A distância associada a transposição é um
problema mais díficil que o da inversão, mas
ainda não foi provado que ele é NP-completo.
• A distância associada a translocação é um
problema de complexidade polinomial
(Hannenhalli-1996).
• Sytenic Distance (NP-completo, DasGupta et
al - 1998). Nela a ordem interna dos genes
nos cromossos não interessa, mas sim a
partição do genoma em cromossomos.
•
(A-A’)UB’ e (B-B’)UA’
Distâncias combinadas
• Hannenhalli-Pevzner (1995): translocação e
reversão.
• El-Mabrouk (2000): extensão.
• Gu et al (97), Walter et al (98):
transposição e reversão (resultados parcias).
• Sankoff (92), _ et al. (92) e Blanchette et al.
(96): combinação dos 3 com pesos.
• Daleivi et al (2000)
• McLysaght et al. (2000)
O “diagrama da realidade e desejo”
• Quando uma reversão remove um
breakpoint ela é chamada de “sorting
reversal”.
• Suponha que a sorting reversal retirou o
breakpoint de xy em: ... x | y ... z | w ...
obtendo ... x -z ... –y w...
Então x –z ou -y w estão na permutação
alvo. Além disso, xy e –y-x não estão.
Construção
Observações
Interleaving Graph
• Um ciclo é bom quando tem duas arestas
reais divergentes. Um ciclo é ruim
quando caso contrário.
• Um ciclo bom tem pelo menos duas
arestas desejo se encontrando no RD.
• Ciclos com pelo menos quatro arestas
são chamados de ciclos próprios.
• As vezes podemos torcer um ciclo ruim
tornando-o em bom, por alguma
reversão.
• Essa torção é possível quando pelo menos uma
das arestas desejo deste ciclo está
encontrando uma aresta desejo de um ciclo
bom.
• Os ciclos nesta situação chamam-se
interleave.
• O interleave graph é construido tomando os
ciclos como nós e colocando arestas apenas
entre ciclos interleaves.
• Forman-se, então, as componentes conexas
ditas boas ou ruins conforme possuam pelo
menos um ciclo bom ou não.
• Se um diagrama contém um ciclo ruim,
nenhuma inversão irá incrementar o
número de ciclos, daí a distância será
estritamente menor que n+1-c(a).
• Teorema 3: Uma reversão caracterizada
por duas arestas divergentes de um
mesmo ciclo é uma sorting reversal se e
somente se sua aplicação não permite a
criação de componentes ruins.
Componentes separadoras.
• Dizemos que a componente B separa as
componentes A e C quando qualquer
aresta ligando nós em A e C encontrem
com uma aresta desejo de B.
• Fazendo uma reversão sobre arestas
reais de A e C resultará na torção da
componente B.
Componentes ruins se dividem em:
• Permutações fortress.
• A equação da distância associada a
reversão:
d(a) = n + 1 – c(a) + h(a) + f(a).
• Onde h(a) é o número de comp. hardle.
• E f(a) é 1 ou 0 conforme a permutação
seja fortress ou não.
• Hannenhalli-Pevzner fizeram três
algoritmos em tempo polinomial. Uma
versão somente para reversão (99),
outro somente para translocação (96) e
um para reversão e translocação (95).
• d(a) = n – c(a) + m(a) + f(a)
m(a) número de comp. ruins
f(a) pertence a {0,1,2}.
Novos conceitos
• Hurdle cutting: reversão em arestas
convergentes de um mesmo ciclo em uma
componente hardle (usamos com h(a) ímpar).
• Hurdle merging: reversão em arestas de ciclos
diferentes em componentes hardles diferentes
(usamos com h(a) par).
• Hurdle opostos: dividem o círculo em duas
metades com o mesmo número de hardles.
d(a) = n + 1 – c(a) + h(a) + f(a)
Caso não-orientado
• Strip: sequência de consecutivos rótulos
entre breakpoints, mas sem breakpoint
interno. Podem ser decrescentes e/ou
crescentes.
• L e R quando pertencem sempre a strip
crescentes.
L 1 2.8 7.3.5 6.4.R
• Teo. 4: Se um rótulo k pertence a um
strip decrescente e k-1 pertence a um
strp crescente, então existe uma
reversão que remove pelo menos um
breakpoint.
... (k-1). ... k.
...
... (k-1) k ...
...
k. ... (k-1). ...
... k (k-1) ...
• Teo. 5: Se um rótulo k pertence a um
strip decrescente e k+1 pertence a um
strip crescente, então existe uma
reversão que remove pelo menos um
breakpoint.
... .k ... .k+1 ...
... k (k+1) ...
• Teo. 6: Seja alfa uma permutação com
um decrescente strip. Se todas as
reversões que removem breakpoints de
alfa não deixam strips, então existe uma
reversão que remove dois breakpoints
de alfa.
O strip decrescente, por hip., será:
... (k-1). ...
k. ...
Para l, o maior rótulo neste strip,
temos:
...
.l
... .(l+1) ...
• Teo. 7: O número de interações em
um algoritmo Sorting Unoriented
Permutation é menor ou igual ao número
de breakpoints na permutação inicial.
Phylogenic Analyses
A reconstrução da “philogeny” pode ser
feita através da aplicação dos métodos
gerais (neighbor-joining, least-squares
fitting, agglomerative clustering, etc.)
para a matrix de distância, ou através
de métodos de inferência ancestral
(maximum likehood, parsimony, etc.).
• Cap. 7 do livro Introduction to
computacional molecular biology, de
Setubal e Meidanis.
• Cap. 6 do livro de Jiang, cap. escrito por
David Sankoff e Nadia El-Mabrouk.
Download

Rearranjo de Genomas