Evolução Biológica e Algoritmos
Genéticos
Fábio Lima Custódio
[email protected]
Sumário
• Conceitos gerais
• O que é evolução?
• Forças Evolutivas
–
–
–
–
Mutação
Deriva Gênica
Fluxo gênico
Seleção Natural
• A teoria evolutiva como um algoritmo de otimização
Genes
• Fragmento de DNA que codifica uma certa função bioquímica,
por exemplo, a produção de uma proteína
• É fundamentalmente uma unidade de herança
• Qualquer fragmento de DNA que sofre ação da
seleção natural
• O DNA de um organismo pode conter desde uma dúzia de
genes (como o de um vírus), até dezenas de milhares (como o
de um humano)
DNA: A Molécula da Vida
• O Ácido Desoxirribonucleico (ADN ou DNA) é o material
genético fundamental de todos os organismos vivos
• O DNA é uma macro-molécula com uma estrutura em duplahélice
• Os dois filamentos da hélice, chamados de fitas, são
polímeros de nucleotídeos
• Um nucleotídeo é um carboidrato (desoxirribose) ligado a um
grupamento fosfato e a uma base nitrogenada
Genes e proteínas
• Genes codificam as proteínas.
Típico organismo moderno
DNA Transcrição RNA
Tradução
Proteínas
Replicação
• A seqüência de aminoácidos de um polipeptídeo é chamada de
estrutura primária. Mas existem 3 outros níveis de organização
estrutural, que, em conjunto, determinam a formação
tridimensional da proteína, e, em conseqüência, sua função (ou
efeito fenotípico).
Cromossomo
• Cromossomo: uma das cadeias de DNA que se encontra no
núcleo das células
• Cada gene é capaz de ocupar somente uma região em
particular de um cromossomo (seu “lugar” ou locus)
• Em cada locus pode existir, em uma população, “formas”
alternativas do gene. Essas formas são chamadas de alelos
6
Genoma
• A coleção total de genes (e portanto, cromossomos) que um
organismo possui
Desenvolvimento
• Genótipo:
A composição genética de um organismo (a informação
contida no genoma)
• Pode-se dizer que, é o que potencialmente pode vir a ser um
indivíduo
Desenvolvimento
• Fenótipo:
Conjunto das características (observáveis) específicas de um
indivíduo
...
Conceitos básicos
• Indivíduo:
Um só membro de uma população
Conceitos básicos
• População:
Um grupo de indivíduos que podem interagir, por exemplo,
para reproduzir
Reprodução
• Reprodução: a geração de um novo indivíduo a partir de
 2 progenitores: sexual
 1 progenitor: asexual
Reprodução
• Gametas:
As células que levam informações genéticas dos pais com o
propósito de efetuar reprodução sexuada
Reprodução
• Denomina-se diplóide a uma célula que contém duas cópias de
cada cromossomo
• As cópias são chamadas de homólogas, quer dizer, contém os
mesmos genes na mesma seqüência  Cromossomos
homólogos
• Denomina-se haplóide a célula que contém somente uma
cópia dos cromossomos
• Um exemplo é o gameta de um organismo diplóide
Reprodução
• Dessa forma, em muitas espécies que se reproduzem
sexuadamente os genes em um dos conjuntos de
cromossomos de uma célula diplóide são herdados do gameta
do pai, enquanto que os genes do outro conjunto são do
gameta da mãe
Recombinação
• Durante a reprodução sexual ocorre a recombinação
(cruzamento ou crossover)
• Caso haplóide: Os genes fazem intercâmbio entre os
cromossomos (haplóides) dos pais
Recombinação
• Caso diplóide: Em cada pai, os genes podem se trocar entre os
pares de cromossomos na formação dos gametas
• Os gametas dos dois pais se juntam para formar um só
conjunto de cromossomos diplóides
Recombinação
• Recombinação (crossover)
• De acordo com o modelo de evolução biológica de
Darwin, os requisitos mínimos para os processos
evolutivos ocorrerem (no sentido filogenético) são
(Banzhaf et al., 1998):
– Reprodução de indivíduos na população
– Variação que afeta a probabilidade de
sobrevivência dos indivíduos
– Hereditariedade na reprodução
– Competição por recursos finitos
Evolução, o que é?
•
São as mudanças na composição genética de uma
determinada população ao longo de gerações
– Mudanças na frequência dos alelos ao longo do tempo
•
Quatro mecanismos distintos levam a essas mudanças
Evolução, o que é?
•
São as mudanças na composição genética de uma
determinada população ao longo de gerações
– Mudanças na frequência dos alelos ao longo do tempo
•
1.
2.
3.
4.
Quatro mecanismos distintos levam a essas mudanças
Mutação
Deriva gênica
Fluxo gênico (migração)
Seleção natural (ou artificial)
Mutação, origens e efeitos evolutivos
• Mutação como fonte de nova variabilidade genética e como
força evolutiva que altera as frequências dos genes em uma
população
• Constitui a origem de todas as novidades genéticas em uma
população
– Grandes ou pequenas
• No sentido amplo, a mutação refere-se a qualquer mudança
imprevista e hereditária no genótipo de um organismo
Mutação, origens e efeitos evolutivos
• Características básicas da mutação gênica
– Pode ocorrer de forma espontânea: erros da enzima DNA polimerase
– Ou induzida por agentes mutagênicos
– Pode ocorrer em qualquer tipo celular, mas apenas as que ocorrem
em gametas são herdáveis
– Ocorrência rara?
Mutação, origens e efeitos evolutivos
• Mutação como força evolutiva
– Células somáticas X células germinativas
– Mudanças na frequência gênica
Mutação, origens e efeitos evolutivos
• Mutação como força evolutiva
– Pequeno efeito na frequência gênica
– Um evento único possui uma chance muito pequena (zero) de
propagação indefinida em uma população muito grande (infinita)...
– Populações reais são finitas! De fato, ocasionalmente mutações únicas
sobrevivem indefinidamente e levam a uma mudança na frequência
gênica
– Porém, com taxas de mutação “normais”, a mutação sozinha pode
produzir somente mudanças muito vagarosas nas frequências gênicas
– Como esse não é o caso em populações naturais, é claro que as
frequências gênicas naturais não são produto da mutação sozinha
Deriva Gênica
• Quando uma população se reproduz...
Gene Pool
• Quando uma população se reproduz...
Deriva Gênica
• Quando uma população se reproduz, existe uma amostragem
no gene pool
– Como se fosse um sorteio, em que os alelos sorteados encontram-se
nos gametas que se unem para formar filhotes
Deriva Gênica
• A frequência dos genes apresenta uma distribuição binomial
– Um alelo é de um determinado tipo OU não
• Cada geração nova é produzida como uma amostragem da
população anterior
• Variação nas frequências gênicas, puramente ao acaso, ligada
exclusivamente aos desvios padrões das frequências
σ ( p) =
pq
n
Deriva Gênica
• A frequência dos genes apresenta uma distribuição binomial
– Um alelo é de um determinado tipo OU não
• Cada geração nova é produzida como uma amostragem da
população anterior
• Variação nas frequências gênicas, puramente ao acaso, ligada
exclusivamente aos desvios padrões das frequências
σ ( p) =
pq
n
• O que aconteceria com uma população infinita?
• O que acontece na prática?
Deriva Gênica
• O que acontece na prática?
Deriva Gênica, em outras palavras...
• São variações que as frequências dos genes sofrem.
– Porque as populações são finitas e cada ser vivo deixa um número
variável de filhotes a cada geração
– É o resultado direto do efeito do desvio padrão no processo de
amostragem que acontece durante o ciclo reprodutivo
– Como o desvio padrão depende do tamanho das amostras: quanto
maior uma população menor a deriva gênica
Fluxo Gênico
• Introdução ou perda de cópias de um alelo na população
Seleção Natural: Definição
• Ela não é um agente ativo, nem uma entidade dotada de
mente ou vontade
• Trata-se de uma avaliação estatística da diferença de
sobrevivência (ou mortalidade) de organismos que são
diferentes em uma ou mais características
• A seleção natura não causa a sobrevivência diferencial, ela é a
sobrevivência diferencial
Seleção Natural: Definição
• “Pode atuar” em qualquer nível dos organismos:
–
–
–
–
Genes
Indivíduos
Populações
Espécies
• Em geral, assumimos que a unidade de seleção
natural é o indivíduo. A sobrevivência diferencial
se deve, então, às diferencias no fenótipo,
determinadas por um ou mais locos gênicos
Seleção Natural: Mecanismos
•
A seleção natura funciona com base em três premissas
1. Genótipos variam dentro de uma população e essa variação é
hereditária
2. Componentes bióticos e abióticos no ambiente de um
organismos agem como pressões seletivas
3. Genótipos melhor adaptados a essas pressões deixam mais
cópias
Seleção Natural: Mecanismos
• 1- Genótipos variam dentro de uma população e essa variação é
hereditária
• De onde vem a variação?
MUTAÇÃO!
• Como a nova variação é passada adiante? Reprodução! (deriva gênica)
• Durante a reprodução ocorre um processo chamado recombinação.
Que faz com que os novos alelos surgidos por mutação sejam
imediatamente colocados em uma variedade de ambientes
genéticos
– Isso é particularmente importante!
– O fenótipo é resultado da interação entre os diferentes genes de um
organismo
Seleção Natural: Mecanismos
• 2- Componentes bióticos e abióticos no ambiente de um
organismos agem como pressões seletivas
• Exemplo de fatores bióticos:
– Predadores
– Competidores
– Mutualistas
• Exemplo de fatores abióticos:
– Disponibilidade de recursos
– Condições físicas
– Condições químicas
• As pressões pode ter origem natural ou artificial
Seleção Natural: Mecanismos
•
3- Genótipos melhor adaptados a
essas pressões deixam mais cópias.
•
Adaptação: uma característica
geneticamente determinada que
melhora a habilidade de um
organismo de sobreviver e
reproduzir em um ambiente em
particular
•
Indivíduos melhor adaptados
possuem um maior valor adaptativo
(“fitness”)
Seleção Natural: Definição e valor adaptativo.
• A seleção natural é a reprodução diferencial dos indivíduos numa
população
– A mortalidade (ou sobrevivência) dos organismos não ocorre ao acaso
• É uma força determinista que causa uma mudança nas frequências
gênicas com sentido e direção determinados. Sempre na direção do
aumento do valor adaptativo médio das populações
• O que é valor adaptativo?
– É a contribuição relativa de um genótipo para a geração seguinte. A taxa
de sobrevivência de um determinado genótipo
– Valor adaptativo médio é a média dos valores adaptativos dos genótipos
em uma população ponderada pelas respectivas frequências
Seleção Natural: Valor adaptativo.
• O que é valor adaptativo.
– É a contribuição relativa de um genótipo para a geração seguinte. A taxa
de sobrevivência de um determinado genótipo.
– Valor adaptativo médio é a média dos valores adaptativos dos genótipos
em uma população ponderada pelas respectivas freqüências. Por
exemplo, um caso de vantagem do hereozigoto:
WAA = 0,9
WAa = 1,0
Com
p = 0,5 e q = 0,5
Logo
p2 = 0,25 2pq=0,5 q2=0,25
O valor adaptativo médio, W é
0,9x0,25+1,0x0,5+0,9x0,25 = 0,95
Waa = 0,9
Seleção Natural: Paisagem adaptativa
• Se podemos calcular o valor adaptativo médio de uma
população, podemos criar uma representação deste valor em
função de p ou q
• Isso é chamado de paisagem adaptativa (“fitness landscape”)
Seleção Natural: Paisagem adaptativa
• Se podemos calcular o valor adaptativo médio de uma
população, podemos criar uma representação deste valor em
função de p ou q.
• Isso é chamado de paisagem adaptativa (“fitness landscape”).
Seleção Natural: Paisagem adaptativa
• As paisagens adaptativas são particularmente úteis para se
vislumbrar o processo evolutivo.
• A escalada do monte improvável de R. Dawkins
• Múltiplos caminhos para os picos.
• ESS.
Estratégias
Evolutivamente
Estáveis.
Evolução, finalizando
•
Quais dos quatro mecanismos da evolução gera adaptação?
1. mutação
2. fluxo gênico
3. deriva gênica
4. seleção
•
Apenas a seleção natural! As outras forças geram variação sem ligação
com melhoria na sobrevivência em um dado ambiente
•
Como estas forças interagem?
– De fato, quanto menor o tamanho de uma população, maior o desvio padrão na
amostragem reprodutiva, assim, quanto menor uma população menores os efeitos
da seleção natural
– De forma análoga, quanto maior uma população, menores serão os efeitos da
deriva gênica
Uma grande ideia
• O conceito de paisagem adaptativa inspirou cientistas da área
de exatas
– Os pesquisadores vinham lidando com problemas cada vez mais
complexos e com formulações incompletas
– Em tais problemas os
métodos tradicionais de
otimização falhavam ou
tinham uma performance
inaceitável...
Uma solução natural
•
A natureza já havia resolvido o maior de todos os problemas há muito
tempo
–
Como o problema da sobrevivência é resolvido?
1. Possíveis soluções são codificadas no genoma (armazenadas no
DNA)
2. Essas possíveis soluções sofrem mudanças aleatórias que passam
de uma geração para outra, são copiadas com fidelidade
3. Essas mudanças causam diferenças na qualidade das soluções
4. Soluções diferentes podem ser combinadas dando ainda mais
variedade
5. As soluções piores, comparativamente, têm menor chance de se
perpetuar, isto é, deixar cópias ao longo das gerações
Uma solução natural
• Foi “apenas” uma questão de adaptar os cinco passos
para resolver outros problemas
• Surgiram os algoritmos genéticos
– Inspirados em processos naturais, cientistas criaram um poderoso
método de otimização, capaz de lidar com problemas de grande
complexidade
– Desde o seu surgimento têm sido aplicados a uma infinidade de
problemas interessantes em muitas áreas diferentes
Algoritmos genéticos
• Um algoritmo genético básico (standard GA).
Inicie a população P;
Avaliar aptidão dos indivíduos dessa população P;
Repita
Repita
Selecione 2 indivíduos de P ;
Aplique um operador de recombinação com probabilidade p(r);
Aplique operador de mutação com probabilidade p(m);
Insira os novos indivíduos em P’;
Até que P’ esteja completa;
Avalie a população P’;
P <- P’;
Até que critério de parada seja satisfeito;
Fim.
Algoritmos genéticos
• Codificação: as solução serão codificadas como no
genoma dos organismos reais
• Por exemplo,
– Estamos querendo encontrar um determinado tipo de configuração de
um peptídeo (pequena proteínas)
– A configuração 3D é determinada pelos ângulos PHI e PSI para cada
aminoácido da estrutura
– Uma solução possível pode ser codificada em uma lista de pares de
ângulos
(60, 50) (50, -60) (80, 75) (20, 60) ...
Algoritmos genéticos
• Codificação: as solução serão codificadas como no
genoma dos organismos reais
• Por exemplo,
(60, 50) (50, -60) (80, 75) (20, 60) ...
Algoritmos genéticos
• Criar uma população inicial
• Consiste em gerar as primeiras soluções para o problema
– Aleatória
– Segundo alguma informação sobre o problema
Algoritmos genéticos
• Avaliar a população
• Consiste em computar as aptidões das possíveis soluções
• Em outras palavras: determinar se uma solução é melhor
do que a outra
• Definindo a função objetivo
– A configuração que buscamos é a que possui o maior número de
pontes de hidrogênio
• Decodificar os ângulos em coordenadas cartesianas (x, y, z) e
contar as pontes de hidrogênio
(60, 50) (50, -60) (80, 75) (20, 60) ...

n pontes
Algoritmos genéticos
• Aplicar os operadores
• Escolher indivíduos para aplicar operadores que irão
gerar variação
– A escolha pode ser dependente da aptidão ou não (pressão seletiva)
• Aleatória, torneio e roleta são os métodos mais comuns
Algoritmos genéticos
• Operadores inspirados na biologia
– Mutação
(60, 50) (50, -60) (80, 75) (20, 60) ...  (60, 50) (30, -80) (80, 75) (25, 55) ...
– Crossover (recombinação)
• Outros operadores inspirados em fenômenos genéticos
• Aplicar operadores até construir uma nova população
Algoritmos genéticos
• Temos duas populações
• Como selecionar indivíduos dentre as duas população para
compor a próxima geração?
Algoritmos genéticos
• Temos duas populações
• Como selecionar indivíduos dentre as duas população para
compor a próxima geração?
• Substituição parental com base na aptidão
– Elitismo
– Fusão
Algoritmos genéticos
• Elitismo
Parental
Filhos
11
12
11
10
10
12
6
6
10
4
2
6
2
1
2
Valores de aptidão = número de pontes de H. Quanto maior melhor
Nova geração
Algoritmos genéticos
• Fusão
Parental
Filhos
11
12
10
10
6
6
4
2
2
1
Valores de aptidão = número de pontes de H. Quanto maior melhor
Nova geração
Algoritmos genéticos
12
11
• Fusão
Parental
Filhos
10
10
11
12
10
10
6
6
4
2
2
1
6
6
4
2
2
1
Valores de aptidão = número de pontes de H. Quanto maior melhor
Algoritmos genéticos
• Fusão
Parental
Filhos
11
12
12
10
10
11
6
6
10
4
2
10
2
1
6
Valores de aptidão = número de pontes de H. Quanto maior melhor
Nova geração
Algoritmos genéticos
• Repetir até...
– Atingida uma solução satisfatória
– Esgotado um orçamento computacional
– Atingido um tempo limita
Algoritmos genéticos
• De uma maneira relativamente simples as forças
evolutivas são implementadas para resolver uma grande
gama de problemas
• Os requisitos de acordo com o modelo de evolução biológica
de Darwin estão presentes
–
–
–
–
Reprodução de indivíduos na população
Variação que afeta a probabilidade de sobrevivência dos indivíduos
Hereditariedade na reprodução
Competição por recursos finitos
Algoritmos genéticos
• De uma maneira relativamente simples as forças
evolutivas são implementadas para resolver uma grande
gama de problemas
1. mutação  variação introduzida pelos operadores
genéticos
2. fluxo gênico  populações diferentes trocando informação
3. deriva gênica  variância natural, pois as populações são
finitas
4. seleção  critério de otimização
Fim