A idéia da aula foi mostrar uma aplicação de permutações à Biologia Computacional. Especificamente, rearranjos genômicos são formalizados como uma permutação de genes. Alguns conceitos e propriedades referentes a permutações que ainda não haviam sido mencionados foram estudados. Visando uma melhor organização dos tópicos, tais conceitos e propriedades são relacionados antes de qualquer outra menção a arranjos genômicos neste documento.
Seja (a b) o 2-ciclo, e P uma permutação qualquer. Se a e b fazem parte do mesmo ciclo em P (considerando-se a decomposição em ciclos disjuntos), esse ciclo é quebrado em (a b)P. Se a e b estão em ciclos diferentes em P, em (a b)P esses ciclos se tornam um só.
Estes resultados também se aplicam a P(a b) pois, pelas propriedades de conjugação, essa permutação possui a mesma estrutura de (a b)P. Como todo 2-ciclo é seu próprio inverso, é fácil verificar que a conjugação de (a b)P por (a b) é P(a b) e a conjugação de P(a b) por (a b) é (a b)P.
Seja (a b c) o 3-ciclo, e P uma permutação qualquer. Três casos são possíveis:
Estes resultados também se aplicam a P(a b c). (*)
Dada uma permutação P, a norma de P, |P|, é o número mínimo de 2-ciclos em uma representação de P como produto de 2-ciclos. As seguintes proposições são válidas:
Sim, é possível obter a norma apenas com a decomposição em ciclos disjuntos (a qual, contrariamente à decomposição em 2-ciclos, é única). O conjunto U, domínio e imagem das permutações, deve ser conhecido. Prova-se que a norma de P é igual ao tamanho de U menos o número de ciclos disjuntos em P (cada elemento fora do suporte conta como um ciclo).
Diz-se que uma permutação P divide uma permutação Q (P|Q) quando |QP-1| = |Q| - |P|. A relação de divisibilidade apresenta as seguintes propriedades:
Através do conceito de divisibilidade é possível definir sob quais condições um ciclo P faz parte da decomposição em ciclos disjuntos de uma permutação Q qualquer. Essas condições são:
A condição |QP-1| = |Q| - |P| torna-se interessante quando P é um ciclo e as normas |QP-1| e |Q| são expressas em termos do tamanho de U e do número de ciclos disjuntos: conclui-se que sempre que um ciclo P divide uma permutação Q, o produto QP-1 apresenta exatamente |P| ciclos a mais que Q. Disto decorre que, nos casos de composição com 2-ciclos e 3-ciclos analisados, um 2-ciclo divide uma permutação Q se seus elementos estão no mesmo ciclo em Q, e um 3-ciclo divide uma permutação Q se, além de seus elementos estarem no mesmo ciclo em Q, eles aparecem em Q na mesma ordem(*) que no 3-ciclo.
O genoma é representado por uma lista de marcadores. As permutações são funções sobre o conjunto de marcadores. No entanto, qualquer permutação diferente da identidade implica um genoma circular. Embora isso exista, também é necessário representar genomas lineares, o que requer adaptações do modelo.
O domínio e imagem das permutações é o conjunto En = {-1, +1, -2, +2, ..., -n, +n}, onde n é o número de genes.
São modeladas ambas as fitas da molécula de DNA. Dessa forma, i (sem sinal) representa o i-ésimo gene. Um dentre +i e -i é um marcador no gene, e o outro é um marcador na mesma posição, porém na outra fita. Dessa forma, um ciclo que contém ambos +i e -i não pode representar uma fita de DNA. Já um ciclo que contém no máximo um de cada i (indepentendemente do sinal), é capaz de representar uma fita de DNA, e é dito ser um ciclo admissível.
O complemento reverso é a adaptação de um conceito da Biologia Molecular, onde o complemento reverso de uma fita de DNA é o inverso da seqüência das bases complementares à fita. Por exemplo, o complemento reverso de ATCCGA é TCGGAT. O complemento reverso do genoma é o inverso da seqüência dos complementos de seus genes. No modelo utilizado, é possível calcular o complemento reverso de um ciclo admissível α através da expressão Γα-1Γ, onde Γ é uma permutação que mapeia os elementos +i em elementos -i. Γ tem a propriedade de ser sua própria inversa, portanto a expressão do complemento reverso é na verdade uma conjugação. Adicionalmente, o complemento reverso do complemento reverso de um ciclo admissível é o próprio ciclo admissível.
Um ciclo admissível e seu complemento reverso sempre são disjuntos, então o produto entre eles é comutativo. Isso evita a necessidade de diversas considerações quando se define o genoma como o produto de uma fita (ciclo admissível) e seu complemento reverso.
Primeiramente, há duas situações a serem consideradas: na primeira, os genomas são na verdade regiões de genomas, delimitadas por regiões que não se alteram; na segunda, estuda-se um genoma inteiro, portanto não há regiões constantes. A primeira situação, genomas lineares com pontas fixas, é tratada pela inclusão de um "gene" representando as pontas fixas. Para a comparação de genomas lineares com pontas livres é realizado processamento adicional, tomando-se a distância entre dois genomas como o mínimo entre as distâncias de ambos o genoma fonte e seu reverso ao genoma destino.
Tomando π como o genoma original e σ como o genoma resultante da operação, onde σ = opπ, definem-se três operações:
A distância entre dois genomas é definida separadamente para cada operação.
O breakpoint graph é uma forma de relacionar dois genomas em um problema de rearranjo. Esse tipo de problema se apresenta como dois genomas, π e σ, e uma classe de operações. Encontrar a solução é determinar o menor número de operações que transforma π em σ. Esse número é denominado distância(*) entre os genomas. A aplicação mais direta do breakpoint graph é a modelos de genomas lineares. Adaptações são necessárias para genomas circulares.
O breakpoint graph possui dois tipos de arestas: pretas e cinzas. As arestas pretas dependem de π, e as cinzas de σ. É possível definir algébricamente ambos os tipos de arestas: as arestas pretas correspondem aos 2-ciclos de Γπ, e as cinzas aos 2-ciclos de Γσ. O produto entre essas permutações é útil também para calcular o número de breakpoints(**) entre π e σ: ele é a metade do tamanho do suporte do produto.
Modelar a realidade de maneira equivocada não deixa de ser um problema. No entanto, a complexidade do problema de rearranjo de genomas cresce demais se for considerado que o caminho entre dois genomas pode não ser mínimo. Este não é o primeiro problema one se procura uma otimização que pode não corresponder exatamente à realidade. Por exemplo, nos modelos de evolução de Jukes-Cantor e de Kimura, a taxa de mutação calculada pode estar bem abaixo da realidade, embora haja uma grande chance de isso não acontecer. O mesmo ocorre com análises baseadas em alinhamento e similaridade: duas seqüências que na realidade não possuem qualquer relação podem ser mais similares do que duas seqüências que possuem alguma relação. Em todos os casos, é pouco provável que a realidade não corresponda ao caminho ótimo, mas não há qualquer garantia de o caminho ótimo de fato modele a realidade.
Qualquer um, desde que seja possível mapear marcadores em genes. Recombinações envolvendo genes multi-alelos podem criar problemas devido à correspondência entre alelos e genes não ser um-para-um.