Combinatorial Pattern Matching BLAST

Combinatorial Pattern Combinatorial Pattern MatchingMatching

BLASTBLAST

TópicosTópicos• Introdução• Repetições Gênicas• Combinatorial Pattern Matching

– Exact Pattern Matching– Approximate Pattern Matching– Query Matching

• BLAST

IntroduçãoIntrodução• Genomas seqüenciados geram bases de dados

gigantescas, que crescem a cada dia• É importante comparar cada novo com os já

existentes, em busca de similaridades e respostas

• Muitas doenças podem ser identificadas através do genoma, o que aumenta ainda mais essa necessidade

• Algoritmos cada vez mais eficientes são necessários para atender à essa demanda crescente de comparações e para se adequar aos computadores atuais

GenBankGenBankSeqüências

0

2.000.000

4.000.000

6.000.000

8.000.000

10.000.000

12.000.000

14.000.000

16.000.000

1982

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000

2001

Ano

606

15 milhõesCrescimento do GenBank

Europeu Japonês

24h

HistóriaHistória

Repetições gênicas – Repetições gênicas – MotivaçãoMotivação

• Rearranjos gênicos geralmente são associados a repetições

• Revelam segredos evolutivos• Muitos tumores são caracterizados por

explosões de repetições• ATGGTCTAGGTCCTAGTGGTC• ATGGTCTAGGACCTAGTGTTC

Pode ser bem difícil encontrar repetições, principalmente não exatas

Combinatorial Pattern Matching –Combinatorial Pattern Matching –MotivaçãoMotivação

• Um grande problema em biologia computacional é buscar por um padrão numa grande base de dados

• Combinatorial Pattern Matching engloba vários algoritmos que fazem esse tipo de busca / comparação

• Entre os algoritmos existem aqueles que são exatos (buscam pelo padrão sem erros) ou aproximados (permitem substituições e às vezes gaps)

• Existem ainda algoritmos que buscam múltiplos padrões em um texto (Multiple Pattern Matching)

EXACT PATTERN EXACT PATTERN MATCHINGMATCHING

Descrição do ProblemaDescrição do Problema• Dado um padrão p e um texto t, encontrar

todas as ocorrências exatas de p em t.• Algoritmo de força

bruta:

– Padrão GCAT

– Texto CGCATC

GCATCGCATCGCATCGCATC

CGCATCGCATCGCATCGCATCGCATCGCAT

Algoritmo e ComplexidadeAlgoritmo e Complexidade

• Geralmente O(m)• Pior caso: O(m.n)

ProblemaProblema• Problema:

– Se n for grande demais, o algoritmo torna-se impraticável

• Exemplo:– Padrão: AAAAAA...AAA– Texto: AAAAAAAAAAAAAAA...AAAAA

SoluçãoSolução• Solução:

– 1973, Peter Weiner:• Uma nova estrutura de dados: Suffix Trees

– Resolvem este problema em O(m + n) para qualquer texto e qualquer padrão

• Suffix Tree paraATCATG

(...(...Keyword Tree / Suffix Tree

Keyword TreeKeyword Tree• Um conjunto de padrões

colocados numa árvore comuma raiz– Cada aresta é rotulada com

uma letra do alfabeto– Duas arestas vizinhas têm

rótulos diferentes– Cada padrão pode ser lido

varrendo-se a árvore da raizaté uma folha

Keyword Tree – ConstruçãoKeyword Tree – Construção• Apple

Keyword Tree – ConstruçãoKeyword Tree – Construção• Apple• Apropos

Keyword Tree – ConstruçãoKeyword Tree – Construção• Apple• Apropos• Banana

Keyword Tree – ConstruçãoKeyword Tree – Construção• Apple• Apropos• Banana• Bandana

Keyword Tree – ConstruçãoKeyword Tree – Construção• Apple• Apropos• Banana• Bandana• Orange

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Appeal”

– appeal

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Appeal”

– appeal

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Appeal”

– appeal

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Appeal”

– appeal

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Apple”

– apple

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Apple”

– apple

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Apple”

– apple

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Apple”

– apple

Busca na Keyword TreeBusca na Keyword Tree• Busca por “Apple”

– apple

ComplexidadeComplexidade• A complexidade do tempo de construção

da Keyword Tree é no melhor caso O(N), onde N é o tamanho de todos os padrões juntos

• Como utilizar Keyword Tree para fazer busca mais rapidamente?– Um padrão pode ser lido simplesmente lendo-

se da raiz até alguma folha– Então, buscar um padrão leva tempo O(n), n

sendo o tamanho do padrão• Melhor que O(m.n)

Complexidade (cont)Complexidade (cont)• Um texto de tamanho m tem

1 + 2 + ... + sufixos

• Tempo quadrático– O(m2)

• Ruim para ser construída• Mas...

Suffix TreeSuffix Tree• Estrutura de dados mais eficiente para

buscas de padrões• Derivada da Keyword Tree• Pode ser construída em tempo O(m)

– m é o tamanho do texto– Muito melhor que O(m2)

• Buscas em O(n)– Assim como na Keyword Tree

ExemploExemplo

...)...)Suffix Tree

Busca com Suffix TreeBusca com Suffix Tree

Suffix Tree para o texto ATGCATACATGG

ATGCATACATGG 1TGCATACATGG 2

GCATACATGG 3CATACATGG 4

ATACATGG 5TACATGG 6

ACATGG 7CATGG 8

ATGG 9TGG 10

GG 11G 12

Multiple Pattern MatchingMultiple Pattern Matching• Dado um conjunto de padrões p1, p2, ..., pk

e um texto t, encontrar se algum dos padrões aparece no texto

• Motivação– Buscar numa base de dados por k padrões

conhecidos– Uma das estratégias do BLAST

• Pode ser reduzido à k Pattern Matching

APPROXIMATE PATTERN APPROXIMATE PATTERN MATCHING /MATCHING /QUERY MATCHINGQUERY MATCHING

Approximate Pattern MatchingApproximate Pattern Matching• Dado um padrão p, um texto t e um inteiro

k, encontrar todas as ocorrências de p em t com no máximo k substituições

• Faz muito mais sentido biologicamente falando– Mutações– Evolução

• Utiliza-se heurísticas para aproximação

Buscas HeurísticasBuscas Heurísticas• Normalmente há um trecho bem

conservado, idêntico ou com pequenas variações.

• Muitas heurísticas são baseadas na idéia de filtragem– Encontrar uma “semente”, um pequeno trecho

que é idêntico (ou muito parecido)– Estender essa semente enquanto tiver menos

que k substituiçõesQuery: 22 VLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLK 60 +++DN +G + IR L G+K I+ L+ E+ RG++KSbjct: 226 IIKDNGRGFSGKQIRNLNYGIGLKVIADLV-EKHRGIIK 263

Matriz de pontosMatriz de pontos• Mostra a similaridade

entre duas strings

Matriz de pontosMatriz de pontos• Diagonais indicam

matches exatos• Buscamos por diagonais

respeitando o limitede mismatches

Matriz de pontosMatriz de pontos• Estendendo as diagonais

encontramos alinhamentos locaisaproximados

Query MatchingQuery Matching• Dado um padrão q, um texto t, um inteiro

k e um inteiro n, encontrar pares de posições (i , j) tais que a substring de tamanho n de q começada em i casa com a substring de tamanho n de t começada em j com no máximo k substituições

• Generalização do Approximate Pattern Matching

• Recebe um parâmetro a mais: um n referente ao “tamanho da janela”, que representa o tamanho médio dos matches

Query MatchingQuery Matching• Quando n é igual ao tamanho do padrão p

o problema de Query Pattern Matching se transforma no Aproximate Query Matching

ComparaçãoComparação

Query MatchingQuery Matching• Idéia central

– Buscar por alinhamentos pequenos– Filtragem

• Duas etapas– 1. Detecção de matches potenciais

• Divide a query em substrings de tamanho n (words) e busca por essas words no texto

– 2. Verificação desses matches potenciais• Estende para a esquerda e para a direita enquanto o

número de mismatches (substituições) seja menor que k

FASTAFASTA

FASTAFASTA• Desenvolvido por Pearson e Lipman• Apresenta os alinhamentos locais da

seqüência analisada com as seqüências do banco

• Procura por um número de k consecutivas letras (aminoácidos ou nucleotídeos), palavras ou k-tuplas.

AlgoritmoAlgoritmo• O algoritmo é dividido em 4 etapas:

– Seleção das 10 melhores regiões– Re-classificação das 10 melhores regiões– Seleção das seqüências mais semelhantes– Alinhamentos das seqüências selecionadas

BLASTBLAST

BLASTBLAST• Basic Local Alignment Search Tool

– Melhor algoritmo conhecido até hoje– Grande ganho de performance em troca de

uma pequena perda de sensibilidade• Funciona similar a uma Query Matching

Algoritmo (cont)Algoritmo (cont)• Fragmenta a query em words (l-mers)

– Por defalult, 3-mers paraproteínas

– e 11-mers paranucleotídeos

• Encontra words similares até um limiar (parâmetro)– Utiliza alguma matriz de substituição (Blosum,

PAM)

MEF EFP FPG PGL GLG

MEFPGLGSLGTSEPLPQFVDPALVSS

ACGTCGATCGT CGTCGATCGTA

ACGTCGATCGTACGTACGTAGCTTCA

Algoritmo (cont)Algoritmo (cont)

Algoritmo (cont)Algoritmo (cont)• PAM 250

Algoritmo (cont)Algoritmo (cont)

Query: 22 VLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLK 60 +++DN +G + IR L G+K I+ L+ E+ RG++KSbjct: 226 IIKDNGRGFSGKQIRNLNYGIGLKVIADLV-EKHRGIIK 263

Query: KRHRKVLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLKIFLENVIRD

word

GVK 18GAK 16GIK 16GGK 14GLK 13GNK 12GRK 11GEK 11GDK 11

vizinhos(limiar T = 13)

words vizinhos

Algoritmo (cont)Algoritmo (cont)• Procura por alguma dessas palavras na

base de dados (hit)• Estende os hits• BLAST original:

– Extensão feita para ambas as direções– Não permitia gaps

• BLAST atual:– Utiliza uma matriz de pontos– Permite gaps

Algoritmo (cont)Algoritmo (cont)• Retém somente os HSPs (High Score Pairs)

com score acima de um limiar (parâmetro)• Determina estatisticamente a relevância

de cada resultado– p-value ≈ 1 – – e-value ≈ 1 –

• Mais usado:– E < 10-100 genes homológos ou idênticos– E < 10-3 genes podem estar relacionados– E > 1 genes provavelmente sem relação– 0,5 < E < 1 Twilight Zone (não há garantia de

homologia ou não homologia)

BLASTBLAST• Existem diversas implementações do BLAST

– blastn• Compara uma seqüência de nucleotídeos com um

banco de nucleotídeos– blastp

• Seqüência de aminoácidos num banco de proteínas– blastx

• Seqüência de nucleotídeos (traduzidos em proteínas) com um banco de proteínas

– tblastn• Seqüência de proteínas com um banco de nucleotídeos

(traduzidos em real time)– tblastx

ExemplosExemplos• Suffix tree

– http://cs-people.bu.edu/lisap/CS549%20Final%20Project%20Webpage%20Applet.html

– http://pauillac.inria.fr/~quercia/documents-info/Luminy-98/albert/JAVA+html/SuffixTreeGrow.html

• Exact Pattern Matching– http://www-igm.univ-mlv.fr/~lecroq/string/

• BLAST– http://www.ncbi.nlm.nih.gov/Education/

BLASTinfo/tut1.html

ReferênciasReferências• http://www.qualidata.com.br/~fabricio/

tbo20051-suffixtree-fabricio.pdf• http://www.cs.unc.edu/Courses/comp590-

090-f07/• http://bioinf.ucsd.edu/~jung/beng202/• http://biotec.icb.ufmg.br/cabi/aulas/