Download PDF
ads:
Aspectos de genˆomica comparativa
Carlos Juliano Moura Viana
Disserta¸c˜ao de Mestrado
Orienta¸c˜ao:Prof.Dr. Nalvo Franco de Almeida Jr.
´
Area de Concentra¸c˜ao: Biologia Computacional
Durante a elabora¸c˜ao desse trabalho o autor recebe u apoio financeiro da CAPES.
dct ufms
Departamento de Computa¸c˜ao e Estat´ıstica
Centro de Ciˆencias Exatas e Tecnologia
Universidade Federal de Mato Grosso do Sul
Agosto/2006
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Aspectos de genˆomica comparativa
Este exemplar corresponde `a reda¸c˜ao final da
tese devidamente corrigida e defendida por
Carlos Juliano Moura Viana e aprovada pela
comiss˜ao julgadora.
Campo Grande/MS, 31 de agosto de 2006.
Banca Examinadora:
• Prof. Dr. Nalvo Franco de Almeida Junior - Orientador (DCT-UFMS)
• Profa. Dra. Maria Em´ılia Machado Te lles Walter (CIC-UNB)
• Prof. Dr. Said Sadique Adi (DCT-UFMS)
ads:
`a minha amada Amandita
e aos meus pais.
Agradecimentos
Tenho a oportunidade neste momento de fazer os meus agradecimentos a todas as pessoas
que me ajudaram a transpor mais uma etapa na minha vida.
Gostaria primeiramente de agradecer a Deus pela sa´ude, pois sem ela nada disso seria
poss´ıvel.
Agrade¸co a minha amada fam´ılia pelo carinho e pelo pleno apoio para continuar os
meus estudos.
Um agradecimento em especial `a minha amada Amandita pela sua enorme paciˆencia,
aten¸c˜ao, carinho, dedica¸c˜ao e pelos seus conselhos, que n˜ao me permitiram desanimar
jamais diante dos momentos dif´ıceis.
Ao professor Edson Norberto C´aceres que n˜ao mede esfor¸cos para melhorar os cursos
de Bacharelado e Mestrado em Ciˆencia da Computa¸c˜ao nesta universidade. Ao professor
Marcelo Henriques de Carvalho pelas suas dicas e colabora¸c˜ao com os trabalhos que
desenvolvi no mestrado. Agrade¸co ao professor Henrique Mongelli pelas recomenda¸c˜oes,
que trouxeram-me novamente para o t´ermino desse trabalho.
Gostaria de agradecer em especial, ao meu orientador, professor Nalvo Franco de
Almeida Junior, pela paciˆencia, conselhos, dicas e aten¸c˜ao dedicados, desde o projeto
final de curso at´e a conclus˜ao deste trabalho de mestrado.
As minhas ex-colegas de sala, Graziela e Luciana, pelas valiosas discuss˜oes em bio-
inform´atica. A minha amiga Bianca (B1), pelos incentivos, aux´ılios e pelas divertidas
conversas durante todo o mestrado. Aos meus amigos Cristiano, Anderson e M´arcio pelos
momentos descontra´ıdos que aliviaram os momentos dif´ıceis.
Em especial, ao meu amigo Cristiano, pelo convite e oportunidade de continuar tra-
balhando durante o final do mestrado, e pelos seus valiosos conselhos. Agrade¸co tamb´em
ao pessoal do Laborat´orio de Engenharia de Software (LEDES) pelo ´otimo acolhimento.
Enfim, agrade¸co desejando um muito obrigado a todos que me ajudaram de alguma
forma a concluir esse trabalho.
i
Resumo
Com o avan¸co no seq¨uenciamento de genomas e facilidade no acesso `as seq¨uˆencias, t´ecnicas
computacionais de an´alise comparativa tornaram-se indispens´aveis ferramentas para uma
melhor caracteriza¸c˜ao e compreens˜ao dos organismos em estudo. Um projeto genoma
consiste, basicamente, em 3 grandes fases: seq¨uenciamento, anota¸c˜ao e an´alise. A se-
gunda fase, anota¸c˜ao, consiste em determinar onde, em cada cromossomo, se encontram
as regi˜oes que codificam informa¸c˜oes gen´eticas, os genes, assim como em determinar a
caracteriza¸c˜ao funcional de cada gene. Na f ase de an´alise, busca-se uma caracteriza¸c˜ao
do organismo estudado, em termos de suas funcionalidades biol´ogicas, a partir das in-
forma¸c˜oes geradas nas duas fases anteriores. E ste trabalho est´a inserido no contexto da
an´alise do genoma. Especificamente, o trabalho consiste na total reformula¸c˜ao do pa-
cote de ferramentas denominado EGG. A reformula¸c˜ao inclui a reimplementa¸c˜ao de todo
o c´odigo-fonte, bem como a descri¸c˜ao e implementa¸c˜ao de novas metodologias e funcio-
nalidades. O objetivo principal ´e disponibilizar `a comunidade cient´ıfica um pacote com
um conjunto de ferramentas para a compara¸c˜ao de genomas no n´ıvel dos seus genes e
prote´ınas.
ii
Abstract
With the advance in the genome sequencing and easiness in accessing the sequences,
computational techniques of comparative analysis had become indispensable tools for a
better characterization and understanding of the organisms in study. A genome project
consists basically in 3 major phases: sequencing, annotation and analysis. The second
phase, annotation, consists of determining, in each chromosome, where genetic coding
regions are as well as in determining the functional characterization of each gene. In the
analysis, the goal is a characterization of the organism of interest, in terms of its biological
functionalities, from the information generated in the two previous phases. This work is
inserted in the context of the analysis of the genome. Specifically, the work consists of
the total reformularization of the package of tools named EGG . T he reformularization
includes reimplementing of the source code, as well as description and implementation of
new methodologies and features. The main goal is to give to the scientific community a
package with a set of tools for genome comparison in the level of its genes and proteins.
iii
Sum´ario
Agradecimentos i
Resumo ii
Abstract iii
1 Introdu¸c˜ao 1
2 Preliminares 4
2.1 Fundamentos b´asicos de Biologia Molecular . . . . . . . . . . . . . . . . . 4
2.2 Fundamentos b´asicos de Computa¸c˜ao . . . . . . . . . . . . . . . . . . . . . 6
2.3 Compara¸c˜ao de seq¨uˆencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 BLAST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Compara¸c˜ao de dois genomas 12
3.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.1 Genes Espec´ıficos e Ort´ologos . . . . . . . . . . . . . . . . . . . . . 15
3.1.2 Regi˜oes espec´ıficas (REs) . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.3 Regi˜oes Ort´ologas (ROs) . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.4 Espinha dorsal dos proteomas . . . . . . . . . . . . . . . . . . . . . 17
3.2 Nova implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 Descri¸c˜ao das fases de egg . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Novas Funcionalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Outras ferramentas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Determina¸c˜ao de genes par´alogos 35
iv
4.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1 Agrupamento de seq¨uˆencias . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2 Busca hom´ologos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Compara¸c˜ao de trˆes genomas 41
5.1 Comparando trˆes genomas . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2 Descri¸c˜ao do M´etodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.4 Alguns resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6 Considera¸c˜oes finais 48
A Detalhes operacionais de egg 50
A.1 Descri¸c˜ao das Ferramentas . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
A.2 Exemplos de alguns arquivos de sa´ıda . . . . . . . . . . . . . . . . . . . . . 54
B Detalhes operacionais para obter par´alogos 65
B.1 Pacote PARALOGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
B.2 Exemplos de alguns arquivos de sa´ıda . . . . . . . . . . . . . . . . . . . . . 66
Referˆencias Bibliogr´aficas 69
v
Lista de Algoritmos
1 Subseq
¨
u
ˆ
encias-Maximais . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Constr
´
oi-Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Junta-Runs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 M
´
etodo-3GC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
vi
Lista de Figuras
2.1 Exemplo da representa¸c˜ao de como as duas fitas de DNA pareiam. . . . . . 5
2.2 Exemplo de um grafo com seis v´ertices. . . . . . . . . . . . . . . . . . . . . 7
2.3 Exemplo de um grafo bipartido. . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Exemplo de uma clique de tamanho 3. . . . . . . . . . . . . . . . . . . . . 8
2.5 Exemplo de uma clique de tamanho 4 maximal. . . . . . . . . . . . . . . . 8
3.1 Exemplo de representa¸c˜ao dos genes de um proteoma G. . . . . . . . . . . 13
3.2 Representa¸c˜ao de uma RO. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Representa¸c˜ao de uma Espinha Dorsal. . . . . . . . . . . . . . . . . . . . . 14
3.4 Exemplo de uma regi˜ao espec´ıfica. . . . . . . . . . . . . . . . . . . . . . . . 23
3.5 Exemplo de um run paralelo consistente. . . . . . . . . . . . . . . . . . . . 25
3.6 Representa¸c˜ao gr´afica de run . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.7 Exemplo de uma RO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.8 Representa¸c˜ao gr´afica da RO. . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.9 Trecho do arquivo texto da espinha dorsal direta entre os BBHs dos geno-
mas dos organismos Xac e Xcc . . . . . . . . . . . . . . . . . . . . . . . . 28
3.10 Trecho do arquivo de BBHs entre genes do organismo Cg e ESTs do orga-
nismo Pb. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.11 Trecho do arquivo de matches entre genes do organismo Pa e ESTs do
organismo Pb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.12 Trecho do arquivo de genes esp ec´ıficos do organismo Ao em rela¸c˜ao as ESTs
do organismo Pb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 Representa¸c˜ao de uma JMC. . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Fluxo de execu¸c˜ao da fase Busca Hom´ologos . . . . . . . . . . . . . . . . . 38
4.3 Uma fam´ılia encontrada em Xylella fastidiosa 9a5c. . . . . . . . . . . . . . 39
vii
5.1 Diagrama de Venn representando (a) seq¨uˆencias exclusivas a um genoma,
(b) seq¨uˆencias compartilhadas por dois genomas, e (c) seq¨uˆencia comparti-
lhadas aos trˆes genomas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2 Genes que podem se r atribu´ıdos as regi˜oes do diagrama de Venn. . . . . . . 42
5.3 Casos complexos de atribui¸c˜ao dos genes `as regi˜oes do diagrama de Venn. . 43
5.4 Diagramas de Venn gerados pela compara¸c˜ao entre dois genomas de fungos
pat´ogenos e cinco genomas de fungos n˜ao-pat´ogenos. . . . . . . . . . . . . 47
A.1 Trecho do arquivo xacxcc.12. . . . . . . . . . . . . . . . . . . . . . . . . . 54
A.2 Trecho do arquivo xacxcc.1. . . . . . . . . . . . . . . . . . . . . . . . . . . 54
A.3 Trecho do arquivo atsm.bbh. . . . . . . . . . . . . . . . . . . . . . . . . . . 55
A.4 Exemplo de uma espinha dorsal entre os genomas dos organismos Xac e Xcc. 56
A.5 Trecho do arquivo atml.exc. . . . . . . . . . . . . . . . . . . . . . . . . . . 57
A.6 Trecho do arquivo atsm.k12. . . . . . . . . . . . . . . . . . . . . . . . . . . 58
A.7 Trecho do arquivo xacxcc.mul. . . . . . . . . . . . . . . . . . . . . . . . . 59
A.8 RO resultante da compara¸c˜ao entre os genomas dos organismos Xac e Xcc. 60
A.9 Exemplo de um run paralelo consistente entre os genomas dos organismos
Sm e Ml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
A.10 Regi˜ao espec´ıfica do genoma do organismo At em rela¸c˜ao ao genoma do
organismo Sm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
A.11 Plotagem do alinhamento obtido pelo LCS entre os BBHs dos genomas dos
organismos Xac e Xcc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
A.12 Plotagem dos BBHs entre os genomas dos organismos Xac e Xcc. . . . . . 64
B.1 Componente conexa encontrada no grafo gerado a partir das prote´ınas do
genoma do organismo Pa. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
B.2 Trecho do arquivo papa.comps. . . . . . . . . . . . . . . . . . . . . . . . . 67
B.3 Clique maximal enc ontrada no grafo gerado para o genoma do organismo
Ssp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
B.4 Fam´ılia encontrada ap´os eliminar as seq¨uˆencias discrepantes de sua clique
maximal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
B.5 Fam´ılia encontrada ap´os agregar uma nova prote´ına. . . . . . . . . . . . . . 68
viii
Lista de Tabelas
4.1 Informa¸c˜oes das fam´ılias encontradas em cada genoma. . . . . . . . . . . . 40
ix
Cap´ıtulo 1
Introdu¸c˜ao
Os avan¸cos na ´area de Biotecnologia, em especial no desenvolvimento de t´ecnicas de
seq¨uenciamento de DNA, tˆem produzido uma gigantesca massa de dados biol´ogicos, tra-
duzidos em seq¨uˆencias de DNA e de prote´ına. O grande desafio criado a partir da gera¸c˜ao
desses dados ´e a tarefa de analis´a-los e transform´a-los em informa¸c˜oes biol´ogicas rele-
vantes, capazes de proporcionar aos pesquisadores novas habilidades. Essas habilidades
incluem, por exemplo, novas t´ecnicas para diagn´ostico e tratamento de doen¸cas gen´eticas.
Em uma vis˜ao mais ampla, as descobertas feitas a partir dessas an´alises devem ser capa-
zes de nos proporcionar um maior entendimento dos mecanismos biol´ogicos que ditam as
funcionalidades dos seres vivos.
A utiliza¸c˜ao da Ciˆencia da Computa¸c˜ao no tratamento dessas informa¸c˜oes ´e impres-
cind´ıvel, n˜ao somente pela grande quantidade de dados gerados ou pelo tamanho das
seq¨uˆencias, mas tamb´em pela possibilidade de se des envolverem novas t´ecnicas computa-
cionais para resolver problemas de Biologia Molecular. Essas novas t´ecnicas deram origem
a uma nova ´area de pesquisa, denominada Bioinform´atica ou Biologia Computacional.
O crescimento constante da Biologia Computacional tornou-se mais evidente com os
in´umeros genomas seq¨uenciados nos ´ultimos anos. Um projeto genoma consiste basi-
camente em trˆes grandes fases: o seq ¨uenciamento, anota¸c˜ao e an´alise. O seq¨uenciamento
consiste na obten¸c˜ao da seq¨uencia exata de nucleot´ıdeos que comp˜oe cada cromossomo
do organismo estudado. A anota¸c˜ao ´e a tarefa de descobrir onde, em cada cromossomo,
se encontram as regi˜oes que codificam informa¸c˜oes gen´eticas, denominadas genes, al´em
da determina¸c˜ao da fun¸c˜ao biol´ogica de cada um desses genes. A ´ultima fase, de an´alise,
consiste em determinar as funcionalidades biol´ogicas gerais do organismo, a partir das
informa¸c˜oes geradas na fase de anota¸c˜ao e seq¨uenciamento.
Este trabalho se insere na fase de an´alise de um genoma. Em particular, estamos interessa-
dos no desenvolvimento de t´ecnicas e metodologias para a compara¸c˜ao de genomas. Essas
compara¸c˜oes podem elucidar quest˜oes relacionadas a funcionalidades comuns e espec´ıficas
importantes dos organismos. Uma forma de auxiliar na descoberta de tais informa¸c˜oes
relevantes passa, certamente, pela de termina¸c˜ao dos pap´eis que os mais diversos objetos
envolvidos num genoma desempenham. Esses pap´eis est˜ao muitas vezes relacionados `as
caracter´ısticas estruturais de cada objeto. Isso acontece de forma bem clara no caso de
prote´ınas, que tˆem suas fun¸c˜oes determinadas diretamente pela sua forma e estrutura.
1
Assim, ´e de se esperar que a compara¸c˜ao entre obje tos, nas suas formas mais prim´arias,
nos tragam pistas de relacionamentos entre eles e, por conseq¨uˆencia, entre suas funciona-
lidades [1].
No caso de genomas ´e de se esperar, portanto, que a compara¸c˜ao entre seus objetos, espe-
cificamente seq¨uˆencias de DNA e seus genes, seja ´util na determina¸c˜ao de funcionalidades
comuns. A id´eia ent˜ao ´e termos ferramentas que evidenciem aspectos funcionais comuns,
al´em de proporcionarem uma melhor compreens˜ao de como os genes se organizam nos
diversos genomas.
Especificamente, a compara¸c˜ao de genomas tem como principais objetivos:
• detec¸c˜ao de similaridades e diferen¸cas entre genomas completos, no n´ıvel de DNA;
• identifica¸c˜ao de genes ou grupos de genes envolvidos em diversas fun¸c˜oes;
• identifica¸c˜ao de genes ou grupos de genes respons´aveis por caracter´ısticas fenot´ıpicas
peculiares a um genoma particular;
• identifica¸c˜ao de genes hom´ologos (genes descendentes de um mesmo gene ancestral);
• anota¸c˜ao de genes de genomas n˜ao completos; e
• inferˆencia de rela¸c˜oes filogen´eticas entre os organismos.
Hist´orico e Justificativa
Objetivando o desenvolvimento de ferramentas computacionais para a compara¸c˜ao de dois
genomas, o trabalho desenvolvido por Almeida [1], em 2002, foi apresentado como tese
de doutorado no Instituto de Computa¸c˜ao da Unicamp. Uma das ferramentas propostas
em [1], denominada egg, compara dois proteomas. O proteoma de um organismo ´e o
conjunto de prote´ınas expressas por seus genes. egg foi inicialmente proposto em [3],
reformulado em [4] e em [1], e sendo utilizado com sucesso em v´arios projetos genoma
[9, 12, 15, 20, 21, 24, 26, 37, 45, 46]. egg leva em considera¸c˜ao as posi¸c˜oes relativas dos
genes nos cromossomos.
Apesar das reformula¸c˜oes sofridas e apesar de ter sido intensamente utilizada, a ferramenta
egg ainda necessita de reformula¸c˜oes visando a melhoria de desempenho e portabilidade,
al´em do acr´escimo de novas funcionalidades. Este trabalho consiste na reformula¸c˜ao e
reimplementa¸c˜ao de egg.
Sum´ario de resultados
Os principais resultados deste trabalho s˜ao:
• total reformula¸c˜ao do c´odigo dos programas contidos na ferramenta egg;
2
• implementa¸c˜ao de metodologia para encontrar regi˜oes espec´ıficas – essa metodologia
foi proposta em [1] mas n˜ao havia sido implementada;
• desenvolvimento e implementa¸c˜ao de nova metodologia para encontrar genes par´alogos
(genes hom´ologos pertencentes ao mesmo organismo);
• desenvolvimento e implementa¸c˜ao de uma vers˜ao de egg, chamada egg-lite, para
a compara¸c˜ao de genomas incompletos, onde se tem apenas genes, ou transcritos do
organismo, sem o seq¨uenciamento completo dos cromossomos;
• desenvolvimento e implementa¸c˜ao de m´odulo para a compara¸c˜ao de trˆes proteomas.
Ap´os essa reformula¸c˜ao, os c´odigos-fonte de egg, al´em de manuais e documenta¸c˜ao
encontram-se dispon´ıveis para download em http://egg.dct.ufms.br/egg.
A aplica¸c˜ao das novas metodologias inseridas em egg foram utilizadas em trabalhos de
pesquisa e resultaram na co-autoria das publica¸c˜oes [5, 41, 47]. Al´em disso, a experiˆencia
adquirida durante o programa de mestrado permitiu ainda a co-autoria de [44].
Organiza¸c˜ao do texto
O texto est´a organizado da seguinte forma. No Cap´ıtulo 2 alguns conceitos b´asicos e
nota¸c˜oes preliminares s˜ao apresentados. O Cap´ıtulo
3 traz a metodologia para a com-
para¸c˜ao de dois genomas. No Cap´ıtulo 4 a nova metodologia para a determina¸c˜ao de
genes par´alogos ´e apresentada. No Cap´ıtulo 5 a metodologia para a compara¸c˜ao de trˆes
genomas ´e descrita. Finalmente, o C ap´ıtulo 6 traz coment´arios conclusivos e propostas
para trabalhos futuros.
3
Cap´ıtulo 2
Preliminares
Neste cap´ıtulo abordamos descri¸c˜oes de conceitos e nota¸c˜oes utilizados no trabalho. Des-
crevemos alguns conceitos b´asicos de Biologia Molecular e de Computa¸c˜ao. Estes con-
ceitos permitem uma melhor interpreta¸c˜ao e compreens˜ao das metodologias descritas no
cap´ıtulos posteriores.
Na Se¸c˜ao 2.1 descrevemos alguns f undamentos b´asicos da Biologia Molecular. A Se¸c˜ao 2.2
traz alguns fundamentos b´asicos de Computa¸c˜ao. Na Se¸c˜ao 2.3 descrevemos conceitos
envolvendo a compara¸c˜ao entre seq¨uˆencias, como: alinhamento; o m´etodo de programa¸c˜ao
dinˆamica para a compara¸c˜ao entre duas seq¨uˆencias; e um m´etodo pr´atico para a busca em
bases de dados. Por fim, na Se¸c˜ao 2.4, descrevemos uma conhecida ferramenta utilizada
na compara¸c˜ao de seq¨uˆencias.
2.1 Fundamentos b´asicos de Biologia Molecular
Neste trabalho utilizamos DNA,(da l´ıngua inglesa DeoxyriboNucleic Acid) para referen-
ciar uma seq¨uˆencia de letras escritas no alfabeto formado por A, C, G, T, e RNA (da l´ıngua
inglesa RiboNucleic Acid) para referenciar uma seq¨uˆencia de letras escritas no alfabeto
A, C, G, U. Essas letras representam as bases nitrogenadas: Adenina, Citosina, Guanina e
Timina.
A base nitrogenada ´e um componente de uma estrutura b´asica denominada de nu-
cleot´ıdeo. Um nucleot´ıdeo ´e um composto qu´ımico que consiste de uma mol´ecula de
a¸c´ucar denominada 2
-deoxyribose no caso de DNA e 2
-ribose no caso de RNA, por
uma mol´ecula de fosfato e por uma base nitrogenada. Existem quatro tipos diferentes
de nucleot´ıdeos, um para cada base, observando-se que a base nitrogenada T no DNA
corresponde a base nitrogenada U no RNA.
A mol´ecula de a¸c´ucar cont´em cinco ´atomos de carbono que s˜ao rotulados de 1
para 5
.
Os nucleot´ıdos conectam-se atrav´es da liga¸c˜ao entre o carbono 5
de um nucleot´ıdeo com
o carbono 3
do nucleot´ıdeo seguinte, utilizando a mol´ecula de fosfato. Dessa forma, a
m´olecula resultante, denominada cadeia simples de DNA, possui por conven¸c˜ao, uma
orienta¸c˜ao, de 5
para 3
.
4
A uni˜ao dos nucleot´ıdeos em duas cadeias (fitas) interligadas e anti-paralelas com a con-
forma¸c˜ao de dupla-h´elice formam a seq¨uˆencia de DNA. Para designar um conjunto de
poss´ıveis nucleot´ıdeos em uma determinada posi¸c˜ao da seq¨uˆencia de DNA, s˜ao admitidas
letras adicionais. Esse alfabeto ´e descrito em [27]
O DNA inteiro de um organismo ´e denominado genoma. O genoma costuma variar em
tamanho de acordo com a esp´ecie, desde milh˜oes de letras, no caso das bact´erias, at´e
bilh˜oes de letras, no caso de mam´ıferos. Genomas s˜ao compostos tamb´em por longas
seq¨uˆencias de DNA, que costumam ser divididas em unidades denominadas de cromos-
somos. Um cromossomo ´e formado por duas cadeias (fitas) de DNA que se “torcem”
uma sobre a outra.
As duas fitas de DNA s˜ao unidas pela liga¸c˜ao das bases de seus nucleot´ıdeos. A base
A sempre liga-se a base T e a base G sempre liga-se a base C. Os pares A-T e C-G s˜ao
denominados pares de bases complementares. Esses pares s˜ao conhecidos como pares
de base Watson-Crick. As duas fitas s˜ao ditas anti-paralelas, pois possuem orienta¸c˜oes,
da extremidade 5
→ 3
, opostas uma em rela¸c˜ao a outra.
No decorrer do texto, consideramos o DNA como uma seq¨uˆencia de letras, onde cada letra
representa uma base. Na Figura 2.1 apresentamos um exemplo da representa¸c˜ao do DNA
como duas seq¨uˆencias de letras, com cada letra de uma seq¨uˆencia justaposta a outra. As
seq¨uˆencias (fitas) de DNA s˜ao escritas uma sobre a outra revelando o pareamento entre
as bases.
Uma fita ´e dita ser o complemento-reverso da outra. O complemento-reverso de um
trecho de DNA G ser´a denotado aqui por G
CR
.
5’ ... A T G G G C A C C G T G C G C ... 3’
| | | | | | | | | | | | | | |
3’ ... T A C C C G T G G C A C G C G ... 5’
Figura 2.1: Exemplo da representa¸c˜ao de como as duas fitas de DNA pareiam.
Utiliza-se como unidade de medida de c omprimento de um trecho de DNA, de fita dupla,
o n´umero de pares de bases, denotado por bp (do inglˆes base pair). N´umeros maiores
em geral s˜ao representadas por Kb (10
3
bp) e Mb (10
6
bp).
A seq¨uˆencia de pares de bases do DNA de um organismo cont´em a informa¸c˜ao necess´aria
para a s´ıntese de prote´ınas. As prote´ınas s˜ao seq¨uˆencias de letras pertencentes ao alfa-
beto de 20 amino´acidos. Trˆes nucleot´ıdeos codificam um amino´acido. A tabela que per-
mite corresponder cada tripla de nucleot´ıdeos em um amino´acido ´e denominada c´odigo
gen´etico.
Combinando os 4 nucleot´ıdeos em triplas, obtemos 64 combina¸c˜oes de poss´ıveis triplas
de nucleot´ıdeos. Cada uma das combina¸c˜oes ´e denominada de codon. Como temos
apenas 20 amino´acidos, mas 64 codons poss´ıveis, temos que alguns codificam o mesmo
amino´acido.
5
Dentre os 64 codons poss´ıveis, 3 n˜ao especificam amino´acidos. Esses codons s˜ao denomi-
nados de codons de parada (ou stop codons), que sinalizam a termina¸c˜ao da tradu¸c˜ao
de uma seq¨uˆencia do alfabeto de nucleot´ıdeo para o alfabeto de amino´acidos. O c´odigo
gen´etico estabelece tamb´em um codon de in´ıcio (ou start codon), que indica o in´ıcio do
processo de tradu¸c˜ao.
Os trechos da seq¨uˆencia de bases do DNA que s˜ao codificados em informa¸c˜ao gen´etica s˜ao
denominados de genes. Existem dois tipos de genes, aqueles que codificam prote´ınas (a
maioria) e aqueles que n˜ao codificam prote´ınas (codificam RNAs).
O conjunto de genes de um genoma que codificam prote´ınas ´e denominado de proteoma.
Utilizamos os termos gene e prote´ına indistintamente, apesar de sabermos que um gene
pode codificar mais de uma prote´ına e que existem genes que n˜ao codificam prote´ınas.
Na anota¸c˜ao de genomas tentamos predizer quais genes codificam uma ou mais prote´ınas.
Dessa forma, comumente utilizamos o termo prote´ına predita de um determinado gene.
Em nosso trabalho, estamos interessados nos genes que s˜ao hom´ologos, ou seja, genes que
evoluiram a partir de um gene ancestral comum. Especificamente, estamos interessados
nos genes ort´ologos e par´alogos. Dois genes g e h s˜ao denominados de ort´ologos se
ambos descendem de um mesmo gene ancestral e pertencem a esp´ecies distintas. Quando
os genes g e h descendem de um mesmo gene ancestral, por´em pertencem a um mesma
esp´ecie, g e h s˜ao denominados par´alogos. A rela¸c˜ao (g, h) entre genomas distintos ´e
donominada “par de genes ort´ologos”.
Na se¸c˜ao seguinte abordamos alguns conceitos b´asicos computacionais com o objetivo de
prover informa¸c˜oes suficientes para a compreens˜ao das metodologias descritas no decorrer
do texto.
2.2 Fundamentos b´asicos de Computa¸c˜ao
Uma cadeia ´e um sucess˜ao de caracteres ou s´ımbolos de um conjunto finito denominado
de alfabeto. Utilizamos o termo seq¨uˆencia como um sinˆonimo para o termo cadeia.
As seq¨uˆencias podem ter s´ımbolos repetidos, por exemplo s = TGCATT. O tamanho de
um seq¨uˆencia s, denotado por |s|, ´e o n´umero de s´ımbolos em s. Para o exemplo anterior,
|s| = 6. Um s´ımbolo que ocupa a posi¸c˜ao i em uma seq¨uˆencia s ´e denotado por s
i
. Logo,
uma seq¨uˆencia s ´e composta pelos s´ımbolos s
1
, . . . s
|s|
. Quando |s| = 0, denominamos s
de seq¨uˆencia vazia.
Apesar dos termos cadeia e seq¨uˆencia possu´ırem o mesmo significado, os termos subca-
deia e subseq ¨uˆencia representam conceitos distintos. Uma subseq¨uˆencia de s ´e uma
seq¨uˆencia que pode ser obtida a partir de s pela remo¸c˜ao de alguns de seus s´ımbolos.
Considerando a seq¨uˆencia exemplo s anteriormente, GAT ´e uma subseq¨uˆencia de s, mas
GTAT n˜ao ´e subseq¨uˆencia de s. Uma subcadeia de s ´e uma cadeia formada p elos s´ımbolos
consecutivos de s, na mesma ordem em que aparecem em s. Considerando novamente a
cadeia s como exemplo, GCA ´e uma subcadeia de s, mas GAT n˜ao ´e uma subcadeia de s.
Dado duas s eq¨uˆencias X e Y , dizemos que uma seq¨uˆencia Z ´e uma subseq¨uˆencia comum
de X e Y se Z ´e uma subseq¨uˆencia de ambos X e Y . Como exemplo, considere as
6
seq¨uˆencias A = ACGTACAG e B = TGAACC. A seq¨uˆencia GAC ´e uma subseq¨uˆencia comum
de A e B. Um segmento de uma seq¨uˆencia ´e uma subcadeia da seq¨uˆencia.
Alguns problemas computacionais envolvem subcadeias e subseq¨uˆencias, como o problema
de determinar uma subcadeia de m´axima soma de uma cadeia de n´umeros reais S; sua
generaliza¸c˜ao, que consiste em determinar n˜ao apenas uma, mas todas as subcadeias de
m´axima soma; e o problema de determinar a subseq¨uˆencia comum mais longa (LCS).
Podemos descrever o problema das subcadeias maximais e do LCS da se guinte forma:
Defini¸c˜ao 2.1 (Problema das subcadeias maximais) A entrada ´e uma cadeia ou
seq¨uˆencia (x
1
, x
2
, . . . , x
n
), de n´umeros reais (n˜ao necessariamente positivos), denominada
de “pontua¸c˜ao”. O objetivo consiste em identificar todas as subcadeias que possuem maior
pontua¸c˜ao, onde a pontua¸c˜ao S
i,j
de uma subcadeia (x
i
, x
i+1
, . . . , x
j
) ´e obtida simplesmente
pela soma de seus elementos:
S
i,j
=
j
k=i
x
k
Defini¸c˜ao 2.2 (Problema da subseq¨uˆencia comum mais longa - LCS) Dadas duas
seq¨uˆencias X = (x
1
, x
2
, . . . , x
m
) e Y = (y
1
, y
2
, . . . , y
n
), desejamos encontrar a subseq¨uˆencia
comum de tamanho m´aximo entre X e Y .
Uma melhor caracteriza¸c˜ao do problema do LCS pode ser encontrada em [14].
Um grafo G ´e uma tripla ordenada (V (G), E(G), ψ
G
) consistindo de um conjunto n˜ao
vazio V (G) de v´ertices, um conjunto E(G) (disjunto de V (G)) de arestas, e uma fun¸c˜ao
de incidˆe ncia ψ
G
que associa a cada aresta de G um par n˜ao ordenado de (e n˜ao ne-
cessariamente distinto) v´ertices de G. Se e ´e uma aresta e u e v s˜ao v´ertices tais que
ψ
G
(e) = (u, v), ent˜ao dizemos que e liga u a v. Os v´ertices u e v s˜ao denominados
extremos de e. Na Figura 2.2 apresentamos um grafo com um conjunto de v´ertices
V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
} e com um conjunto de arestas E = {e
1
, e
2
, e
3
, e
4
, e
5
}.
v
1
v
2
v
3
v
4
v
5
v
6
e
1
e
2
e
3
e
4
e
5
Figura 2.2: Exemplo de um grafo com seis v´ertices e cinco arestas.
Em um grafo G, se todo v´ertice ´e “ating´ıvel” pelos outros v´ertices, dizemos que o grafo
G ´e conexo. Quando um grafo n˜ao ´e conexo, podemos determinar suas componentes
conexas. A Figura 2.2 ilustra um grafo com duas componentes conexas.
7
Um grafo G ´e bipartido se o seu conjunto de vertices V pode ser particionado em dois
conjuntos X e Y tais que, qualquer aresta (u, v) ´e tal que: u ∈ X e v ∈ Y , ou u ∈ Y
e v ∈ X. Na Figura 2.3 apresentamos um grafo bipartido com cinco v´ertices e quatro
arestas.
v
1
v
2
v
3
v
4
v
5
e
1
e
2
e
3
e
4
Figura 2.3: Exemplo de um grafo bipartido, tal que X = {v
1
, v
2
, v
3
} e Y = {v
3
, v
4
}.
Um conjunto C de v´ertices de um grafo G(V, E) ´e uma clique, se para todo par u, v de
v´ertices distintos em C, existe uma aresta (u, v) ∈ E. Uma clique C em G ´e maximal,
se n˜ao existe outra clique C
em G que contenha C propriamente. As Figuras 2.4 e 2.5
ilustram, respectivamente, um exemplo de uma clique e de clique maximal no grafo G.
v
1
v
2
v
3
v
4
v
5
Figura 2.4: Exemplo de uma clique de tamanho 3 formada pelos v´ertices v
1
, v
2
e v
3
.
v
1
v
2
v
3
v
4
v
5
Figura 2.5: Exemplo de uma clique de tamanho 4 maximal formada pelos v´ertices v
2
, v
3
, v
4
e v
5
.
Um Modelo Oculto de Markov (HMM) ´e uma base formal para constru¸c˜ao de modelos
probabil´ısticos. O modelo provˆe um conjunto de ferramentas conceituais para a constru¸c˜ao
de modelos complexos simplesmente pelo desenho de uma figura intuitiva [18]. Os modelos
de Markov s˜ao bem adequados para muitas tarefas em Biologia Molecular e s ˜ao o n´ucleo
de uma diversa faixa de programas, incluindo os programas para procurar genes, buscar
8
por perfis, obter alinhamento m´ultiplo e identificar regi˜oes regulat´orias em DNA. Segundo
Eddy [18], HMMs s˜ao os “legos” da an´alise computacional de seq¨uˆencias.
Em uma descri¸c˜ao mais formal, um modelo oculto de markov M ´e definido por um
alfabeto Σ, um conjunto de estados (escondidos) Q, uma matriz das probabilidades de
transi¸c˜ao de estados A, e uma matriz de probabilidades de emiss˜ao de s´ımbolos E, mais
especificamente:
• Σ ´e um alfabeto de s´ımbolos;
• Q ´e um conjunto de estados que emitem s´ımbolos do alfabeto Σ;
• A = (a
kl
) ´e uma matriz |Q| × |Q| das probabilidades de transi¸c˜ao de estados; e
• E = (e
k
(b)) ´e uma matriz |Q| × |Σ| das probabilidades de emiss˜ao de s´ımbolos;
Um caminho π = π
1
. . . π
n
em um HMM M ´e uma seq¨uˆencia de estados. A probabilidade
de que uma seq¨uˆencia x de s´ımbolos tenha sido gerada por uma seq¨uˆencia de estados π
dado um modelo M ´e :
P (x|π) =
n
i=1
P (x
i
|π
i
)P (π
i
|π
i+1
) = a
π
0
,π
1
·
n
i=1
e
π
i
(x
i
) · a
π
i
,π
i+1
Convenientemente inserimos π
0
e π
n+1
como os fict´ıcios estados iniciais e terminais in´ıcio
e fim.
Na grande maioria das aplica¸c˜oes, deseja-se conhecer, dada uma seq¨uˆencia x de s´ımbolos,
que ´e a parte n˜ao-oculta do modelo, qual a seq¨uˆencia de estados (o caminho π) mais
prov´avel de ocorrer. Ou seja, π ´e o componente oculto do modelo.
Um simples exemplo ´e o de lan¸camento de 3 moedas, m
1
, m
2
, m
3
, divulgando apenas a
seq¨uˆencia de resultados (cara ou coroa) e perguntando ao modelo qual ´e a seq¨uˆencia de
moedas lan¸cadas, ou seja, para cada lan¸camento, qual foi a moeda lan¸cada.
Neste caso,
• Σ = {cara, coroa};
• Q = {m
1
, m
2
, m
3
};
• A ´e a matriz que indica a probabilidade do lan¸cador trocar de moeda; e
• E ´e a matriz que dita o v´ıcio de cada moeda.
A utiliza¸c˜ao mais popular de HMM em Biologia Molecular ´e como um “perfil proba-
bil´ıstico” de uma fam´ılia de prote´ınas, o qual ´e denominado de perfil HMM (pHMM).
A partir de fam´ılias de prote´ınas ou de DNA, um perfil HMM pode s er constru´ıdo para
buscar, em uma base de dados, por outros membros da fam´ılia.
Um Perfil ´e uma simples representa¸c˜ao de uma fam´ılia de prote´ınas relacionadas, que ´e
dada por uma alinhamento m´ultiplo. Dado um alinhamento m´ultiplo de n colunas em
9
um alfabeto A, um perfil P ´e uma matriz |A| × n que especifica a freq¨uˆencia e
i
(a) de
cada s´ımbolo a de um alfabeto A em uma coluna i [28]. Mais adiante descreveremos o
conceito de alinhamento.
Na literatura temos alguns textos que abordam HMMs e pHMMs, permitindo uma me-
lhor compreens˜ao dos conceitos aqui descritos. Especificamente, citamos o trabalho de
Eddy [17], que descreve uma revis˜ao sobre pHMMs; Salzberg e outros [33] fazem uma
descri¸c˜ao n˜ao-matem´atica, no entanto mais did´atica, de HMMs, descrevendo-os atrav´es
de um exemplo e posteriormente descrevendo perfis HMMs; Pevzner [28] descreve HMMs
e pHMMs mais formalmente; Eddy [18] descreve em s´ıntese o que ´e um odelo oculto de
Markov; e um exemplo de HMM para encontrar promotores em uma seq¨uˆencia de DNA
procari´otico ´e descrito em Almeida [2].
2.3 Compara¸c˜ao de seq¨uˆencias
Compara¸c˜ao de seq¨uˆencias ´e a mais importante opera¸c˜ao em bioinform´atica, servindo
como base para muitas outras manipula¸c˜oes mais complexas.
Ao compararmos duas seq¨uˆencias, podemos determinar a similaridade e o alinhamento
entre elas. A similaridade de duas seq¨uˆencias ´e uma medida que indica o quanto as
seq¨uˆencias s˜ao semelhantes. O alinhamento de duas seq¨uˆencias ´e uma forma de posici-
onar uma seq¨uˆencia sobre a outra, acrescentando espa¸cos nas duas seq¨uˆencias, para que
ambas fiquem do mesmo tamanho, com o objetivo de evidenciar a correspondˆencia entre
s´ımbolos ou subseq¨uˆencias similares das seq¨uˆencias, ou seja, o alinhamento evidencia qu˜ao
similares duas seq¨uˆencias s˜ao.
Para computar a similaridade entre duas seq¨uˆencias, poder´ıamos gerar todos os poss´ıveis
alinhamentos e escolher o melhor, ou seja, o de maior valor. Entretanto, o n´umero de
alinhamentos entre duas seq¨uˆencias ´e exponencial. Uma solu¸c˜ao eficiente para o problema
´e fornecida pela t´ecnica de programa¸c˜ao dinˆamica.
A t´ecnica de programa¸c˜ao dinˆamica consiste basicamente em solucinar uma instˆancia do
problema tirando vantagem de solu¸c˜oes anteriormente computadas de instˆancias meno-
res do mesmo problema. Na pr´atica, a programa¸c˜ao dinˆamica soluciona todos os sub-
problemas somente uma vez, armazenando as solu¸c˜oes em uma tabela, para que sejam re-
cuperadas sem a necessidade de uma recomputa¸c˜ao. Uma excelente descri¸c˜ao da t´ecnica,
incluindo aplica¸c˜oes, pode ser encontradas no livro de Cormen [14]. Setubal e Meida-
nis [36] fazem uma descri¸c˜ao mais detalhada da compara¸c˜ao de duas seq¨uˆencias, incluindo
uma excelente descri¸c˜ao de algoritmos que utilizam a t´ecnica de programa¸c˜ao dinˆamica
para a compara¸c˜ao de seq¨uˆencias biol´ogicas.
Com o crescente volume de seq¨uˆencias sendo geradas pelos laborat´orios, bancos de dados
de seq¨uˆencias foram sendo criados. Esse evento criou uma necessidade por programas efi-
cientes para comparar as seq¨uˆencias nesses bancos de informa¸c˜oes biol´ogicas. Em essˆencia,
o problema consiste em listar quais trechos de uma seq¨uˆencia de prote´ına ou de DNA s˜ao
similares a quais regi˜oes de uma determinada seq¨uˆencia de prote´ına ou DNA fornecida
pelo usu´ario.
10
Devido a complexidade quadr´atica dos algoritmos baseados em programa¸c˜ao dinˆamica,
novos e r´apidos m´etodos tˆem sido des envolvidos, em especial heur´ısticas tˆem sido emprega-
das na pr´atica. Um dos programas baseado em heur´ısticas, mais freq¨uentemente utilizado
de busca de seq¨uˆencias similares em bases de dados, ´e o blast, que ser´a descrito a seguir.
2.4 BLAST
O blast, Basic Local Alignment Search Tool, foi inicialmente proposto por Altschul e
colegas [6], e desde ent˜ao vem sendo aperfei¸coado [7].
Dada uma seq¨uˆencia de entrada, denominada de seq¨uˆencia query, blast retorna uma lista
de poss´ıveis seq¨uˆencias similares, denominadas hits, e seus alinhamentos com a seq¨uˆencia
query. Cada hit ´e acompanhado de uma estimativa de significˆancia estat´ıstica, de-
nominada e-value. Em essˆencia, o e-value representa a quantidade de hits com uma
determinada pontua¸c˜ao que s˜ao esperados ao acaso. Dessa forma, quando menor ´e o
valor de e-value, menor ´e a probabilidade de um determinado hit ter sido encontrado
ao acaso. Os alinhamentos entre a seq¨uˆencia query e seus hits possuem um valor, de-
nominado de score. O valor de score considera o tamanho do banco de seq¨uˆencias e os
tamanhos das seq¨uˆencias.
A metodologia de blast para computar os hits ´e basicamente a seguinte. Primeiro,
blast encontra certas “sementes”, que s˜ao subcadeias curtas de tamanho W da seq¨uˆencia
query, cujo alinhamento com subcadeias de mesmo tamanho das seq¨uˆencias da base de
seq¨uˆencias, tenha valor maior ou igual a uma valor limite T , utilizando para isso alguma
matriz de substitui¸c˜ao de amino´acidos. As “sementes” da seq¨uˆencia query e da base de
seq¨uˆencias s˜ao ent˜ao estendidas em ambas as dire¸c˜oes, at´e o score m´aximo poss´ıvel, para
que a extens˜ao dessa “semente” em particular seja alcan¸cada. blast tem um crit´erio
de parar as extens˜oes quando o valor de score cair a um valor de limite inf erior X. Os
segmentos estendidos s˜ao utilizados na constru¸c˜ao do alinhamento.
Os valores de W , T e X s˜ao parˆametros de blast. Obviamente, todos os parˆametros de
blast influenciam diretamente no resultado da busca por seq¨uˆencias, fazendo com que a
complexidade do bla st seja dif´ıcil de c alcular, visto que todos os parˆametros tornam-se
fatores importantes na disputa entre sensibilidade e seletividade.
11
Cap´ıtulo 3
Compara¸c˜ao de dois genomas
Neste cap´ıtulo abordaremos a estrat´egia descrita em Almeida [1] para a compara¸c˜ao de
dois genomas, que nos permita determinar regi˜oes comuns em termos de genes conserva-
dos, determinar os genes espec´ıficos e as regi˜oes espec´ıficas entre os proteomas, determinar
os pares de genes ort´ologos e as regi˜oes ort´ologas, construir o alinhamento entre os pro-
teomas, e por fim comparar genomas n˜ao seq¨uenciados completamente. Objetivamos
desenvolver uma ferramenta que ajude a explicar como a reordena¸c˜ao e o reagrupamento
de genes influenciam nas diferen¸cas entre as funcionalidades de dois genomas.
Estamos interessados nos genes que codificam prote´ınas, presentes nas fitas de DNA de
uma esp´ecie, onde cada prote´ına possui uma posi¸c˜ao de acordo com a ordem em que o
seu respectivo gene aparece no genoma. Assim, t´ecnicas de compara¸c˜ao para as prote´ınas
preditas dos genomas s˜ao necess´arias.
Este cap´ıtulo est´a organizado da seguinte forma. Na Se¸c˜ao 3.1 descrevemos a metodo-
logia utilizada. Na Se¸c˜ao 3.2 descrevemos uma proposta de implementa¸c˜ao segundo a
metodologia descrita. Na Se¸c˜ao 3.3 descrevemos as novas funcionalidades acrescentadas `a
nova proposta de implementa¸c˜ao. Por fim, na Se¸c˜ao 3.4, descrevemos sucintamente uma
compara¸c˜ao com outras ferramentas.
3.1 Metodologia
Descreveremos nessa se¸c˜ao a metodologia utilizada por Almeida em [1] que possibilita
a compara¸c˜ao entre dois proteomas. Existem outras meto dologias [22, 23, 31, 32, 39]
que tamb´em permitem determinar regi˜oes de elementos conservados entre as esp´ecies
comparadas. Na Se¸c˜ao 3.4 desc reveremos algumas dessas outras metodologias.
Embora algumas defini¸c˜oes tenham sido descritas anteriormente, no Cap´ıtulo 2, descreve-
remos e refaremos outras defini¸c˜oes, para uma melhor interpreta¸c˜ao das pr´oximas se¸c˜oes.
• A fita de um gene ´e a fita de DNA a qual o gene pertence, sendo denominada de
fita ‘+’ ou ‘-’;
12
• A ordem dos genes de um proteoma ´e dada pela ordem n˜ao-decrescente das
coordenadas de in´ıcio dos genes. Seja P
i
a posi¸c˜ao da primeira base de um gene g
i
,
caso g
i
tenha sido codificado na fita ‘+’; ou a posi¸c˜ao da ´ultima base antes do c´odon
de termina¸c˜ao, caso g
i
tenha sido codificado na fita ‘-’. Ent˜ao a ordem dos genes,
g
1
, g
2
, . . . , g
n
, ´e determinada respeitando a rela¸c˜ao P
1
≤ P
2
≤ . . . ≤ P
n
;
Na Figura 3.1 temos duas representa¸c˜oes gr´aficas simplificadas do proteoma de um
genoma G. A primeira representa¸c˜ao ilustra os genes e suas orienta¸c˜oes: setas
para a esquerda representam genes pertencentes a fita ‘-’, enquanto que setas para
a direita representam genes pertencentes a fita ‘+’. A segunda representa¸c˜ao ´e
mais adequada para nosso prop´osito, pois considera a ordem dos genes baseada nas
orienta¸c˜oes descritas acima.
G
→
g
1
→
g
2
←−
g
3
→
g
4
←
g
5
−→
g
6
←−
g
7
→
g
8
−→
g
9
−→
g
10
←
g
11
G
① ① ① ① ① ① ① ① ① ① ①
g
1
g
2
g
3
g
4
g
5
g
6
g
7
g
8
g
9
g
10
g
11
Figura 3.1: Exemplo de representa¸c˜ao dos genes de um proteoma G.
• Dois genes g
i
e g
j
s˜ao hom´ologos se s˜ao descendentes de um mesmo gene ancestral;
• Dois genes g
i
e g
j
de um mesmo genoma G s˜ao par´alogos se s˜ao hom´ologos e essa
homologia originou-se atrav´es de um evento de duplica¸c˜ao;
• Uma regi˜ao de genes consecutivos (RGC) ´e um conjunto de genes consecutivos
em um proteoma, de acordo com suas coordenadas de in´ıcio, independente da fita.
Assim, temos que o pr´oprio proteoma ´e uma RGC;
• Dois genes g de G e h de H s˜ao ort´ologos se s˜ao hom´ologos em genomas diferentes
atrav´es de um evento de especia¸c˜ao o corrido antes de um evento de duplica¸c˜ao.
Dizemos que (g, h) ´e um par de ort´ologos;
• Um gene g de um proteoma G ´e espec´ıfico em rela¸c˜ao a um proteoma H se n˜ao
existir gene h no proteoma H tal que g e h s˜ao ort´ologos;
• Uma regi˜ao espec´ıfica (RE) de um proteoma G em rela¸c˜ao a um outro proteoma
H ´e uma regi˜ao de G, denotada por RE(G), tal que |RE(G)| ≥ E
, onde E
´e um
limite fixo;
• Uma regi˜ao ort´ologa (RO) de dois proteomas G e H ´e um par (α, β) tal que:
– α ´e uma RGC em G;
– β ´e uma RGC em H;
– α e β s˜ao descendentes de uma mesma regi˜ao ancestral; e
13
– α e β contˆem aproximadamente o mesmo n´umero de genes.
Uma descri¸c˜ao mais formal e detalhada de regi˜ao ort´ologa ser´a apresentada na
Se¸c˜ao 3.1.3.
• Dois pares de genes ort´ologos (g, h) e (g
, h
) formam um cruzamento quando a
ordem de g e g
no proteoma G e a ordem de h e h
no proteoma H s˜ao invertidas;
e
• A espinha dorsal de duas RGCs, α de G e β de H, ´e uma seq¨uˆencia de pares
de ort´ologos (g, h), tal que:
– cada gene em α tem no m´aximo um gene ort´ologo a ele em β, e vice-versa; e
– n˜ao existem cruzamentos entre os pares da seq¨uˆencia.
As figuras abaixo ilustram, respectivamente, um exemplo de RO e de uma espinha dorsal
de duas RGCs.
g
i
g
i+1
g
i+2
g
i+3
g
i+4
g
i+5
h
j
h
j+1
h
j+2
h
j+3
h
j+4
Figura 3.2: Representa¸c˜ao de uma regi˜ao ort´ologa.
g
i
g
i+1
g
i+2
g
i+3
g
i+4
g
i+5
h
j
h
j+1
h
j+2
h
j+3
h
j+4
Figura 3.3: Representa¸c˜ao de uma espinha dorsal de duas Regi˜oes de Genes Consecutivos
- RGCs.
Antes de apresentarmos a metodologia descrita por Almeida em [1], citaremos os objetivos
que desejamos alcan¸car na compara¸c˜ao de dois proteomas:
1. Encontrar genes espec´ıficos entre proteomas;
2. Encontrar regi˜oes espec´ıficas entre proteomas;
3. Encontrar pares de genes ort´ologos;
14
4. Encontrar regi˜oes ort´ologas;
5. Determinar a espinha dorsal entre proteomas; e
6. Determinar fam´ılias de genes par´alogos de um proteoma.
Apresentaremos separadamente o item de n´umero 6 no Cap´ıtulo 4. Nas se¸c˜oes se guintes,
descreveremos os passos para alcan¸carmos os outros objetivos listados acima.
3.1.1 Genes Espec´ıficos e Ort´ologos
Para apresentarmos os passos para encontrar os genes espec´ıficos e os genes ort´ologos,
necessitamos das seguintes defini¸c˜oes:
• Sejam g e h genes dos proteomas G e H respectivamente;
• Seja s(g, h) uma medida de significˆancia estat´ıstica de similaridade de g e h, de tal
modo que, quanto menor s(g, h), mais similares g e h s˜ao. Sua implementa¸c˜ao ser´a
descrita na Se¸c˜ao 3.2; e
• Seja A um alinhamento entre as seq¨uˆencias representantes dos genes g e h. Sejam
I
g
, J
g
, I
h
, J
h
posi¸c˜oes de g e h como definidas abaixo:
– I
g
e J
g
s˜ao o primeiro e o ´ultimo s´ımbolos de g que aparecem em A, respecti-
vamente; e
– I
h
e J
h
s˜ao o primeiro e o ´ultimo s´ımbolos de h que aparecem em A, respecti-
vamente.
A cobertura do alinhamento A em g , denotada por c(A, g), ´e dada pelo percentual
de |g| que aparece em A. Assim,
c(A, g) =
J
g
− I
g
+ 1
|g|
× 100
A mesma defini¸c˜ao vale para c(A, h), ou seja,
c(A, h) =
J
h
− I
h
+ 1
|h|
× 100
Segundo as defini¸c˜oes acima, utilizamos o seguinte crit´erio para a determina¸c˜ao dos genes
ort´ologos:
• Um gene h ´e ort´ologo a um gene g e vice-versa se, e somente se :
– s(g, h) ≤ S, onde S ´e um limite fixo; e
– o alinhamento A entre g e h ´e tal que c(A, g) ≥ P e c(A, h) ≥ P , onde P ´e um
limite fixo.
15
Quando os genes g e h s˜ao ort´ologos e h ´e o gene de H que possui menor medida de
significˆancia estat´ıstica de similaridade com g, para qualquer gene h
de H ort´ologo
a g e vice-versa, definimos g e h como genes fortemente ort´ologos. Utilizaremos
essa defini¸c˜ao de genes fortemente ort´ologos objetivando o alinhamento entre os
proteomas.
• Um gene g de G ´e espec´ıfico em rela¸c˜ao ao proteoma H se, e somente se, a medida
de significˆancia s(g, h) ´e tal que s(g, h) > S
para qualquer gene h de H e S
≥ S,
onde S
´e um limite fixo.
Conforme os crit´erios citados acima, necessitamos de um algoritmo que compare dois
genes, fornecendo a similaridade e a significˆancia estat´ıstica entre eles. Na Se¸c˜ao 3.2,
descreveremos como essa compara¸c˜ao e como esses valores ser˜ao obtidos.
3.1.2 Regi˜oes espec´ıficas (REs)
O problema de determinar REs pode ser modelado para o problema computacional co-
nhecido como subcadeia de m´axima soma, definido na Se¸c˜ao 2.2.
Na literatura, especificamente em an´alise de prote´ınas, encontramos algumas aplica¸c˜oes
para esse problema, como a identifica¸c˜ao de regi˜oes de transmembranas e dom´ınios de
liga¸c˜ao, ambos citados em Ruzzo e Tompa [30].
Conforme defini¸c˜ao do problema no Cap´ıtulo 2, utilizamos a mesma estrat´egia de Almeida,
que consiste em atribuir valores aos genes do proteoma, onde um valor δ ´e atribu´ıdo para
os genes n˜ao espec´ıficos e um valor ∆ para os genes espec´ıficos, tal que ∆ > δ. Assim, a
seq¨uˆencia de entrada para o problema ´e constitu´ıda pelos valores atribu´ıdos aos genes.
Dessa forma, um algoritmo para encontrar todas as subcadeias maximais ´e suficiente para
a implementa¸c˜ao dessa estrat´egia. Na Se¸c˜ao 3.2 utilizaremos uma vers˜ao modificada do
algoritmos de Ruzzo e Tompa [30], que foi descrita por C´aceres e colegas [8], e que resolve
eficientemente esse problema.
3.1.3 Regi˜oes Ort´ologas (ROs)
Para descrevermos os m´etodos necess´arios para determina¸c˜ao das regi˜oes ort´ologas, as
seguintes defini¸c˜oes s˜ao necess´arias:
Defini¸c˜ao 3.1 (Run) Sejam dois genomas G e H. Seja α uma RGC de G formada pelos
genes g
i
, . . . , g
k
e β uma RGC de H formada pelos genes h
j
, . . . , h
l
, tais que k − i + 1 =
l − j + 1, k > i e l > j. Dizemos que α e β formam um run se quaisquer das seguintes
seq¨uˆencias de pares de genes ort´ologos ocorrerem:
1. (g
i
, h
j
), (g
i+1
, h
j+1
), . . . , (g
k
, h
l
); ou
2. (g
i
, h
l
), (g
i+1
, h
l−1
), . . . , (g
k
, h
j
).
16
Um run ´e classificado como paralelo ou anti-paralelo. Classificamos um run como para-
lelo quando a seq¨uˆencia de pares ort´ologos corresponder a op¸c˜ao n´umero 1 acima. Quando
a seq¨uˆencia de pares de ort´ologos corresponder a op¸c˜ao n´umero 2 acima, classificamos o
run como anti-paralelo.
Os runs s˜ao classificados tamb´em como consistentes ou inconsistentes. Um run ´e classi-
ficado como consistente se, quando for paralelo, todos os pares de genes s˜ao tais que os
genes participantes de cada par pertencem `a mesma fita; e no caso de ser anti-paralelo,
os genes de cada par pertencem a fitas opostas. Caso contr´ario, o run ´e classificado como
inconsistente.
Assim, podemos redefinir o conceito de RO, descrito na Se¸c˜ao 3.1, detalhando as suas
caracter´ısticas.
Defini¸c˜ao 3.2 (Regi˜ao Ort´ologa) Definimos uma regi˜ao ort´ologa R como:
1. um run isolado com pelo menos M pares de ort´ologos, onde M ´e um valor fixo; ou
2. a uni˜ao de runs, cada um com um total de pelo menos M pares de ort´ologos, e cuja
distˆancia entre os genes extremos
1
de runs consecutivos n˜ao seja maior que um
determinado valor fixo k, em n´umero de genes; ou
3. um BBH. Definiremos o conceito de BBH na Se¸c˜ao 3.2.1.
A estrat´egia para determinar ROs consiste em percorrer todos os runs, da esquerda para
a direita (conforme a ordem dos genes de um dos proteomas), e juntar aqueles runs que
s˜ao pr´oximos, segundo o crit´erio 2 acima definido.
Desta forma, a estrat´egia utilizada para a determina¸c˜ao das ROs est´a fundamentada na
jun¸c˜ao de runs pr´oximos e na determina¸c˜ao de valores adequados para M e k.
Os testes realizados por Almeida em [1] sugerem que o valor M = 3, para genomas de
procariotos, ´e suficiente para garantir que um run n˜ao seja encontrado ao acaso.
A implementa¸c˜ao da estrat´egia para determinar as ROs ser´a descrita detalhadamente na
Se¸c˜ao 3.2.
3.1.4 Espinha dorsal dos proteomas
A estrat´egia aplicada para a determina¸c˜ao da espinha dorsal entre dois proteomas con-
siste no alinhamento global entre eles. O alinhamento entre os proteomas ´e baseado no
problema computacional denominado subseq¨uˆencia comum mais longa [14].
Particularmente, cada s´ımbolo do alinhamento corresp onde ao n´umero seq¨uencial do gene
no proteoma, e dois s´ımbolos das cadeias s ˜ao iguais se, e somente se, os respec tivos genes
compartilham uma determinada rela¸c˜ao.
Para minimizar a interferˆencia de genes par´alogos, a rela¸c˜ao exigida para que dois genes
(g, h) sejam candidatos a se alinharem, ´e que g e h devem ser genes fortemente ort´ologos.
1
Os genes extremos dos runs s˜ao aqueles genes que encontram-se mais pr´oximos de um outro run.
17
Dessa forma, objetivamos obter o alinhamento com maior n´umero de pares de genes
ort´ologos, sem que existam cruzamentos, o que caracteriza um alinhamento.
Podemos observar, nesse caso, a diferen¸ca entre a estrat´egia acima definida, e a estrat´egia
utilizada para a determina¸c˜ao de runs. No caso da espinha dorsal, aplicamos o conceito de
ortologia forte para minimizarmos a a¸c˜ao dos genes par´alogos. Para a determina¸c˜ao dos
runs, n˜ao podemos aplicar a mesma estrat´egia, pois um determinado gene pode participar
de mais de um par de ort´ologos, podendo participar de mais de uma regi˜ao ort´ologa, devido
as duplica¸c˜oes internas que po dem ocorrer no genoma [34].
A se¸c˜ao seguinte cont´em as implementa¸c˜oes e descri¸c˜oes da mais detalhadas da utiliza¸c˜ao
dessa metodologia para determina¸c˜ao da espinha dorsal, que procura evidenciar a proxi-
midade dos proteomas.
3.2 Nova implementa¸c˜ao
Nesta se¸c˜ao abordaremos uma nova proposta de implementa¸c˜ao para a metodologia de
Almeida, descrita anteriormente. Inicialmente, a primeira implementa¸c˜ao da metodologia
resultou no programa de computador denominado de Extended Genome-Genome compar-
sion (egg). egg foi inicialmente formulado por Almeida e Setubal em [3], posteriormente
reformulado em [4] e em [1].
Posteriormente `a ´ultima reformula¸c˜ao, existiu a necessidade de uma reestrutura¸c˜ao do
programa, que atendesse `as corre¸c˜oes de pequenas falhas, a melhoria da portabilidade e de-
sempenho, al´em da inclus˜ao de novas funcionalidades e disponibiliza¸c˜ao para os usu´arios.
Conforme essas necess idades, descreveremos nesse cap´ıtulo a terceira reformula¸c˜ao de
egg.
Segundo Almeida [1], o objetivo principal de egg ´e a compara¸c˜ao de dois proteomas. Pri-
meiramente, ´e realizada uma compara¸c˜ao das prote´ınas preditas, na forma todas-contra-
todas, utilizando o blast. Posterior a essa compara¸c˜ao, um grafo bipartido ´e constru´ıdo,
onde o conjunto de v´ertices ´e constitu´ıdo pelos genes particionados pelos genomas e o con-
junto de arestas ´e constitu´ıdo pelas ortologias entre os genes. Por fim, algumas es truturas
organizacionais s˜ao constru´ıdas para alcan¸car os objetivos listados na Se¸c ˜ao 3.1.
Assim como a metodologia, esta nova reimplementa¸c˜ao tamb´em ´e baseada na reformula¸c˜ao
apresentada por Almeida em [1].
3.2.1 Descri¸c˜ao das fases de egg
Podemos distinguir em egg trˆes fases importantes:
• Compara¸c˜ao dos genes todos-contra-todos;
• Constru¸c˜ao do grafo bipartido; e
• Determina¸c˜ao das estruturas organizacionais.
18
Nas se¸c˜oes subse q¨uentes, descreveremos cada uma das 3 fases de egg e detalhes de suas
implementa¸c˜oes.
Compara¸c˜ao dos genes todos-contra-todos
Nessa fase, temos a compara¸c˜ao de cada gene g
i
de um genoma G contra todos os genes
do genoma H e, em seguida, cada gene h
j
de H ´e comparado contra todos os genes de
G. O objetivo consiste em relacionar os genes com a finalidade de determinar os genes
ort´ologos e genes espec´ıficos.
Para realizar esse procedimento, egg utiliza como ferramenta comparativa o programa
blast [6, 7]. Esse programa fornece para cada gene g
i
, uma lista de genes h
j
similares a
g
i
, dentre todos os genes de H e algumas informa¸c˜oes sobre os alinhamentos entre esses
genes. Cada gene similar h
j
retornado por blast´e denominado de hit.
Para implementar o valor de similaridade descrito na Se¸c˜ao 3.1.1, usamos a medida de
significˆancia estat´ıstica do blast, denominada e-value. Conforme descrito no Cap´ıtulo 2,
essa medida ´e proporcional `a probabilidade de um determinado hit ter sido encontrado
ao acaso. Assim, quanto menor ´e o valor de e-value, menor ´e a probabilidade de um hit
ter sido encontrado ao acaso, ou seja, mais significante ´e o hit.
Para armazenarmos os hits obtidos pelo blast, utilizamos a estrutura de dados lista
ligada, que armazenar´a para c ada gene g
i
de G uma lista de todos os seus hits h
j
de H,
ordenados de forma n˜ao-decrescente pelo valor de e-value. Esta forma de armazenamento
permite obter o melhor hit de um gene g
i
em tempo constante.
Ao final dessa fase, egg consegue determinar os genes espec´ıficos entre os proteomas,
objetivo 1 listado na Se¸c˜ao 3.1. Especificamente, egg considera que um gene g
i
´e espec´ıfico
em rela¸c˜ao a H, se g
i
n˜ao obteve hits com e-value menor ou igual a S
= 10
−3
. Na se¸c˜ao
seguinte descreveremos o crit´erio para encontrarmos os genes ort´ologos.
Determina¸c˜ao das arestas do grafo
Na ´ultima reformula¸c˜ao, egg criou um grafo bipartido determinando as ortologias entre
os genes dos genomas. Essas ortologias s˜ao estabelecidas atrav´es da especifica¸c˜ao do
relacionamento, denominado match, e ntre os genes. egg utiliza os matches como arestas
do grafo bipartido. Utilizaremos o termo match no lugar de “par de genes ort´ologos” no
decorrer do texto.
Um match entre os genes g
i
de G e h
j
de H ocorre quando g
i
encontrar h
j
como hit,
com os seguintes valores limites: S = 10
−5
, P = 60 e vice-versa. Esses valores foram
utilizados por Almeida em [1]. Tamames [39] utilizou os valores 10
−5
e 75 para S e P
respectivamente. Assim como em Almeida, os valores de S e P podem ser alterados pelo
usu´ario.
Pela determina¸c˜ao dos matches, egg atinge o objetivo 3, que ´e determinar pares de
genes ort´ologos. Assim, podemos reescrever os seguintes crit´erios para obtermos os genes
ort´ologos e os genes espec´ıficos:
19
• Dados dois genes g e h pertencentes, respectivamente, aos genomas G e H, e os
alinhamentos A e A
retornado pelo blast, tais que A ´e o alinhamento de g para h
e A
´e o alinhamento de h para g. Dizemos que g e h s˜ao ort´ologos se, e somente se
(s(g, h)+s(h, g))/2 ≤ 10
−5
e (c(A, g)+c(A
, g))/2 ≥ 60 e (c(A, h)+c(A
, h))/2 ≥ 60.
• Um gene g ´e espec´ıfico em rela¸c˜ao a um genoma H se, e somente se, s(g, h
j
) > 10
−3
,
para 1 ≤ j ≤ |H|.
Conforme os crit´erios acima definidos, consideramos que os e-values menores ou iguais a
10
−5
indicam homologia com alta probabilidade. Dessa forma, dois genes s˜ao considerados
ort´ologos se eles forem hom´ologos com alta probabilidade e se a cobertura do alinhamento
entre eles for maior ou igual a P = 60. Por outro lado, os genes que n˜ao possu´ırem hits
com e-values menores ou iguais a 10
−3
s˜ao denominados como genes espec´ıficos. Por
esses crit´erios, consideramos a regi˜ao compreendida entre 10
−3
e 10
−5
como uma regi˜ao
de d´uvida, da terminologia em inglˆes “twilight zone”.
A implementa¸c˜ao do conceito de “pares de genes fortemente ort´ologos” ´e realizada atrav´es
da utiliza¸c˜ao do melhor hit bidirecional, da tradu¸c˜ao do termo em inglˆes, Bidirectional
Best Hit (BBH). O termo BBH foi empregado em [1, 4, 35, 39] tamb´em para determinar
os pares de genes ort´ologos. Um par de genes ort´ologos (g
i
, h
j
) formam um BBH, se h
j
´e
o melhor hit encontrado por g
i
, ou seja, com menor e-value, e vice-versa [1].
Armazenamos os matches entre os genes g
i
de G e h
j
de H na mesma estrutura que
implementa um hit h
j
de um gene g
i
, sinalizando quando (g
i
, h
j
) formar um match. Como
os hits de um gene g
i
est˜ao armazenadas na lista ligada de hits, com o melhor hit de g
i
na
primeira posi¸c ˜ao da lista, em tempo constante, obtemos o melhor hit de um determinado
gene g
i
. Dessa forma, obtemos todos os BBHs de dois proteomas em tempo linear no
n´umero de genes de G e H.
Determina¸c˜ao das estruturas organizacionais.
Nessa fase desc reveremos as regi˜oes espec´ıficas, os runs, as regi˜oes ort´ologas e a espinha
dorsal entre dois proteomas.
Regi˜oes espec´ıficas
A implementa¸c˜ao das regi˜oes espec´ıficas ´e realizada conforme a estrat´egia descrita na
Se¸c˜ao 3.1.2. Definimos que o valor δ = −1 ´e atribu´ıdo para os genes n˜ao espec´ıficos e ∆ = 1
para os genes espec´ıficos, atendendo a restri¸c˜ao ∆ > δ. Dessa forma, faz-se necess´aria a
implementa¸c˜ao de um algoritmo que encontre to das as subseq¨uˆencias cont´ıguas de soma
m´axima, de uma seq¨uˆencia de entrada A composta pelos valores 1 e −1.
Segundo Ruzzo e Tompa [30], as caracter´ısticas do problema de determinar todas as
subseq¨uˆencias de soma m´axima de uma seq¨uˆencia X sugerem um algoritmo simples de
divis˜ao e conquista com os seguintes passos:
1. Encontre a subseq¨uˆencia m´axima de maior soma e remova-a da seq¨uˆencia X;
20
2. Aplique o algoritmo recursivamente, para as partes restantes `a esquerda e `a direita
da por¸c˜ao removida.
No entanto, a an´alise desse algoritmo ´e similar a an´alise do algoritmo de ordena¸c˜ao Quick-
Sort, que no pior caso, necessitar´a de tempo quadr´atico para encontrar a solu¸c˜ao do
problema [14].
No mesmo trabalho [30], Ruzzo e Tompa descrevem um algoritmo para encontrar todas
as subseq¨uˆencias de m´axima soma em temp o linear. Segundo os pr´oprios autores, o algo-
ritmo, conforme descrito, n˜ao executa em tempo linear, sendo necess´aria uma altera¸c˜ao
em uma poss´ıvel fase de implementa¸c˜ao, para que o tempo total de execu¸c˜ao do algoritmo,
utilizando a an´alise amortizada, torne-se linear.
Inicialmente, implementamos a vers˜ao de divis˜ao e conquista conforme descrita em [30].
Devido aos testes de compara¸c˜ao de tempo, entre os algoritmos da vers˜ao de divis˜ao e
conquista e de tempo linear, realizados por Ruzzo e Tompa em [30]; e pela diferen¸ca
entre suas complexidades, decidimos implementar o algoritmo descrito por Alves e cole-
gas [8], que ´e uma vers˜ao modificada do algoritmo de Ruzzo e Tompa, que tamb´em possui
complexidade O(n) amortizada.
Embora os algoritmos de [30] e [8] possuam complexidades similares, o algoritmo apre-
sentado por Alves [8] est´a descrito de forma mais expl´ıcita, fazendo utiliza¸c˜ao de vetores
com a finalidade de facilitar a an´alise e compreens˜ao; e tamb´em mantendo a mesma
complexidade da vers˜ao do algoritmo de Ruzzo e Tompa. Neste algoritmo, a entrada ´e
uma seq¨uˆencia A e a sa´ıda s˜ao dois vetores denominados Mlista(A) (Ml(A)) e P lista(A)
(P l(A)), que armazenam, respectivamente, as informa¸c˜oes sobre as subseq¨uˆencias maxi-
mais e o seu ´ındice de ocorrˆencia na seq¨uˆencia A. Intuitivamente, o algoritmo mant´em o
vetor Ml(A) com as informa¸c˜oes de cada subseq¨uˆencia de m´axima pontua¸c˜ao e um vetor
de ´ındices de subseq¨uˆencias candidatas de m´axima soma prefixa, onde pretende-se esten-
der alguma subseq¨uˆencia candidata para que transforme-se em uma subseq¨uˆencia maior
e de m´axima soma. O algoritmo descrito por Alves e colegas utiliza os vetores P l(A) e
Ml(A) como a estrutura de dados de pilhas. Descrevemos em seguida, de forma sucinta,
o algoritmo Subseq
¨
u
ˆ
encias-Maximais de Alves e colegas.
21
Algoritmo 1 Subseq
¨
u
ˆ
encias-Maximais
Entrada: Seq¨uˆencia A = (a
1
, a
2
, . . . , a
|A|
)
Sa´ıda: Ml(A) e P l(A) com n
m
e n
p
elementos. s mant´em a soma de cada subseq¨uˆencia.
1: n
m
← 0, n
p
← 0, s ← 0
2: para i ← 1 at´e |A| fa¸ca
3: s ← s + a
i
4: se a
i
negativo ent˜ao
5: enquanto tiver subseq¨uˆencia candidata e ela n˜ao contribuir para a soma da
subseq¨uˆencia atual fa¸ca
6: n
p
← n
p
− 1 {Desempilha subseq¨uˆencia candidata}
7: fim enquanto
8: fim se
9: se a
i
positivo ent˜ao
10: {Empilha a nova seq¨uˆencia formada por a
i
}
11: n
m
← n
m
+ 1
12: {Obt´em informa¸c˜oes da nova seq¨uˆencia}
13: {Armazena ´ındice n
m
no vetor P l(A)}
14: enquanto tiver subseq¨uˆencia candidata e ela n˜ao contribuir para a extens˜ao at´e
a
i
fa¸ca
15: n
p
← n
p
− 1{Desempilha subseq¨uˆencia candidata}
16: fim enquanto
17: n
p
← n
p
+ 1
18: {P l[n
p
] aponta para a melhor subseq¨uˆencia candidata}
19: n
m
← P l[n
p
]
20: {Completa as informa¸c˜oes da melhor subseq¨uˆencia}
21: fim se
22: fim para
Todo comando presente no la¸co na linha 2 executa em tempo constante, exceto os la¸cos
das linhas 5 e 14. Nesse caso, com a an´alise amortizada no n´umero de elementos da
pilha P l(A), observamos que os la¸cos n˜ao ir˜ao procurar por todas as subseq¨uˆencias de A,
mas apenas pelas candidatas de m´axima soma. Por meio da an´alise amortizada temos
que o custo do algoritmo ´e O(n) amortizado. As provas da complexidade amortizada do
algoritmo, assim como maiores detalhes da implementa¸c˜ao da vers˜ao de Alves e colegas
est˜ao descritos em [8].
Em nosso trabalho particularmente, a entrada do algoritmo ´e o vetor A constitu´ıdo p e los
valores conforme definidos anteriormente. Por´em, a sa´ıda do algoritmo s˜ao as subcadeias
A
i
de m´axima soma, do vetor de entrada A, tal que |A
i
| ≥ w. Nesse trabalho utilizamos
o valor w = 10, que pode ser alterado pelo usu´ario.
Como sa´ıda de egg, temos um arquivo texto onde as REs encontradas s˜ao apresentadas.
Na Figura 3.4 temos uma RE de Xanthomonas axonopodis pv. citri str. 306 (Xac) em
rela¸c˜ao ao proteoma de Xanthomonas campestris pv. campestris str. ATCC 33913 (Xcc).
Maiores detalhes sobre o arquivo podem ser vistos em no Apˆendice A.
22
>Region from 4061 to 4091
31 orfs
=====================================================================
Gene Synonym start..end product
=====================================================================
# -_ XAC4118 4833465..4833995 hypothetical protein
# -_ XAC4119 4833998..4837528 hypothetical protein
# -_ XAC4120 4837525..4838880 hypothetical protein
# -_ XAC4121 4838787..4840121 hypothetical protein
# -_ XAC4122 4840701..4842017 hypothetical protein
# -_ XAC4123 4842304..4842852 hypothetical protein
# -_ XAC4124 4842849..4844885 hypothetical protein
-_ XAC4125 4844967..4846298 hypothetical protein
# -_ XAC4126 4846534..4846929 hypothetical protein
# -pknB XAC4127 4846892..4849189 serine threonine kinase
# -ecfR XAC4128 4849390..4849929 extracytoplasmic sigma factor
+rpoE XAC4129 4850278..4850805 ECF sigma factor
+_ XAC4130 4850802..4851872 transmembrane_sensor
+_ XAC4131 4852271..4855222 hypothetical protein
+appA XAC4132 4855361..4856611 6 phytase
# +_ XAC4133 4856619..4857986 hypothetical protein
# +_ XAC4134 4858039..4858398 hypothetical protein
# -_ XAC4135 4858635..4859336 hypothetical protein
# -_ XAC4136 4859777..4861771 hypothetical protein
+_ XAC4137 4862893..4864107 ISxac1 transposase
+_ XAC4138 4864112..4864522 transposase
# -_ XAC4139 4864528..4865544 hypothetical protein
-clpB XAC4140 4865531..4868311 ClpB
# -_ XAC4141 4868367..4869407 hypothetical protein
# -_ XAC4142 4869371..4871254 hypothetical protein
# -_ XAC4143 4871259..4871762 hypothetical protein
# -_ XAC4144 4871768..4872607 hypothetical protein
# -_ XAC4145 4872761..4873264 hypothetical protein
# -_ XAC4146 4873345..4874838 hypothetical protein
# -_ XAC4147 4874842..4875351 hypothetical protein
# +feaR XAC4148 4875665..4876336 transcriptional regulator
Figura 3.4: Exemplo de regi˜ao espec´ıfica de Xanthomonas axonopodis pv. citri str. 306
em rela¸c˜ao a Xanthomonas campestris pv. campestris str. ATCC 33913. O s´ımbolo #
indica os genes que pertencem a regi˜ao espec´ıfica.
Runs
Conforme descrito na metodologia, para obter as regi˜oes ort´ologas, devemos determinar
previamente os runs. A implementa¸c˜ao dos runs ´e realizada utilizando os matches, con-
forme descrito na Se¸c˜ao 3.2.1. Segundo a Defini¸c˜ao 3.1, temos que um run ´e uma seq¨uˆencia
de pelo menos dois matches. Dessa forma, determinamos os runs primeiramente armaze-
nando os matches em uma matriz bin´aria A
mn
, onde m ´e o n´umero de genes do genoma
G e n o n´umero de genes do genoma H, tal que A
i,j
= 1 se, e somente se, os genes g
i
de G
e h
j
de H formam um match. Em seguida, percorremos a matriz A procurando por pelo
menos duas posi¸c˜oes consecutivas em qualquer diagonal, onde as p osi¸c˜oes est˜ao preenchi-
das com 1. Em seguida descrevemos, em pseudo-c´odigo, o algoritmo Constr
´
oi-Run que
determina os runs.
23
Algoritmo 2 Constr
´
oi-Run
Entrada: Uma matriz bin´aria A
mn
.
Sa´ıda: Uma lista de runs
1: para i ← m at´e 1 fa¸ca
2: para j ← n at´e 1 fa¸ca
3: {Obt´em as coordenadas finais do run.}
4: k ← i
5: l ← j
6: enquanto A[k][l] = 0 fa¸ca
7: {Obt´em informa¸c˜oes sobre consistˆencia.}
8: k ← k − 1
9: l ← l − 1
10: fim enquanto
11: {Obt´em as coordenadas iniciais e o c´odigo do run.}
12: fim para
13: fim para
Conforme a defini¸c˜ao de run na Se¸c˜ao 3.1, temos que os runs podem ser anti-paralelos.
Nesse caso, o algoritmo ´e an´alogo ao acima apresentado, com altera¸c˜oes no ´ındice da
linha 2 e nas linhas 8 e 9. O custo do algoritmo descrito acima, no melhor caso, ´e O(mn),
que ocorre quando todos os elementos da matriz forem 0s. Por outro lado, o custo de pior
caso ´e O(mn)
2
e ocorre quando todos os elementos da matriz forem 1s.
O programa egg apresenta em um arquivo texto os runs encontrados, onde cada run ´e
identificado por um c´odigo. O c´odigo de um run ´e composto pelas seguintes informa¸c˜oes:
os seis primeiros s´ımbolos identificam os pares de genomas comparados; os 8 d´ıgitos se-
guintes identificam o ano, o mˆes e o dia; o n´umero seguinte ´e um n´umero seq¨uencial
do run na compara¸c˜ao proteˆomica; e os caracteres finais indicam se o run ´e paralelo ou
anti-paralelo e se ´e consistente ou anti-consistente.
Nas Figuras 3.5 e 3.6 temos, respectivamente, um trecho do arquivo resultante da com-
para¸c˜ao entre Xanthomonas axonopodis pv. citri str. 306 e Xanthomonas campestris pv.
campestris str. ATCC 33913 ; e uma representa¸c˜ao gr´afica desse run. Maiores detalhes
sobre o arquivo texto est˜ao apresentados no Apˆendice A.
24
>XACXCC20060329-245-Pc
# of matches: 5
6kb in XAC - 6kb in XCC
===============================================================================================
Gene |Synonym start size e-value [ best hit ] product
===============================================================================================
-_ |XAC0925 1087413 139 3e-43 [best ] hypothetical protein
-_ |XCC0848 1007675 139 4e-63 [best ] hypothetical protein
------------------------------------------
+_ |XAC0926 1088018 184 1e-103 [best ] hypothetical protein
+_ |XCC0849 1008268 184 1e-103 [best ] hypothetical protein
------------------------------------------
+ilvE |XAC0927 1088637 361 0 [best ] branched chain amino acid aminotransferase
+ilvE |XCC0850 1008887 361 0 [best ] branched chain amino acid aminotransferase
------------------------------------------
+_ |XAC0928 1090032 575 0 [best ] extracellular protease
+_ |XCC0851 1010286 580 0 [best ] extracellular protease
------------------------------------------
+_ |XAC0929 1091789 546 1e-162 [+_ |XCC0 851 /1e-174] extracellular protease
+_ |XCC0852 1012120 518 1e-169 [best ] extracellular protease
------------------------------------------
Figura 3.5: Exemplo de um run paralelo consistente entre Xanthomonas axonopodis pv.
citri str. 306 e Xanthomonas campestris pv. campestris str. ATCC 33913.
XCC0848
XAC0925 XAC0929
XCC0852
XAC
XCC
Figura 3.6: Representa¸c˜ao gr´afica do run do trecho de arquivo da Figura 3.5
Na figura acima, as setas para a esquerda representam os genes pertencentes a fita ’-’,
enquanto que as setas para a direita representam os genes pertencentes a fita ’+’. As
linhas de cor azul conectam os genes que fizeram BBH, enquanto que a linha de cor
vermelha conecta os genes que fizeram match.
Regi˜oes ort´ologas
Segundo a Defini¸c˜ao 3.1.3, uma regi˜ao ort´ologa ´e composta por M pares de ort´ologos ou
pela uni˜ao de runs com pelo menos M pares de ort´ologos que distam, a partir dos seus
genes extremos, no m´aximo um determinado valor fixo k.
Como a metodologia est´a baseada na uni˜ao de runs pr´oximos, devemos implementar a
no¸c˜ao de distˆancia entre os genes extremos dos runs. Descreveremos abaixo uma im-
plementa¸c˜ao, conforme Almeida [1], para determinarmos a proximidade adequada para
juntar os runs.
Sejam R
1
e R
2
dois runs entre os genomas G e H. Sem perda de generalidade, segundo
a defini¸c˜ao de run da Se¸c˜ao
3.1, representamos R
1
e R
2
como:
R
1
= (g
i
, h
j
), (g
i+1
, h
j+1
), . . . , (g
k
, h
l
) e R
2
= (g
p
, h
q
), (g
p+1
, h
q+1
), . . . (g
r
, h
s
)
25
Sejam tamb´em I
G
e I
H
os n ´umeros de genes entre os runs nos proteomas G e H, respec-
tivamente, tal que I
G
= p − k − 1 e I
H
= q − l − 1; I
min
e I
max
os intervalos m´ınimos
e m´aximos entre os runs; max small gaps e max large gaps os valores dos tamanhos
m´aximos, do menor e do maior intervalo entre os runs, fornecidos pelos usu´ario.
Como queremos juntar os runs pr´oximos formando uma s´o regi˜ao que evidencie um bloco
de genes com certo grau de ortologia [1], juntaremos os runs conforme a seguinte regra
de distˆancia:
I
min
≤ max small gap e I
max
≤ max large gap
Na figura 3.7, temos uma representa¸c˜ao gr´afica de uma jun¸c˜ao entre dois runs R
1
e
R
2
, seguindo as restri¸c˜oes da regra de distˆancia descrita acima. Nesse caso, definimos
max small gap = 5 e max large gap = 2.
g
i
g
i+1
g
k
h
j
h
j+1
h
l
R
1
R
2
h
q+1
h
q+2
h
s
g
p
g
p+1
g
r
I
min
h
q
I
max
Figura 3.7: Exemplo de uma jun¸c˜ao entre dois runs R
1
e R
2
.
Denominamos os runs que obedecem a rela¸c˜ao de distˆancia, de runs pr´oximos, e o
procedimento de uni˜ao dos runs de jun¸c˜ao.
Utilizamos o algoritmo incremental de Almeida [1] para determinar as ROs entre dois
proteomas. Abaixo temos uma des cri¸c˜ao de um pseudo-c´odigo para esse algoritmo.
Algoritmo 3 Junta-Runs
Entrada: LR : uma lista de runs
Sa´ıda: LRO : uma lista de ROs
1: LRO ← ∅
2: para i ← 1 at´e |LR| fa¸ca
3: para j ← i + 1 at´e |LR| fa¸ca
4: {Obt´em I
min
e I
max
}
5: se I
min
≤ max small gaps e I
max
≤ max large gaps ent˜ao
6: {junta os runs i e j}
7: fim se
8: fim para
9: fim para
26
O algoritmo, de forma increme ntal, realiza a jun¸c˜ao dos runs do in´ıcio para o final dos
proteomas, ou seja, uma regi˜ao ort´ologa resultante da uni˜ao de runs pr´oximos poder´a ser
unida com o pr´oximo run `a direita. A complexidade de tempo do algoritmo, no pior caso
´e O(|LR|
2
), onde |LR| ´e o n´umero de runs na lista LR. O pior caso do pesudo-algoritmo
ocorre quando todos os runs n˜ao passarem na regra de distˆancia, definida anteriormente.
Segundo Almeida, poderemos ter uma situa¸c˜ao onde um run est´a pr´oximo a um match
isolado, e ambos n˜ao podem ser juntados se estiverem isolados no decorrer do proteoma.
Essa jun¸c˜ao pode ser importante, pois po der´a gerar uma regi˜ao com 3 ou mais matches.
Para esses casos, permitiremos que o run possa ser juntado com o match se este match
contribuir significativamente para a regi˜ao, ou seja, se o match for BBH e obedecer a regra
de distˆancia em rela¸c˜ao ao run. Logo, consideramos um BBH isolado como um run.
egg mostra as regi˜oes ort´ologas encontradas em um arquivo texto. Na Figura 3.8 temos
um trecho do arquivo texto da Regi˜ao Ort˜ologa resultante da compara¸c˜ao entre Xylella
fastidiosa 9a5c e Neisseria meningitidis MC58. Maiores detalhes sobre o arquivo de texto
podem ser vistos no Apˆendice A.
>XFNMB20060710-26-Rc
7 matches
7kb in XF - 10kb in NMB
=====================================================================
Gene Synonym (XF) gi size product
=====================================================================
+_ XF0736 15837338 635aa threonyl-tRNA synthetase
+infC XF0737 15837339 159aa translation initiation factor IF-3
+_ XF0738 15837340 31aa hypothetical protein
+rpmI XF0739 15837341 65aa 50S ribosomal protein L35
+_ XF0740 15837342 119aa 50S ribosomal protein L20
+pheS XF0741 15837343 333aa phenylalanyl-tRNA synthetase alpha subunit
+pheT XF0742 15837344 792aa phenylalanyl-tRNA synthetase beta subunit
+_ XF0743 15837345 99aa integration host factor alpha subunit
=====================================================================
Gene Synonym (NMB) gi size product
=====================================================================
+thrS NMB0720 15676618 637aa threonyl-tRNA synthetase
+infC NMB0721 15676619 155aa translation initiation factor 3
+rpmI NMB0722 15676620 65aa 50S ribosomal protein L35
+rplT NMB0723 15676621 119aa 50S ribosomal protein L20
+pheS NMB0724 15676622 330aa phenylalanyl-tRNA synthetase alpha subunit
+_ NMB0725 15676623 352aa modification methylase HgaI-1
+_ NMB0726 15676624 489aa type II restriction enzyme HgaI
+_ NMB0727 15676625 216aa N-6 adenine-specific DNA methylase
+phe NMB0728 15676626 787aa phenylala nyl- tRNA synthetase beta subunit
+himA NMB0729 15676627 100aa integration host factor, alpha subunit
=======
matches
=======
===============================================================================================
Gene Synonym start size e-value [ best hit ] product
===============================================================================================
+_ XF0743 698556 99 1e-27 [best ] integration host factor alpha subunit
+himA NMB0729 761371 100 2e-27 [best ] integration host factor, alpha subunit
------------------------------------------
+pheT XF0742 696154 792 1e-151 [best ] phenylalanyl tRNA synthetase beta subunit
+pheT NMB0728 758934 787 1e-150 [best ] phenylalanyl tRNA synthetase beta subunit
------------------------------------------
+pheS XF0741 695069 333 1e-104 [best ] phenylalanyl tRNA synthetase alpha subunit
+pheS NMB0724 754557 330 2e-88 [best ] phenylalanyl tRNA synthetase alpha subunit
------------------------------------------
+_ XF0740 694438 119 2e-40 [best ] 50S ribosomal protein L20
+rplT NMB0723 753852 119 1e-35 [best ] 50S ribosomal protein L20
------------------------------------------
+rpmI XF0739 694230 65 2e-12 [best ] 50S ribosomal protein L35
+rpmI NMB0722 753642 65 3e-12 [best ] 50S ribosomal protein L35
------------------------------------------
+infC XF0737 693490 159 2e-47 [best ] translation initiation factor IF 3
+infC NMB0721 753028 155 3e-55 [best ] translation initiation factor 3
------------------------------------------
+_ XF0736 691467 635 0 [best ] threonyl tRNA synthetase
+thrS NMB0720 751043 637 0 [best ] threonyl tRNA synthetase
------------------------------------------
Figura 3.8: Exemplo de uma RO entre Xylella fastidiosa 9a5c e Neisseria meningitidis
MC58.
27
Na Figura 3.9, temos uma representa¸c˜ao gr´afica da regi˜ao ort´ologa da Figura 3.8 resultante
da jun¸c˜ao de 3 runs com 2, 3 e 2 matches respectivamente. O gene de cor preta ilustra
um gene anotado como hipot´etico. O sentido das setas representam as orienta¸c˜oes dos
genes, como na Figura 3.6.
NMB0720
XF0736 XF0743
NMB0729
Figura 3.9: Representa¸c˜ao gr´afica da RO da Figura 3.8.
Espinha Dorsal
Segundo a metodologia desc rita na Se¸c˜ao 3.1.4, egg implementa a espinha dorsal entre
os proteomas utilizando o algoritmo de programa¸c˜ao dinˆamica descrito por Cormen e
outros [14], para o problema de LCS, definido na Se¸c˜ao 2.2. Particularmente, as seq¨uˆencias
s e t de entrada s˜ao tais que, s
i
= i, para 1 ≤ i ≤ m, representando os genes de G e
t
j
= p(j), para 1 ≤ j ≤ n, representando os genes de H, onde p(j) = i se, e s omente se,
(g
i
, h
j
) forem BBHs, ou p(j) = 0 caso contr´ario.
O programa egg encontra a espinha dorsal entre os proteomas de forma direta e reversa,
com a finalidade de encontrar a espinha dorsal que mais evidencie o quanto os genomas
s˜ao parecidos. Na forma direta, as seq¨uˆencias s e t s˜ao conforme definimos acima. Por´em
na forma reversa, trocamos a seq¨uˆencia t pela sua seq¨uˆencia reversa e comparamos com
a seq¨uˆencia s da mesma forma como descrito no par´agrafo acima.
Por fim, egg mostra as espinhas dorsais em arquivos textos. Na figura 3.10 temos um
trecho do arquivo texto que mostra a espinha dorsal direta entre os proteomas de Xantho-
monas axonopodis pv. citri str. 306 e Xanthomonas campestris pv. campestris str. ATCC
33913. Maiores detalhes sobre o arquivo texto podem s er vistos no Apˆendice A.
28
===========================================================================================================================================
PRODUCT START..END GENE(STRAND) (STRAND)GENE START..END PRODUCT
===========================================================================================================================================
chromosomal replication initiator 42..1370 XAC0001 (+) <<<>>> (+) XCC0001 42..1370 chromosomal replication initiator
DNA polymerase III beta chai 1647..2747 XAC0002 (+) <<<>>> (+) XCC0002 1646..2746 DNA polymerase III beta chain
DNA replication and repair RecF 3799..4905 XAC0003 (+) <<<>>> (+) XCC0003 3633..4739 DNA replication and repair RecF protein
DNA gyrase subunit 5020..7464 XAC0004 (+) <<<>>> (+) XCC0004 4853..7297 DNA gyrase subunit B
hypothetical protein 7685..8368 XAC0005 (+) <<<>>> (+) XCC0005 7359..8201 hypothetical protein
hypothetical protein 8552..9358 XAC0006 (+) <<<>>> (+) XCC0006 8264..9070 hypothetical protein
hypothetical protein 9636..10829 XAC0007 (+) <<<>>> (+) XCC0007 9209..10405 hypothetical protein
TonB protein 10983..11654 XAC0008 (+) <<<>>> (+) XCC0008 10559..11230 TonB protein
biopolymer transport ExbB protein 11740..12501 XAC0009 (+) <<<>>> (+) XCC0009 11315..12076 biopo lymer transport ExbB protein
biopolymer transport ExbD1 protein 12548..12970 XAC0010 (+) <<<>>> (+) XCC0010 12123..12545 biop olyme r transport ExbD1 protein
biopolymer transport ExbD2 protein 12974..13387 XAC0011 (+) <<<>>> (+) XCC0011 12549..12959 biop olyme r transport ExbD2 protein
pyridoxal phosphate biosynthetic 13649..14416 XAC0012 (-) <<<>>> (-) XCC0012 14113..14883 pyridoxal phosphate biosyn
hypothetical protein 14424..14756 XAC0013 (-) <<<>>> (-) XCC0013 14891..15160 hypothetical protein
cardiolipin synthetas 14768..16228 XAC0014 (-) <<<>>> (-) XCC0014 15235..16695 cardiolipin synthetase
hypothetical protein 16671..17330 XAC0015 (+) # -
hypothetical protein 17330..17920 XAC0016 (+) # -
hypothetical protein 18131..19258 XAC0017 (-) <<<>>> (+) XCC0015 16981..18075 hypothetical protein
hypothetical protein 19442..20359 XAC0018 (-) <<<>>> (-) XCC0016 18170..18940 hypothetical protein
outer_membrane protein 20413..21753 XAC0019 (-) <<<>>> (-) XCC0017 19513..20853 outer membrane protein
hypothetical protein 21972..22664 XAC0020 (+) <<<>>> (+) XCC0018 21074..21766 hypothetical protein
Figura 3.10: Trecho do arquivo texto da espinha dorsal direta entre os BBHs dos geno-
mas dos organismos Xanthomonas axonopodis pv. citri str. 306 (Xac) e Xanthomonas
campestris pv. campestris str. ATCC 33913 (Xcc).
3.3 Novas Funcionalidades
Com o advento do seq¨uenciamento de ESTs, muitas das ESTs tem sido seq¨uenciadas
como uma alternativa ao seq¨uenciamento completo dos genomas. Ferramentas de Bioin-
form´atica baseadas em an´alise de seq¨uˆencias tˆem sido estendidas ao escopo da an´alise de
ESTs no campo da proteˆomica, desenvolvimento de marcadores e anota¸c˜ao genˆomica [29].
Embora existam metodologias baseadas em arrays (Macroarrays ou Microarrays) que
permitem a investiga¸c˜ao massiva e de forma paralela da express˜ao de genes, podemos
utilizar tamb´em as seq¨uˆencias de ESTs para inferir similaridades entre genes e ESTs,
como realizado com ESTs de fungos pat´ogenos e genes de fungos n˜ao pat´ogenos [41].
Dessa forma, para utilizarmos o programa egg para an´alise ou compara¸c˜ao entre ESTs e
genes de genomas seq¨uenciados completamente, necessitar´ıamos manipular as informa¸c˜oes
de entrada (ESTs) para que egg executasse adequadamente. Assim, surgiu a necessi-
dade da implementa¸c˜ao de uma ferramenta menos robusta, por´em que pudesse inferir
informa¸c˜oes s obre os conjuntos de seq¨uˆencias em compara¸c˜ao. Para atender a essas ne-
cessidades, implementamos a ferramenta denominada egg-lite, que possibilita a com-
para¸c˜ao de dois conjuntos de seq¨uˆencias provenientes de genomas incompletos para inferir
similaridade entre elas.
A estrutura do programa egg-lite ´e semelhante a egg, por´em sem a cria¸c˜ao das estrutu-
ras organizacionais, terce ira fase de egg. egg-lite realiza a compara¸c˜ao das seq¨uˆencias
de forma todas-contra-todas, utilizando tamb´em a ferramenta blast. No final dessa
fase, egg-lite, assim como egg, determina os genes espec´ıficos, da mesma forma como
descrito na Se¸c˜ao 3.2.1. Em seguida, os matches e os BBHs tamb´em s˜ao determinados,
29
conforme descrito na Se¸c˜ao 3.2.1. Como esperado, egg-lite n˜ao constr´oi as estrutu-
ras organizacionais, pois estas dependem de informa¸c˜oes relativas ao posicionamento dos
genes no genoma.
O programa egg-lite mostra a descri¸c˜ao das seq¨uˆencias que fizeram BBH, matches e que
s˜ao espec´ıficas, em arquivos texto, contendo as informa¸c˜oes descritivas de cada seq¨uˆencia
a partir de seus arquivos multi-fasta.
As figuras a seguir mostram trechos dos arquivos de sa´ıda para as seq¨uˆencias que fizeram
BBH, matches e que s˜ao espec´ıficas.
##############################
CGPB bidirectional best hits
##############################
==============================================================================================
Identifier
==============================================================================================
(CHG00002.1) hypothetical pro tein (translation)
Contig1420 nucleotide excisio n repair protein rad23 homolog
------------------------------------
(CHG00007.1) hypothetical pro tein (translation)
PBGAC-M1-015t_D06 Sulfur meta boli te repression control protein
------------------------------------
(CHG00008.1) hypothetical pro tein (translation)
Contig1600
------------------------------------
(CHG00009.1) hypothetical pro tein (translation)
PBDEX-M1-035t_D07 zinc metall o-pr otea se
------------------------------------
(CHG00013.1) hypothetical pro tein (translation)
Contig582 vacuolar aminopeptidase ysc1
------------------------------------
Figura 3.11: Trecho do arquivo de BBHs entre genes do organismo Chaetomium globosum
(Cg) e ESTs do organismo Paracoccidioides brasiliensis (Pb), respectivamente.
##############################
matches between PA and PB
##############################
==============================================================================================
Identifier
==============================================================================================
pans_AUG:pans_0-g1.1 pans_0:join(684..752,818..1464,1517..2027) cdslen=1227
Contig25 Probable 26S protease subunit and member of CDC48/PAS1/SEC18 family of ATPases
------------------------------------
pans_AUG:pans_0-g1.1 pans_0:join(684..752,818..1464,1517..2027) cdslen=1227
Contig935 Microsomal protein of CDC48/PAS1/SEC18 family of ATPa ses
------------------------------------
pans_AUG:pans_0-g1.1 pans_0:join(684..752,818..1464,1517..2027) cdslen=1227
Contig1120 40 kDa putative membrane-spanning ATPase
------------------------------------
pans_AUG:pans_0-g1.1 pans_0:join(684..752,818..1464,1517..2027) cdslen=1227
Contig1407 Probable 26S protease subunit and member of the CDC48/PAS1/SEC18 family of ATPases; Rpt5p
------------------------------------
pans_AUG:pans_0-g1.1 pans_0:join(684..752,818..1464,1517..2027) cdslen=1227
PBDEX-M1-006t_A08 ATPase, NSF A, protein involved in protein transpo rt between endoplasmic reticulum and Golg
------------------------------------
Figura 3.12: Trecho do arquivo de matches entre genes do organismo Podospora anserina
(Pa) e ESTs do organismo Paracoccidioides brasiliensis (Pb).
30
##############################
AO genes with no hits in PB
##############################
==============================================================================================
Identifier
==============================================================================================
AO090001000007 AP007154:join(10406..11844,12269..12296) cdslen=1467
AO090001000009 AP007154:complement(join(25153..25587,16084..25080)) cdslen=9432
AO090001000010 AP007154:join(26017..26072,26127..26407,26490..26695,26742.. 268 71
AO090001000011 AP007154:complement(join(30510..30705,30277..30457,30071..30 223 ))
AO090001000018 AP007154:41615..43270 cdslen=1656
AO090001000023 AP007154:join(57665..57975,58037..58595) cdslen=870
AO090001000025 AP007154:complement(join(62298..62392,62146..62237,62033..62 135 ,617 28.. 6197 7)) cdslen=540
AO090001000026 AP007154:complement(join(62904..62975,62523..62849)) cdslen=399
AO090001000034 AP007154:76702..77472 cdslen=771
AO090001000037 AP007154:complement(join(83716..84113,83116..83662)) cdslen=945
AO090001000042 AP007154:join(90812..91034,91086..91245,91297..92182) cdslen=1269
AO090001000044 AP007154:complement(join(99713..100075,98985..99697,98216..9 896 3)) cdslen=1824
AO090001000046 AP007154:complement(join(102947..103337,102575..102895,10180 4.. 1025 13)) cdslen=1422
AO090001000048 AP007154:104000..104836 cdslen=837
AO090001000055 AP007154:complement(join(117051..117101,116618..116989,11639 4.. 1164 29)) cdslen=459
Figura 3.13: Trecho do arquivo de genes espec´ıficos do organismo Aspergillus oryzae (Ao)
em rela¸c˜ao as ESTs do organismo Paracoccidioides brasiliensis (Pb).
Al´em do desenvolvimento da ferramenta egg-lite, descrevemos como uma nova fun-
cionalidade a implementa¸c˜ao da metodologia descrita na Se¸c˜ao 3.1.2 para encontrar as
REs, a descri¸c˜ao e implementa¸c˜ao de uma nova proposta de metodologia para encontrar
as fam´ılias de genes par´alogos de um organismo. No Cap´ıtulo 4 apresentaremos essa
metodologia e sua implementa¸c˜ao.
3.4 Outras ferramentas
Descreveremos nessa se¸c˜ao alguns trabalhos que utilizam regi˜oes ort´ologas ou estruturas
semelhantes para possibilitar a determina¸c˜ao funcional dos genes e a caracteriza¸c˜ao de
aspectos ligados `a funcionalidade dos genomas.
Salzberg e colegas [31, 32] descrevem um m´etodo para alinhar genomas relacionados dis-
tantemente pela detec¸c˜ao de homologia entre seq¨uˆencias de prote´ınas. O m´etodo, deno-
minado de promer, ´e uma extens˜ao do programa mummer [31, 32], e em resumo, alinha
dois genomas depois de traduzir suas seq¨uˆencias de entrada, para cada genoma, em todos
os seis frames de leitura, extraindo e agrupando todas as seq¨uˆencias de prote´ınas que se
“relacionaram”. Denominam-se esses “relacionamentos” de matches.
Especificamente, dado dois arquivos multi-fasta com seq¨uˆencias de nucleot´ıdeos, promer
traduzir´a essas seq¨uˆencias em seq¨uˆencias de amino´acidos considerando os seis frames de
leitura. Nesse passo, um ´ındice ´e criado para mapear todas as seq¨uˆencias de prote´ınas e
seus tamanhos para a seq¨uˆencia de DNA de origem, sendo es te ´ındice usado posteriormente
para mapear as seq¨uˆencias que fizeram matches no DNA de origem. As seq¨uˆencias de
amino´acidos transcritas s˜ao ent˜ao filtradas para remover aquelas que tiveram um n´umero
excessivo de stop c´odons, indicando que provavelmente n˜ao ser˜ao partes de uma prote´ına.
Ap´os esses passos, as seq¨uˆencias transcritas para amino´acidos de cada genoma de entrada
31
s˜ao concatenadas para formarem uma ´unica seq¨uˆencia de amino´acidos, que representa
todas as potenciais prote´ınas no genoma.
Esses pseudo-proteomas s˜ao parˆametros de entrada para o programa mummer, que de-
termina todos os matches exatos e n˜ao exatos com um tamanho maior ou igual a um
valor l. O ´ındice criado anteriormente ´e utilizado para mapear as s eq¨uˆencias matches
de volta na seq¨uˆencia de DNA original. Ap´os serem identificados, os matches s˜ao ent˜ao
agrupados de acordo com suas respectivas coordenadas de DNA. As seq¨uˆencias matches
s˜ao unidas em um mesmo grupo se o tamanho do intervalo entre elas for menor do que um
valor g, determinado pelo usu´ario. Cada grupo ´e analisado quanto ao n´umero m´ınimo de
matches consecutivos dentro do grupo. Quando esse n´ume ro de matches ´e no m´ınimo c,
esse grupo ser´a levado em considera¸c˜ao. Os grupos resultantes s˜ao ent˜ao estendidos para
“cobrir” uma parte maior da regi˜ao de alinhamento. Esse passo ´e realizado utilizando-se
o algoritmo de programa¸c˜ao dinˆamica com “bandas” [36]. As informa¸c˜oes do alinhamento
resultante s˜ao ent˜ao utilizadas pelo programa “MapView” [32] que mostra os alinhamentos
graficamente.
Comparando a metodologia de promer com a nossa metodologia de egg, temos que
ambas utilizam grupos de seq¨uˆencias matches para estabelecer regi˜oes de alinhamento
entre os genomas de dois organismos. Enquanto promer utiliza mummer para determi-
nar todas as seq¨uˆencias matches exatas e n˜ao exatas, egg utiliza blast para determinar
as seq¨uˆencias que fizeram hits, matches e BBHs. A metodologia de agrupamento utili-
zada em egg ´e semelhante a utilizada por promer, por´em egg utiliza dois parˆametros
de entrada, max small gaps e max large gaps, para determinar a proximidade entre os
RUNs, com pelo menos M matches, que far˜ao parte das regi˜oes ort´ologas (ROs). Por fim,
egg determina o alinhamento entre os proteomas utilizando o algoritmo de programa¸c˜ao
dinˆamica conforme descrito por Cormen [14], enquanto que promer utiliza a vers˜ao com
“bandas” desse algoritmo. Ambos possibilitam a visualiza¸c˜ao do alinhamento entre os
proteomas, gerando um arquivo de formato “pdf”.
Al´em de possibilitar a visualiza¸c˜ao do alinhamento entre os proteomas, egg determina
as seq¨uˆencias e as regi˜oes exclusivas a cada genoma, e mostra essas informa¸c˜oes em ar-
quivos textos. egg gera tamb´em arquivos textos para cada produto obtido durante as
compara¸c˜oes entre as seq¨uˆencias, como: os hits, matches, BBHs, RUNs, ROs, etc.
Enquanto promer ´e utilizado para determinar os alinhamentos entre os genomas baseado
na tradu¸c˜ao das seq¨uˆencias nos seis frames de leitura, egg al´em de possibilitar tamb´em
essa forma de compara¸c˜ao, permite a compara¸c˜ao das seq¨uˆencias de DNA dos genomas,
sem diretamente traduz´ı-las. Dessa forma, egg possibilita “agregar” as funcionalidades
dos programas nucmer e promer [31, 32], pacotes de extens˜ao do mummer [32], utili-
zando uma metodologia diferente para detectar as similaridades entre as seq¨uˆencias em
compara¸c˜ao.
Tamames [39] apresentou uma an´alise da extens˜ao e das caracter´ısticas da ordem de con-
serva¸c˜ao dos genes em procariotos, tentando determinar se essa ordem ocorre similarmente
para os procariotos e se essas regi˜oes conservadas est˜ao distribu´ıdas uniformemente nos
genomas.
Para determinar essas informa¸c˜oes, Tamames empregou uma metodologia tamb´em base-
ada na similaridade de blast. Nesse caso, para que duas ORFs de genomas distintos
32
sejam consideradas hom´ologas, o alinhamento entre elas deve cobrir 75% do tamanho das
ORFs e o valor de e-value deve ser menor ou igual a 10
−5
. O relacionamento entre as
ORFs que atenderam a essa caracter´ıstica foi denominado de hits bidirecionais (BHs).
Em egg, utilizamos o termo “match” para definir essa forma de relacionamento. Como
genes par´alogos podem existir, Tamames utilizou BBHs para determinar os resultados, e
utilizou a estrutura dos RUNs para definir um agrupamento de genes no qual a ordem dos
genes est´a conservada. Tamames define o conceito de BBHs como em 3.2.1. Os RUNs que
foram utilizados n˜ao continham genes pertencentes `a fitas diferentes, o que difere de egg
que permite a constru¸c˜ao de RUNs com genes de fitas diferentes. Os RUNs de Tamames
s˜ao constru´ıdos com o m´ınimo de 3 BBHs, permitindo uma distˆancia m´axima de 3 genes
entre os BBHs. egg tamb´em especifica um parˆametro para o n´umero m´ınimo de matches
pertencentes aos RUNs. Para medir a ordem de conserva¸c˜ao de genes entre dois genomas,
Tamames utilizou a taxa entre o n´ume ro de genes localizados em RUNs conservados, e o
n´umero total de genes que fizeram BBHs. Por fim, m´etodos de filogenia molecular foram
utilizados para determinar o grau de relacionamento entre os organismos [39].
egg n˜ao implementa uma medida de ordem de conserva¸c˜ao de genes, no entanto, egg
poderia ser utilizado para determinar a conserva¸c˜ao da ordem dos genes entre dois organis-
mos, pois implementa as estruturas necess´arias a essa an´alise. Dessa forma, a conserva¸c˜ao
da ordem dos genes poderia ser utilizada como uma medida filogen´etica para estudar os re-
lacionamentos entre as esp´ecies, mesmo entre esp´ecies distantes filogeneticamente, no qual
a ordem de conserva¸c˜ao dos genes existe na forma de agrupamentos de genes altamente
conservados, sugerindo a existˆencia de um processo seletivo que mant´em a organiza¸c˜ao
dessas regi˜oes [39]. egg foi utilizado com esse prop´osito no trabalho de Ara´ujo [10].
Kellis e colegas [23] apresentaram um m´etodo para a determina¸c˜ao autom´atica da corres-
pondˆencia genˆomica. O m´etodo apresentado foi utilizado para o alinhamento entre os ge-
nomas das esp´ecies das Saccharomyces: S. paradoxus, S.mikatae, S.bayanus e S.cerevisiae,
permitindo uma correta identifica¸c˜ao de genes ort´ologos n˜ao-amb´ıguos, cerca de mais de
90% dos n˜ao-amb´ıguos genes codantes dessas prote´ınas.
Em resumo, o algoritmo representa as similaridades entre os genes como um grafo bi-
partido, com “peso” nas arestas, conectando genes entre duas esp´ecies. Para “pesar” ou
pontuar as arestas que conectam dois genes, foram utilizados ambos, a similaridade entre
os amino´acidos das seq¨uˆencias entre dois genes e o tamanho total de alinhamento entre
os genes.
O grafo ´e separado progressivamente em sub-grafos menores, at´e que somente os matches
remanescentes conectem ort´ologos “verdadeiros”. Essa separa¸c˜ao ´e atingida eliminando
arestas que s˜ao sub-´otimas em uma s´erie de passos.
No primeiro passo, denominado de pr´e-processamento, s˜ao eliminadas todas as arestas
cuja pontua¸c˜oes s˜ao menores do que 80% da aresta de m´axima pontua¸c˜ao do n´o, conside-
rando ambos, a identidade em amino´acidos e o tamanho de alinhamento entre os genes.
Como segundo passo, baseado nos matches (arestas) n˜ao-amb´ıguos que resultaram do
passo anterior, s˜ao constru´ıdos blocos de genes de ordem conservada (blocos sintˆenicos)
utilizando os matches na forma um-para-um entre os genes de esp´ecies distintas. Esses
blocos s˜ao utilizados para resolver ambig¨uidades adicionais, entre os genes pertencentes
a esses blocos, e genes que n˜ao pertencem aos blocos. Finalmente, como terceiro passo,
33
s˜ao procurados os subconjuntos de genes que s˜ao ´otimos locais, tais que todos os melho-
res matches dos genes dentro de um grupo est˜ao contidos dentro desse grupo; e nenhum
gene fora do grupo possui matches dentro desse grupo. Esses conjuntos de matches s˜ao
denominados de BUS do tˆermo em inglˆes Best Unambiguous Subsets e asseguram que o
grafo bipartido ´e maximalmente separ´avel, mantendo todos os poss´ıveis relacionamentos
ort´ologos [22].
Quando nenhuma separa¸c˜ao posterior for poss´ıvel, as componentes conexas do grafo final
s˜ao retornadas. Ess as componentes contˆem pares de genes ort´ologos na forma um-para-
um.
A metodologia desc rita por Kellis [23] difere em alguns aspectos da metodologia em-
pregada em egg. Em egg, utilizamos os B BHs, ao inv´es do BUS. Nesse caso, temos
um relacionamento na forma um-para-um entre as seq¨uˆencias de um genoma contra as
seq¨uˆencias de um outro genoma, sem utilizar diretamente o valor de identidade entre as
bases de seq¨uˆencias comparadas. Utilizamos os valores e-value e porcentagem de sobre-
posi¸c˜ao para relacionar dois genes de genomas distintos, formando um BBH da forma
descrita na Se¸c˜ao 3.2.1. Assim como Kellis, primeiramente constru´ımos blocos de genes
de ordem conservada (RUNs), e em seguida, aumentamos esses blocos para formarem
uma regi˜ao ort´ologa, baseado nas informa¸c˜oes sintˆenicas desses genes. Por fim, utilizamos
esses BBHs, juntamente com as ROs, para determinar o alinhamento (Espinha Dorsal)
entre os conjuntos de prote´ınas dos genomas.
Embora as metodologias aplicadas em egg e Kellis [22, 23] considerem medidas diferentes
para determinar uma correspondˆencia entre os genes de dois genomas, faz-se necess´aria
uma an´alise mais refinada entre essas metodologias, utilizando o mesmo conjunto de dados
de Kellis [23], para comprovar a afirma¸c˜ao de que a utiliza¸c˜ao dos BBHs, ao inv´es do BUS,
no caso de um recente evento de duplica¸c˜ao, marca somente um dos genes duplicados
como ort´ologo, sem sinalizar a presen¸ca de hom´ologos adicionais. Logo, segundo Kellis,
o m´etodo de egg estaria apontando rela¸c˜oes de ortologia incorretamente, e nesse caso,
os BBHs deixariam de representar relacionamentos ort´ologos, possibilitando que matches
sejam determinados incorretamente na forma um-para-um.
34
Cap´ıtulo 4
Determina¸c˜ao de genes par´alogos
Devido `as duplica¸c˜oes internas que podem ocorrer em um genoma, segundo Cannon e
Young [13], para estendermos o conhecimento sobre genes entre esp´ecies filogeneticamente
relacionadas, ´e importante distinguirmos genes que est˜ao diretamente relacionados uns
aos outros atrav´es de eventos de especia¸c˜ao (ort´ologos), dos genes que tiveram duplica¸c˜ao
independente da especia¸c˜ao (par´alogos).
Como um dos objetivos ´e determinarmos as fam´ılias de genes par´alogos, e como abordamos
a determina¸c˜ao dos genes ort´ologos na Se¸c˜ao 3.2.1, no presente cap´ıtulo, descreveremos
a metodologia utilizada por Almeida [1] para obter as fam´ılias de genes par´alogos, uma
nova proposta para reformular a metodologia de Almeida e a implementa¸c˜ao dessa nova
proposta.
O cap´ıtulo est´a organizado da seguinte forma. Na Se¸c˜ao 4.1 descrevemos a metodologia
aplicada por Almeida [1] e uma nova proposta reformulativa para essa metodologia, e na
Se¸c˜ao 4.2 apresentamos os resultados.
4.1 Metodologia
A metodologia de Almeida [1] para encontrar fam´ılias de genes par´alogos ´e baseada nos
valores da significˆancia estat´ıstica de similaridade e na cobertura de alinhamento, ambos
valores disponibilizados por blast, que s˜ao crit´erios semelhantes aos utilizados para a
determina¸c˜ao dos genes ort´ologos, como definido na Se¸c˜ao 3.1.1.
Intuitivamente, a metodologia de Almeida possui as trˆes fases seguintes:
1. Encontrar os genes que s˜ao similares entre si e construir fam´ılias com esses genes,
considerando valores de significˆancia e stat´ıstica de similaridade e cobertura de ali-
nhamento entre os genes;
2. Agregar genes externos a essas fam´ılias, segundo valores menos exigentes de signi-
ficˆancia estat´ıstica de similaridade e cobertura de alinhamento; e
35
3. Para todos os genes que pertencem a mais de uma fam´ılia, removˆe-los das fam´ılias
com que menos se identificam, segundo o crit´erio de significˆancia de similaridade
m´edia entre esses genes e todos os outros genes da fam´ılia.
Os valores utilizados por Almeida para implementar a significˆancia estat´ıstica de simila-
ridade e cobertura de alinhamento foram o e-value e a porcentagem m´edia de cobertura
entre os genes comparados.
Objetivando melhorias na t´ecnica descrita acima, desenvolvemos juntamente com Almeida
e colegas [5], uma nova metodologia para tentar determinar as fam´ılias de genes par´alogos,
que ´e baseada em cliques maximais em grafos e modelos ocultos de Markov.
A nova proposta de metodologia consiste de duas fases. Na primeira fase, denominada de
“Agrupamento de seq¨uˆencias”, juntamos todas as prote´ınas em fam´ılias iniciais, baseadas
em cliques maximais em grafos. A segunda fase, intitulada “Busca hom´ologos”, constr´oi
um perfil dessas fam´ılias iniciais, segundo os modelos ocultos de Markov. Nas se¸c˜oes
seguintes descreveremos estas duas fases.
4.1.1 Agrupamento de seq¨uˆencias
Essa fase consiste em trˆes passos. No primeiro passo, realizamos a compara¸c˜ao das
prote´ınas na forma todas-contra-todas, utilizando o blast como ferramenta compara-
tiva. Consideramos duas prote´ınas g, h similares se, e somente se, g e h possu´ırem valores
de e-value rec´ıprocos menores ou igual a 10
−5
e com pelo menos 60% de alinhamento entre
as seq¨uˆencias. Utilizamos a condi¸c˜ao de porcentagem de cobertura das seq¨uˆencias no ali-
nhamento com a finalidade de evitarmos o agrupamento das prote´ınas que compartilham
pequenas faixas de alinhamentos, chamadas de “dom´ınios prom´ıscuos” [19]. Prote´ınas
que compartilham somente uma parte pequena desses dom´ınios n˜ao compartilham uma
hist´oria evolucion´aria e n˜ao podem ser membros da mesma fam´ılia.
O segundo passo consiste em construir um grafo G, onde os v´ertices s˜ao as prote´ınas e
as arestas representam os pares de prote´ınas similares. A id´eia consiste em encontrar
estruturas nesse grafo, de tal forma que representem as fam´ılias de prote´ınas similares.
Utilizamos nesse sentido, as cliques em grafos, definidas na Se¸c˜ao 2.2. Especificamente,
estamos interessados em cliques maximais. O problema de determinar todas as cliques
maximais ´e NP-Dif´ıcil [14], por´em na pr´atica, os grafos que representam os relaciona-
mentos de similaridade entre os genes de dois genomas, em grande maioria s˜ao esparsos.
Al´em disso, primeiramente separamos o grafo G em componentes conexas e aplicamos o
algoritmo de for¸ca bruta para encontrar todas as cliques maximais em cada componente,
que na maioria s˜ao pequenas, em rela¸c˜ao ao n´umero de v´ertices. Ao final desse passo
temos todas as cliques maximais de G.
O terceiro passo da primeira etapa consiste na jun¸c˜ao de cliques maximais de uma mesma
componente que compartilham muitos v´ertices. Decidimos juntar quaisquer cliques ma-
ximais, pertencentes a uma mesma componente, que compartilham pelo menos 50% do
n´umero de v´ertices da menor clique. Denominamos a estrutura resultante de JMC, do
termo em inglˆes Joined Maximal Clique. Dessa forma, podemos definir uma JM C em G
da seguinte forma:
36
• Uma JMC ´e uma clique maximal em G; ou
• ´e a uni˜ao de duas ou mais JMCs.
Na figura abaixo temos uma representa¸c˜ao de duas cliques maximais abstratas C
1
e C
2
formando uma ´unica JMC. A figura ilustra a condi¸c˜ao de jun¸c˜ao, onde mais do que 50%
do n´umero de v´ertices da clique C
2
s˜ao adjacentes com os v´ertices da clique C
1
.
C
1
C
2
JMC
Figura 4.1: Representa¸c˜ao de uma JMC. Os v´ertices de cor preta pertencem a clique C
1
,
enquanto que os v´ertices de cor branca pertencem a clique C
2
.
O resultado dessa fase ´e um conjunto de JMCs represe ntando fam´ılias iniciais de prote´ınas
similares. Essas fam´ılias constituem a entrada para a segunda fase, descrita em seguida.
4.1.2 Busca hom´ologos
A id´eia dessa fase consiste em construir modelos para cada JMC, c riada na fase anterior,
e buscar por prote´ınas que n˜ao fazem parte das JMCs, para que possam ser unidas a essas
fam´ılias, segundo um crit´erio de similaridade entre a nova prote´ına e o modelo.
Nossa metodologia utiliza os modelos estat´ısticos de alinhamentos m´ultiplos de seq¨uˆencia,
denominados “Profile Hidden Markov models” (pHMMs) [33]. Esses modelos s˜ao utili-
zados pois retornam informa¸c˜oes de posi¸c˜oes espec´ıficas e a quantidade de conserva¸c˜ao
de cada coluna do alinhamento, incluindo informa¸c˜oes sobre as “penalidades para bura-
cos” de cada posi¸c˜ao do alinhamento. Para essa proposta, utilizamos a implementa¸c˜ao de
pHMMs para a an´alise de seq¨uˆencias biol´ogicas, denominada hmmer [17].
Para construirmos os modelos, primeiramente descartamos as seq¨uˆencias de uma fam´ılia
que apresentam tamanhos discrepantes em rela¸c˜ao `as outras prote´ınas da fam´ılia. Para
realizar esse procedimento, exclu´ımos as prote´ınas de uma determinada fam´ılia cujo ta-
manho, em n´umero de amino´acidos, est´a a uma distˆancia de D = 3 desvios padr˜oes do
tamanho m´edio das seq¨uˆencias da fam´ılia. O valor D ´e um parˆametro de entrada para o
programa. Em seguida, constru´ımos um alinhamento m´ultiplo com as seq¨uˆencias restan-
tes nas fam´ılias, utilizando o programa clustalw [42]. A elimina¸c˜ao das seq¨uˆencias des-
crita anteriormente ´e realizada com a finalidade de aumentar a qualidade do alinhamento
m´ultiplo. Por fim, utilizamos os trˆes programas seguintes abaixo, do pacote hmmer, para
construir os modelos e buscar por outras prote´ınas hom´ologas.
37
hmmbuild - cria um modelo pHMM para cada fam´ılia, utilizando o alinhamento m´ultiplo
gerado anteriormente;
hmmcalibrate - calibra o pHMM com a finalidade de aumentar a sensibilidade de buscas
futuras; e
hmmsearch - busca por novos membros para cada fam´ılia.
Ap´os executar o programa hmmsearch, se uma prote´ına p cujo v´ertice est´a em uma mesma
componente conexa de uma fam´ılia F e se a prote´ına p puder ser agregada `a fam´ılia F , um
novo modelo pHMM ´e constru´ıdo (incluindo a nova prote´ına p) e ´e calibrado novamente
para novas buscas. Esse passo ´e executado at´e que nenhum pHMM possa ser aumentado.
A figura abaixo ilustra o fluxo de execu¸c˜oes da segunda fase da metodologia para uma
fam´ılia abstrata ’A’.
discrepantes
Elimina
discrepantes
A sem
Alinhamento
m ´ultiplo
Modelo de A
Modelo
calibrado
Modelo com seqs.
agregadas
Nova Fam´ılia A
ClustalW
hmmbuild
JMC A
hmmcalibrate
hmmsearch
Enquanto agregar prote´ınas
Figura 4.2: Fluxo de execu¸c˜ao da fase Busca Hom´ologos
O resultado dessa fase consiste de fam´ılias com pelo menos trˆes prote´ınas contendo in-
forma¸c˜oes sobre a fam´ılia, como o identificador, tamanho e produto das prote´ınas, assim
como o alinhamento m´ultiplo res ultante. A figura abaixo ´e um trecho de um arquivo
texto, contendo uma fam´ılia, resultante da aplica¸c˜ao da nossa metodologia para o orga-
nismo Xylella fastidiosa 9a5c.
38
9105737 1032 transcriptional regulator (LysR family)
9106094 906 transcriptional regulator (LysR family)
9106570 978 oxidative stress transcriptional regulator
9106798 891 transcriptional regulator (LysR family)
9106824 975 transcriptional regulator (LysR family)
9106842 942 transcriptional regulator (LysR family)
# 9106785 666 hypothetical protein
CLUSTAL W (1.83) multiple sequence alignment
gi|9106824 -----------------MARRNLNDLLY FVTI AREG S-FT RAA AHLG VTQ
gi|9106842 MAEKIVKSTYNGAENSPMPKENLNDLQA FVAV ARAR S-FT RAA AQLG LSR
gi|9106094 ------------------MQNMFDGVQL FVEV VEAG G-FA KAG KRLS LTR
gi|9106798 ---------------------------- -MQV VHLG S-FA AAA REQN VDP
gi|9105737 ----MEVIYSRFWFCDISPVMTLTQLRY LVAI ADAD LNIT LAA ARIH ATQ
gi|9106570 ------MWNYIPSLAARFGFMNLRDLKY LIAL ADYK H-FG RAA TACF VSQ
gi|9106785 ---------------------------- ---- ---- ---- --- ---- ---
gi|9106824 SALSQAINGLEARLQIRLLTRTTR-SVS PTAA GERL LNAI GHR FDEI ESE
gi|9106842 SALSHAMLALEARLGVRLLTRTTR-SVS TTEA GARL LDAV APR LDEI ELE
gi|9106094 STIGKAIARLEMRLGVQLFQRTTR-VQS LTED GQQY YERC LRA IKEL RAG
gi|9106798 SSVSRAVAALEAELGTRLFARNTR-HLA LTEA GSVF TERL PLL LEEL SQA
gi|9105737 PGLSKQLKKLEDELGFLLFVRRGRSLES VTPA GEEV IERA RAM LVEV NNI
gi|9106570 PTLSTQIKKLEGELGVSLVERAPR-KVM MTPA GREA AIRA RSI VAEV EEM
gi|9106785 -------------MGALMHDAASR---- ---- ---- ---- --- ---- ---
Figura 4.3: Uma fam´ılia encontrada em Xylella fastidiosa 9a5c. O s´ımbolo # refere-se a
uma prote´ına agregada na s egunda f ase.
Nossa metodologia foi implementada utilizando scripts e programas escritos em C++. O
Apˆendice B cont´em maiores detalhes operacionais desses scripts e programas. Na se¸c˜ao
seguinte abordaremos alguns resultados da utiliza¸c˜ao de nossa metodologia, apresentados
em [5].
4.2 Resultados
A metodologia foi empregada para encontrar fam´ılias de genes par´alogos em cinco geno-
mas. Especificamente, utilizamos os genomas da Pseudomonas aeruginosa PA01 (PS),
Escherichia coli K12 (EC), Synechocystis sp. PCC 6803 (SP), Xylella fastidiosa 9a5c
(XF), e Chlamydia pneumoniae (CP). A Tabela 4.1 cont´em informa¸c˜oes encontradas so-
bre cada fam´ılia nos genomas.
39
organismo N
p
N
cfc
N
fde
N
pi
S
f
PA 5565 16 16 142 0.86
EC 4289 174 170 525 0.81
SP 3169 107 107 264 0.81
XF 2766 57 54 5 0.88
CP 1052 19 18 77 0.84
Tabela 4.1: Informa¸c˜oes das fam´ılias encontradas em cada genoma. N
p
: n´umero de
prote´ınas; N
cfc
: n´umero de componentes fortemente conexas com ≥ 3 v´ertices; N
fde
:
n´umero de fam´ılias depois de descartar seq¨uˆencias esp´urias; N
pi
: n´umero total de prote´ınas
inclu´ıdas; e S
f
: Pontua¸c˜ao m´edia das fam´ılias considerando todas as fam´ılias.
Para avaliar nossa metodologia, utilizamos o n´umero COG [40] de cada prote´ına, ob-
tido no NCB I [49], que supostamente possui uma verifica¸c˜ao manual da informa¸c˜oes nas
seq¨uˆencias. As prote´ınas contidas em cada grupo de n´umeros COG supostamente possuem
alguma rela¸c˜ao com alguma prote´ına ancestral. Para avaliarmos as fam´ılias de prote´ınas
encontradas em cada genoma, utilizamos o valor de Information Content (IC), que ´e uma
medida de como ´e restrita a escolha dos n´umeros COG em cada fam´ılia. O c´alculo do IC
foi realizado como em [38]. A pontua¸c˜ao final s
f
de uma fam´ılia f ´e dado pelo seu IC
dividido pelo m´aximo IC que seria poss´ıvel para a fam´ılia f. Dessa forma, fam´ılias ideais
deveriam possuir s
f
= 1 onde, 0 ≤ s
f
≤ 1. A tabela 4.1 mostra que nossa metodologia,
em m´edia, encontrou acima de 80% de par´alogos corretos.
40
Cap´ıtulo 5
Compara¸c˜ao de trˆes genomas
Neste cap´ıtulo, descrevemos uma proposta [41] para a compara¸c˜ao simultˆanea de trˆes
genomas. A compara¸c˜ao dessas informa¸c˜oes ´e importante pois pode gerar “pistas” das
vias metab´olicas dos genomas e como as prote´ınas compartilhadas pelos genomas est˜ao
envolvidas em determinadas fun¸c˜oes.
Na literatura encontram-se diversas metodologias de compara¸c˜ao genˆomica [1, 16], muitas
delas utilizando informa¸c˜oes apenas de seq¨uˆencias de DNA e outras utilizando seq¨uˆencias
de genes codantes. Dentro desse conjunto de metodologias, existem aquelas que reali-
zam an´alise comparativa entre genomas de organismos n˜ao-pat´ogenos com organismos
pat´ogenos para tentar identificar os genes ou grupos de genes associados `a doen¸cas e
infec¸c˜oes [23].
Em [41] propomos uma metodologia para comparar trˆes genomas simultaneamente, ao
n´ıvel de suas prote´ınas preditas. As informa¸c˜oes de entrada para a metodologia s˜ao os trˆes
conjuntos de seq¨uˆencias de genes codantes, referentes aos trˆes genomas. A sa´ıda consiste
nas seq¨uˆencias exclusivas para cada genoma, nas seq¨uˆencias compartilhadas p elos pares de
genomas e nas seq¨uˆencias compartilhadas pelos trˆes genomas. Comparativamente, a sa´ıda
da metodologia corresponde `as regi˜oes em um diagrama de Venn (Figura 5.1). Determinar
cada regi˜ao do diagrama pode indicar o conjunto de genes compartilhados e exclusivos
dos genomas, fornecendo pistas interessantes sobre as vias metab´olicas compartilhadas, e
tamb´em sobre as prote´ınas relacionadas `a uma fun¸c˜ao em particular.
O m´etodo foi utilizado para a compara¸c˜ao de dois genomas de fungos pat´ogenos com cinco
genomas de fungos n˜ao-pat´ogenos, de trˆes em trˆes simultaneamente, com a finalidade de
inferir os genes envolvidos com patogenicidade.
O cap´ıtulo es t´a organizado da seguinte forma. Na Se¸c˜ao 5.1 abordamos aspectos gerais
da metodologia. Nas se¸c˜oes 5.2 e 5.3 descrevemos aspectos espec´ıficos da metodologia e
os experimentos. Por fim, na Se¸c˜ao 5.4, apresentamos alguns resultados obtidos.
41
5.1 Comparando trˆes genomas
Sejam trˆes genomas P , Q, R. Considere que os genomas s˜ao representados pelos conjuntos
de suas seq¨uˆencias codantes de DNA ou por suas seq¨uˆencias de prote´ınas. Conseguindo
atribuir de forma n˜ao amb´ıgua os genes de cada genoma `a cada regi˜ao do diagrama de
Venn, como da Figura 5.1, essas regi˜oes poderiam representar as seq¨uˆencias compartilha-
das e exclusivas de cada genoma.
(b)
(c)
(a)
Figura 5.1: Diagrama de Venn representando (a) seq¨uˆencias exclusivas a um genoma, (b)
seq¨uˆencias compartilhadas por dois genomas, e (c) seq¨uˆencia compartilhadas pelos trˆes
genomas.
A constru¸c˜ao do diagrama ´e realizada utilizando a similaridade de seq¨uˆencias, com a
finalidade de selecionar as seq¨uˆencias que ser˜ao atribu´ıdas a cada regi˜ao do diagrama.
Na Figura 5.2 est˜ao ilustradas algumas situa¸c˜oes adequadas de atribui¸c˜ao das seq¨uˆencias
`as regi˜oes do diagrama de Venn. As arestas que conectam dois genes indicam que as
seq¨uˆencias desses genes s˜ao similares.
P R
Q
p
1
r
1
q
1
P R
Q
p
1
r
1
P R
Q
p
1
(a) (b) (c)
Figura 5.2: Genes que podem ser atribu´ıdos as regi˜oes do diagrama de Venn. (a) Gene s
em todos os trˆes genomas. (b) Genes pertencentes somente aos genomas P e R. (c) Genes
exclusivos a P .
Como uma seq¨uˆencia de um genoma pode ser similar a muitas outras seq¨uˆencias de
outros genomas, o procedimento de atribui¸c˜ao das seq¨uˆencias `as regi˜oes do diagrama pode
42
encontrar alguns casos complexos, ou seja, casos onde ´e dif´ıcil decidir em qual regi˜ao uma
seq¨uˆencia deve ser inclu´ıda. Esse processo pode conduzir `a rela¸c˜oes entre as seq¨uˆencias
com significado biol´ogico n˜ao muito evidente. Na Figura 5.3 temos trˆes exemplos dessas
rela¸c˜oes.
P R
Q
p
1
p
2
r
1
q
1
P R
Q
p
1
r
1
q
1
P R
Q
p
1
p
2
r
1
q
1
(a) (b) (c)
Figura 5.3: Casos complexos de atribui¸c˜ao dos genes `as regi˜oes do diagrama de Venn.
Nossa metodologia para encontrar as seq¨uˆencias em cada regi˜ao do diagrama de Venn
objetiva evitar os casos complexos. O m´etodo inicia encontrando as seq¨uˆencias simila-
res entre trˆes genomas. A busca por essas seq¨uˆencias similares continua at´e quando n˜ao
encontrar mais seq¨uˆencias compartilhadas entre os trˆes genomas considerando uma de-
terminada pontua¸c˜ao limite T
t
para toda tripla de seq¨uˆencias. Em seguida, buscam-se
pelas seq¨uˆencias comuns a pares de genomas. Esse procedimento continua at´e quando n˜ao
encontrar mais seq¨uˆencias compartilhadas entre dois genomas considerando uma determi-
nada pontua¸c˜ao limite T
e
para toda dupla de seq¨uˆencias. Por fim, as seq¨uˆencias exclusivas
a cada genoma s˜ao determinadas. Na s e¸c˜ao seguinte descreveremos mais detalhadamente
esse m´etodo.
5.2 Descri¸c˜ao do M´etodo
As seguintes considera¸c˜oes s˜ao neces s´arias para descrevermos detalhadamente o m´etodo :
• Uma seq¨uˆencia ´e apenas uma justaposi¸c˜ao de letras;
• As seq¨uˆencias podem ser de DNA ou prote´ına;
• Um genoma consiste de um conjunto de seq¨uˆencias; e
• Denota-se G(p) o genoma ao qual a seq¨uˆencia p pertence.
O m´etodo utiliza os seguintes conceitos de aresta e triˆangulo.
43
Defini¸c˜ao 5.1 (Aresta entre genomas) Dados dois genomas P e Q, uma aresta ´e
um par de seq¨uˆencias (p, q), p ∈ P e q ∈ Q. O peso w de uma aresta (p, q), denotado por
w(p, q), ´e qualquer medida de similaridade que possa avaliar p e q.
Defini¸c˜ao 5.2 (Triˆangulo entre genomas) Dados trˆes genomas P , Q e R, um triˆan-
gulo ´e uma tripla de seq¨uˆencias (p, q, r), p ∈ P , q ∈ Q e r ∈ R, tais que existam as arestas
(p, q), (p, r) e (q, r). O peso w de um triˆangulo (p, q, r), denotado por w(p, q, r), ´e qualquer
medida que possa avaliar w(p, q), w(p, r) e w(q, r).
O m´etodo come¸ca calculando o peso de cada par de seq¨uˆencias de genomas distintos. Em
seguida, os triˆangulos s˜ao processados em ordem n˜ao-crescente dos seus pesos. Um a um
os triˆangulos s˜ao atribu´ıdos `as regi˜oes do diagrama de Venn, at´e que n˜ao existam mais
triˆangulos com peso maior ou igual a T
t
. Quando um triˆangulo (p, q, r) ´e atribu´ıdo `a regi˜ao
central do diagrama, outros triˆangulos ou arestas que contˆem os v´ertices p, q ou r n˜ao
s˜ao levados mais em considera¸c˜ao. Em seguida, as arestas s˜ao processadas uma a uma em
ordem n˜ao-crescente dos seus pesos. Uma ap´os outra as arestas s˜ao atribu´ıdas `as regi˜oes
de intersec¸c˜ao entre dois genomas do diagrama, at´e que n˜ao existam mais arestas com
peso maior ou igual a T
e
. Quando uma aresta (u, v) ´e atribu´ıda `a uma regi˜ao do diagrama,
outras arestas ou v´ertices que contˆem u ou v n˜ao s˜ao mais levados em considera¸c˜ao. Na
p´agina seguinte descrevemos em pseudo-c´odigo o algoritmo intitulado M
´
etodo-3gc que
foi desenvolvido como a descri¸c˜ao dessa metodologia.
A nossa metodologia ´e uma heur´ıstica gulosa, no sentido de que para cada triˆangulo e
aresta selecionados, sempre optamos por atribuir primeiramente aqueles que possuem os
maiores pesos, sem garantia de que esses triˆangulos e arestas evidenciem rela¸c˜oes biologi-
camente corretas entre os genes desses organizas.
O tempo de execu¸c˜ao para um algoritmo que segue os passos da metodologia ´e da ordem
de O(|P||Q|α+|P ||R|α+|Q||R|α+|P ||Q||R|β +|P ||Q|R| log(|P||Q|R|)), que corresponde
ao n´umero de compara¸c˜oes de s eq¨uˆencias `a um custo α por compara¸c˜ao, mais a quantidade
de triˆangulos que podem ser formados a um custo β por triˆangulo. A ´ultima parcela da
soma corresponde ao custo da ordena¸c˜ao dos triˆangulos e arestas.
44
Algoritmo 4 M
´
etodo-3GC
Entrada: Genomas P , Q e R
Sa´ıda: seq¨uˆencias em P , Q e R atribu´ıdas `as regi˜oes do diagrama de Venn.
1: L ← ∅.
2: Calcule w(a, b) para todo par de seq¨uˆencias tal que G(a) = G(b).
3: para todo triˆangulo (p, q, r), p ∈ P , q ∈ Q e r ∈ R, tal que w(p, q, r) ≥ T
t
fa¸ca
4: acrescente (p,q,r) `a lista L;
5: fim para
6: Ordene a lista L na forma n˜ao-crescente em rela¸c˜ao aos pesos dos triˆangulos.
7: enquanto L = ∅ fa¸ca
8: pegue o primeiro triˆangulo de L e renomeie para t, onde t = (p, q, r).
9: acrescente t `a regi˜ao do diagrama.
10: remova qualquer triˆangulo em L que possua p, q ou r como membro
11: remova p, q, r dos genomas P , Q e R.
12: fim enquanto
13: para toda aresta (p, q), p ∈ P e q ∈ Q tal que w(p, q) ≥ T
e
fa¸ca
14: acrescente (p, q) `a lista L;
15: fim para
16: para toda aresta (p, r), p ∈ P e r ∈ R tal que w(p, r) ≥ T
e
fa¸ca
17: acrescente (p, r) `a lista L;
18: fim para
19: para toda aresta (q, r), q ∈ Q e r ∈ R tal que w(q, r) ≥ T
e
fa¸ca
20: acrescente (q, r) `a lista L;
21: fim para
22: Ordene a lista L na forma n˜ao-crescente em rela¸c˜ao aos pesos das arestas.
23: enquanto L = ∅ fa¸ca
24: pegue a primeira aresta de L e renomeie para e, onde e = (a, b).
25: acrescente e `a regi˜ao do diagrama.
26: remova qualquer aresta em L que contenha a ou b como membro.
27: remova a e b de G(a) e G(b) respectivamente.
28: fim enquanto
29: para toda seq¨uˆencia s em P fa¸ca
30: acrescente s `a regi˜ao correspondente exclusivamente a P no diagrama.
31: fim para
32: para toda seq¨uˆencia s em Q fa¸ca
33: acrescente s `a regi˜ao correspondente exclusivamente a Q no diagrama.
34: fim para
35: para toda seq¨uˆencia s em R fa¸ca
36: acrescente s `a regi˜ao correspondente exclusivamente a R no diagrama.
37: fim para
45
5.3 Experimentos
Os experimentos foram realizados utilizando genomas de fungos. Especificamente, foram
utilizados cinco genomas de fungos n˜ao-pat´ogenos e dois genomas de fungos pat´ogenos.
Utilizamos os seguintes genomas: Aspergillus nidulans(9541 s eq¨uˆencias), Candida albi-
cans(6165 seq¨uˆenc ias), Criptococcus neoformans(6578 se q¨uˆencias), Fusarium graminea-
rum(11640 seq¨uˆencias), Magnaporte grisea(11109 seq¨uˆencias), Neurospora crassa(10082
seq¨uˆencias) e Saccharomyces cereviseae(6305 seq¨uˆencias). C. neoformans e C. albicans
s˜ao fungos pat´ogenos de humanos, enquanto que os outros n˜ao s˜ao. Nesses experimentos,
foi definido que uma aresta entre dois v´ertices (genes) ocorre atrav´es da utiliza¸c˜ao dos
hits bidirecionais do programa blast. Dizemos que as seq¨uˆencias p e q, onde p ∈ P e
q ∈ Q formam um hit bidirecional se:
• q ´e encontrado por blast de p contra Q com e-value menor ou igual a 10
−5
; e
• p ´e encontrado por bla st de q contra P com e-value menor ou igual a 10
−5
.
O peso de uma aresta (p, q) ´e obtido p ela cobertura m´edia do alinhamento das seq¨uˆencias
p e q retornada pelo relat´orio do blast. A cobertura m´edia de alinhamento foi utilizada
pois acredita-se que essa medida possa evitar que uma aresta entre dois genes compartilhe
apenas pequenos “peda¸cos” das seq¨uˆencias (dom´ınios esp´urios [19]).
Para determinar um valor adequado para T
t
e T
e
, foi utilizado o banco de dados Pfam [11]
como referˆencia comparativa. Pfam foi escolhido pois utiliza Hidden Markov Models para
detectar caracter´ısticas de fam´ılias de prote´ınas de uma dada seq¨uˆencia proteica. Espera-
se que seq¨uˆencias de um mesmo triˆangulo perten¸cam a uma mesma fam´ılia Pfam.
Os testes realizados em [41] mostraram que o valor 50 ´e adequado para ambos os limites T
t
e T
e
, pois foi observado um n´umero constante de triˆangulos e arestas para uma cobe rtura
de alinhamento abaixo de 50%. A metodologia aparentemente previne que hits contendo
baixa similaridade fa¸cam parte dos triˆangulos, o que melhora o n´umero de ort´ologos
detectados corretamente entre as esp´ecies comparadas.
5.4 Alguns resultados
A metodologia permitiu a compara¸c˜ao e extra¸c˜ao de informa¸c˜oes entre genomas pat´ogenos
e n˜ao-pat´ogenos. Os triˆangulos entre os genomas comparados sugerem que esses genes
est˜ao envolvidos no metabolismo central dos genomas, considerando esse conjunto de
genes indispens´aveis para fungos. Outras inferˆencias biol´ogicas podem ser vistas em [41].
Como um outro resultado, essa metodologia surge como um framework, no sentido de
que alguns valores e limites n˜ao foram especificados, permitindo que o m´etodo possa ser
especializado dependendo da necessidade, tal como o poder de processamento, tamanho
do genomas, e sensibilidade.
A compara¸c˜ao de todos os genomas de fungos n˜ao-pat´ogenos com os genomas C.neofor-
mans e C.albicans gerou os cinco diagramas de Venn da Figura 5.4 abaixo.
46
Figura 5.4: Diagramas de Venn gerados pela compara¸c˜ao entre dois genomas de fungos
pat´ogenos e cinco genomas de fungos n˜ao-pat´ogenos, comparados de trˆes em trˆes simul-
taneamente.
Para apresentarmos os resultados obtidos, desenvolvemos dois scripts em Perl. O script
intitulado venn.pl gera uma figura de diagrama de Venn preenchida com os valores das
intersec¸c˜oes, com os nomes dos organismos e m compara¸c˜ao e com o n´umero de genes de
cada organismo. O segundo script, vennWeb.pl, gera uma p´agina html com a figura
do diagrama de Venn, anteriormente gerada, com links na figura para arquivos textos
referentes `as regi˜oes do diagrama de Venn que s˜ao compartilhadas entre dois genomas,
entre os trˆes genomas e para as regi˜oes exclusivas de cada genoma.
47
Cap´ıtulo 6
Considera¸c˜oes finais
O presente trabalho teve como principal objetivo a reformula¸c˜ao do pacote de ferramentas
egg [1]. A reformula¸c˜ao incluiu a reimplementa¸c˜ao de todo o c´odigo-fonte, al´em da
descri¸c˜ao e implementa¸c˜ao de novas metodologias e funcionalidades.
As principais contribui¸c˜oes do trabalho foram:
• total reformula¸c˜ao do c´odigo-fonte dos programas contidos na ferramenta egg;
• implementa¸c˜ao de metodologia para encontrar regi˜oes espec´ıficas – essa metodologia
foi proposta em [1] mas n˜ao havia sido implementada;
• desenvolvimento e implementa¸c˜ao de nova metodologia para encontrar genes par´alogos
(genes hom´ologos pertencentes ao mesmo organismo);
• desenvolvimento e implementa¸c˜ao de uma vers˜ao de egg, denominada egg-lite,
para a c ompara¸c˜ao de genomas incompletos, onde se tem apenas genes, ou trans-
critos do organismo, sem o seq¨uenciamento completo dos cromossomos;
• desenvolvimento e implementa¸c˜ao de um m´odulo para a compara¸c˜ao de trˆes prote-
omas.
Ap´os essa reformula¸c˜ao, os c´odigos-fonte de egg, al´em de manuais e documenta¸c˜ao se
encontram dispon´ıveis para download em http://egg.dct.ufms.br/egg.
A aplica¸c˜ao das novas metodologias inseridas em egg foram utilizadas em trabalhos de
pesquisa e resultaram na co-autoria das publica¸c˜oes [5, 41] e do artigo em prepara¸c˜ao [47].
Al´em disso, a experiˆencia adquirida durante o programa permitiu ainda a co-autoria
de [43, 44].
Trabalhos futuros
Muitas altera¸c˜oes podem ser realizadas no presente trabalho para melhorar o pacote de
ferramentas egg, suas metodologias e o detalhamento dos seus resultados. A seguir,
listamos algumas das possibilidades.
48
Interface gr´afica
Os arquivos de sa´ıda do pacote de programa egg est˜ao em formato texto, a menos dos
arquivos de plotagem cbbh.pdf e hbbh.pdf. Maiores detalhes desses arquivos est˜ao no
apˆendice A. Embora os arquivos de sa´ıda possam ser processados/analisados, muitas
vezes s˜ao dif´ıceis de serem amplamente analisados. Dessa forma, uma interface gr´afica
que centralizasse as informa¸c˜oes dos arquivos textos seria muito ´util.
Portanto, poder´ıamos criar uma ferramenta que utilizasse informa¸c˜oes de ortologia en-
tre prote´ınas ilustrando as intera¸c˜oes entre as prote´ınas e entre as regi˜oes em que est˜ao
localizadas. A id´eia consiste em ilustrar graficamente as regi˜oes ort´ologas e as regi˜oes
espec´ıficas, permitindo a visualiza¸c˜ao das rela¸c˜oes com perspectivas para escalas me no-
res, com zoom’s, de forma similar a utilizada pela ferramenta string [50], utilizando
informa¸c˜oes origin´arias dos RUNs, ROs e REs, ao inv´es das informa¸c˜oes de COG, utili-
zadas pela ferramenta string [50].
Sintonia-fina para determinar par´alogos
Muitas altera¸c˜oes podem ser feitas em nossa metodologia para determinar genes par´alogos.
Primeiro, podemos melhorar o algoritmo para encontrar as JMCs, por exemplo, atribuindo
pesos ou pontua¸c˜oes `as arestas do grafo. Podemos tamb´em tentar evitar o caso de que duas
ou mais fam´ılias compartilhem uma mesma prote´ına, decidindo que uma prote´ına deva
participar da fam´ılia com a qual mais se identifique [1]. Um outro trabalho futuro est´a
relacionado com a qualidade dos alinhamentos. Nesse caso podemos ajustar os parˆametros
do programa hmmbuild para melhorar a qualidade dos pHMMs resultantes. Precisamos
tamb´em encontrar valores mais adequados para todos os parˆametros utilizados em nossa
metodologia, pois os valores que utilizamos foram baseados em testes preliminares.
Agrupamento na compara¸c˜ao entre 3 genomas
Ao compararmos trˆes genomas, sugerimos como um outro trabalho futuro, a imple-
menta¸c˜ao de um passo pr´evio de clusteriza¸c˜ao (agrupamento) dos trˆes genomas. Nesse
caso, esse passo adicional na metodologia poderia ajudar a evitar os casos complexos
envolvendo os genes par´alogos, descritos na Se¸c˜ao 5.1. Poder´ıamos tamb´em aplicar a
metodologia de encontrar regi˜oes espec´ıficas, descrita na Se¸c˜ao 3.1.2, aos pares de geno-
mas, para tentar determinar as poss´ıveis regi˜oes espec´ıficas em cada genoma, tentando
descobrir metabolismos secund´arios de cada organismo.
49
Apˆendice A
Detalhes operacionais de egg
A nova proposta de implementa¸c˜ao para a metodologia descrita na Se¸c˜ao 3.2 resultou nos
programas egg e egg-lite. Nas se¸c˜oes seguintes descreveremos alguns detalhes sobre
esses programas.
A.1 Descri¸c˜ao das Ferramentas
Os programas e scripts pertencentes aos pacotes de egg e egg-lite foram escritos nas
linguagens C++ e Perl. Os programas escritos em C++ utilizaram o compilador g++ (GNU
Software).
Conforme descrito na Se¸c˜ao 3.2.1, o programa egg cont´em trˆes fases (compara¸c˜ao de ge-
nes, determina¸c˜ao do grafo bipartido e determina¸c˜ao das estruturas organizacionais). No
entanto, a implementa¸c˜ao de egg foi dividida em dois m´odulos. No primeiro m´odulo im-
plementamos a compara¸c˜ao entre as seq¨uˆencias na forma todas-contra-todas, e no segundo
m´odulo implementamos a “constru¸c˜ao” do grafo bipartido e a determina¸c˜ao das estrutu-
ras organizacionais, como descrito na Se¸c˜ao 3.2.1. Os m´odulos de egg s˜ao executados
separadamente.
O programa egg-lite, conforme descrito em 3.3, cont´em apenas as duas fases iniciais de
egg. A implementa¸c˜ao dessas fases foram realizadas em dois m´odulos, conforme egg.
No entanto, os m´odulos de egg-lite s˜ao executados em apenas um passo. Na se¸c˜oes
seguintes abordaremos maiores detalhes sobre cada programa.
EGG
A f erramenta egg possui como entrada dois arquivos com os conjuntos de seq¨uˆencias
dos genes ou prote´ınas dos genomas G e H. egg sup˜oe a existˆencia de dois arquivos
com extens˜oes ptt, que trazem informa¸c˜oes sobre os genes dos genomas. As informa¸c˜oes
contidas nesses arquivos s˜ao as coordenadas de in´ıcio e fim, a fita, tamanho do gene, nome,
produto, c´odigo identificador no GenBank (gi) e n´umero COG.
Al´em dos arquivos com extens˜ao ptt, egg sup˜oe que existam tamb´em dois arquivos
com extens˜oes faa que contˆem as seq¨uˆencias no formato FASTA, de todos os genes dos
50
genomas. Ambos os tipos de arquivos est˜ao dispon´ıveis no NCBI [49] para genomas
publicados.
Conforme descrito na Se¸c˜ao 3.2.1, egg compara cada gene de um genoma contra todos os
genes do outro genoma, e vice-versa, utilizando a ferramenta blast. Essas compara¸c˜oes
s˜ao realizadas primeiramente c onstruindo as bases de seq¨uˆencias de genes para cada ge-
noma. Utilizamos o programa formatdb, que ´e uma ferramenta dispon´ıvel pelo pacote
do blast, para construir as bases de seq¨uˆencias. Ap´os construir essas bases para cada
genoma, o programa egg pode ser executado.
O pacote egg cont´em dois m´odulos. O primeiro m´odulo, denominado de egg-parser,
busca informa¸c˜oes, geradas pelo blast, sobre as compara¸c˜oes entre as seq¨uˆencias per-
tencentes aos arquivos de extens˜oes faa e gera arquivos de sa´ıda contendo informa¸c˜oes
necess´arias para o segundo m´odulo. Supondo que o nome dos genomas em compara¸c˜ao
s˜ao gG e gH, os seguintes arquivos de entrada s˜ao necess´arios:
• gG.ptt e gH.ptt; e
• gG.faa e gH.faa.
Os arquivos de sa´ıda gerados por egg-parser possuem os seus nomes compostos pelos
nomes dos arquivos de entrada de extens˜ao ptt. Assim, ter´ıamos os seguintes arquivos
de sa´ıda e suas descri¸c˜oes:
• gGgH.12 - Para cada gene do genoma gG, cont´em as informa¸c˜oes sobre a quantidade
de hits encontrados; e para cada hit, o n´umero seq¨ue ncial do hit, o seu gi, score,
e-value e as porcentagens de cobertura de alinhamento entre o gene e o hit;
• gGgH.21 - Para cada gene do genoma gH, cont´em as informa¸c˜oes sobre a quantidade
de hits encontrados; e para cada hit, o n´umero seq¨ue ncial do hit, o seu gi, score,
e-value e as porcentagens de cobertura de alinhamento entre o gene e o hit;
• gGgH.1 - Cont´em as mesmas informa¸c˜oes do arquivo gG.ptt, por´em em um formato
mais facilmente parse´avel; e
• gGgH.2 - Cont´em as mesmas informa¸c˜oes do arquivo gH.ptt, por´em em um formato
mais facilmente parse´avel.
Na Se¸c˜ao A.2 apresentamos alumas figuras ilustrando trechos dos arquivos de sa´ıda de
egg-parser.
egg-parser cont´em um conjunto de parˆametros que permitem ao usu´ario executar e
alterar valores de alguns dos parˆamtros de entrada do blast. A descri¸c˜ao da lista de
parˆametros pode ser vista na documenta¸c˜ao do programa, encontrada em [48].
O objetivo da cria¸c˜ao dos arquivos de sa´ıda ´e permitir que possam ser facilmente utilizados
por outros programas que necessitem dessas informa¸c˜oes.
A implementa¸c˜ao desse m´odulo foi escrita em Perl, devida a flexibilidade da sua lingua-
gem para a extra¸c˜ao de informa¸c˜oes de documentos textos, utilizando express˜oes regulares.
51
O segundo m´odulo, denominado simplesmente de egg, conforme descrito em 3.2.1, “cons-
tr´oi” um grafo bipartido e encontra as estruturas organizacionais nesse grafo. egg utiliza
como parˆametros de entrada os arquivos de extens˜ao ptt e os arquivos gerados por egg-
parser. Supondo novamente que os nomes dos arquivos com extens˜ao ptt s˜ao gG e gH,
egg necessita dos seguintes arquivos:
• gG.ptt e gH.ptt;
• gGgH.1 e gGgH.2; e
• gGgH.12 e gGgH.21
Os nomes dos arquivos de sa´ıda s˜ao compostos pelos nomes dos arquivos de extens˜ao ptt.
Assim ter´ıamos os seguintes arquivos de sa´ıda e suas funcionalidades:
• gGgH.bbh - Informa¸c˜oes sobre os genes que fizeram BBH. Esse arquivo foi utilizado
em [10] como instrumentos para a obten¸c˜ao de medidas de distˆancias entre genomas
em compara¸c˜ao.
• gGgH.bkb - Informa¸c˜oes sobre a espinha dorsal entre gG e gH;
• gHgG.bkb - Informa¸c˜oes sobre a espinha dorsal entre gH e gG;
• gGgH.exc - Informa¸c˜oes sobre os genes exclusivos de cada genoma;
• gGgH.hyp - Informa¸c˜oes sobre os genes com produtos hip ot´eticos;
• gGgH.k12 - Informa¸c˜oes para cada gene do genoma gG, se o gene possui hits, o valor
de e-value do melhor hit e em quais regi˜oes o hit aparece;
• gGgH.k21 - Informa¸c˜oes para cada gene do genoma gH, se o gene possui hits, o valor
de e-value do melhor hit e em quais regi˜oes o hit aparece;
• gGgH.mul - Informa¸c˜oes simplificadas de cada regi˜ao ort´ologa. Esse arquivo foi
utilizado em [25] para a compara¸c˜ao de m´ultiplos genomas;
• gGgH.reg - Informa¸c˜oes mais detalhadas de cada regi˜ao ort´ologa;
• gGgH.rns - Informa¸c˜oes sobre os runs entre os genomas;
• gGgH.sre - Informa¸c˜oes sobre as regi˜oes espec´ıficas do genoma gG;
• gHgG.sre - Informa¸c˜oes sobre as regi˜oes espec´ıficas do genoma gH;
• cbbh.pdf - Gr´afico ilustrando os BBHs; e
• hbbh.pdf - Gr´afico ilustrando as ROs;
O programa egg cont´em um conjunto de parˆametros que possibilitam especificar: o
n´umero m´ınimo de ORFs dentro de uma regi˜ao espec´ıfica, o n´umero m´ınimo de matches
dentro de um RUN, os valores de e-value para a defini¸c˜ao de um match, porcentagem
m´ınima de cobertura de alinhamento entre as seq¨uˆencias comparadas, tamanho dos ge-
nomas, etc. A lista completa dos parˆametros pode ser enc ontrada no endere¸co eletrˆonico:
http://egg.dct.ufms.br/egg/
52
EGG-LITE
A ferramenta necessita como parˆametros de entrada os dois arquivos de extens˜ao faa,
que cont´em as seq¨uˆencias no formato FASTA.
Descrevemos na Se¸c˜ao 3.3 que egg-lite compara uma seq¨uˆencia de um conjunto A de
seq¨uˆencias, contra todas as seq¨uˆencias de um conjunto B e vice-versa. Conforme egg,
egg-lite utiliza o blast como ferramenta comparativa e o programa formatdb para
criar as bases de seq¨uˆencias.
O pacote egg-lite ´e composto por dois m´odulos. O primeiro m´odulo, denominado
simplesmente de egg-lite, ´e respons´avel por definir as rela¸c˜oes de match e BBH entre
os conjuntos de seq¨uˆencias utilizando como parˆametros de entrada os arquivos de sa´ıda
do segundo m´odulo. O segundo m´odulo, denominado de egg-parser-lite, executa
as compara¸c˜oes das seq¨uˆencias dos conjuntos na forma todas-contra-todas, utilizando o
blast e criando como sa´ıda, arquivos contendo as seq¨uˆencias de um conjunto e suas
seq¨uˆencias hits do outro conjunto.
Conforme descrito na Se¸c˜ao 3.3, egg-lite n˜ao constr´oi as estruturas organizacionais
entre os conjuntos de seq¨uˆencias, pois poder´ıamos estar comparando um genoma contra
um conjunto de seq¨uˆencias de um outro genoma ainda n˜ao completamente seq¨uenciado
(ESTs). Supondo que os nomes dos conjuntos de seq¨uˆencias s˜ao sG e sH, egg-lite gera
os seguintes arquivos de sa´ıda:
• sGsH.bbh - Informa¸c˜oes sobre as seq¨uˆencias que fizeram BBH;
• sGsH.exc - Informa¸c˜oes sobre as seq¨uˆencias que s˜ao exclusivas em cada conjunto; e
• sGsH.match - Informa¸c˜oes sobre as seq¨uˆencias que fizeram match;
Assim como em egg, egg-lite possui um conjunto de parˆametros que permitem a
execu¸c˜ao do programa blast e a altera¸c˜ao dos valores de alguns parˆametros do blast,
para a sua execu¸c˜ao. A lista de parˆametros de egg-lite pode ser obtida em [48].
O programa egg-lite foi escrito em C++ e o script egg-parser-lite foi escrito em Perl.
Algumas figuras contendo trechos dos arquivos de sa´ıda de egg-lite podem ser vistas
em 3.11, 3.12 e 3.13.
Os pacotes egg, egg-lite, e uma documenta¸c˜ao dos programas e scripts contidos nesses
pacotes podem ser obtidos no endere¸co eletrˆonico: http://egg.dct.ufms.br/egg/
53
A.2 Exemplos de alguns arquivos de sa´ıda
As figuras A.1 e A.2 ilustram um trecho dos arquivos xacxcc.12 e xacxcc.1 resultantes
da compara¸c˜ao dos genomas Xanthomonas axonopodis pv. citri str. 306 (xac) e Xantho-
monas campestris pv. campestris str. ATCC 33913 (xcc).
#1 21240775 2
> 1 21229479 860 0.0 100 100
> 2739 21232217 46 4e-06 49 87
#2 21240776 1
> 2 21229480 676 0.0 100 100
#3 21240777 1
> 3 21229481 655 0.0 98 98
#4 21240778 2
> 4 21229482 1545 0.0 100 100
> 1670 21231148 362 1e-101 73 93
#5 21240779 1
> 5 21229483 382 1e-107 100 81
#6 21240780 2
> 6 21229484 509 1e-146 100 100
> 955 21230433 83 2e-17 60 31
#7 21240781 1
> 7 21229485 714 0.0 100 100
Figura A.1: Trecho do arquivo xacxcc.12. Cada gene do genoma xac ´e marcado com #,
seguido pelo seu n´umero seq¨uencial no genoma xac, de acordo com seu arquivo de extens˜ao
ptt, pelo seu gi e pela quantidade de hits. Cada hit ´e marcado com o s´ımbolo >, seguido
pelo seu n´umero sequencial no genoma xcc, pelo seu gi, score, e-value, porcentagens de
cobertura de alinhamento entre o gene e o hit.
4312
21240775 42 1370 + dnaA XAC0001 chromosomal replication initiator
21240776 1647 2747 + dnaN XAC0002 DNA polymerase III beta chain
21240777 3799 4905 + recF XAC0003 DNA replication and repair RecF protein
21240778 5020 7464 + gyrB XAC0004 DNA gyrase subunit B
21240779 7685 8368 + - XAC0005 hypothetical protein
21240780 8552 9358 + - XAC0006 hypothetical protein
21240781 9636 10829 + - XAC0007 hypothetical protein
21240782 10983 11654 + tonB XAC0008 TonB protein
21240783 11740 12501 + exbB XAC0009 biopolymer transport ExbB protein
21240784 12548 12970 + exbD1 XAC0010 biopolymer transport ExbD1 protein
21240785 12974 13387 + exbD2 XAC0011 biopolymer transport ExbD2 protein
21240786 13649 14416 - pdxJ XAC0012 pyridoxal phosphate biosynthetic protein
21240787 14424 14756 - - XAC0013 hypothet ical protein
21240788 14768 16228 - cls XAC0014 cardiolipin synthetase
21240789 16671 17330 + - XAC0015 hypothet ical protein
21240790 17330 17920 + - XAC0016 hypothet ical protein
21240791 18131 19258 - - XAC0017 hypothet ical protein
21240792 19442 20359 - - XAC0018 hypothet ical protein
21240793 20413 21753 - ompP1 XAC0019 outer membrane protein
Figura A.2: Trecho do arquivo xacxcc.1 . Na primeira linha do arquivo temos a quan-
tidade de orfs encontradas no arquivo xac.ptt. Em cada linha subseq¨uente, temos in-
forma¸c˜oes das orfs, como: gi, coordenada de in´ıcio e fim no genoma, fita, nome, sinˆonimo,
e produto, separados por espa¸cos em branco.
54
A Figura A.3 mostra um trecho do arquivo de sa´ıda de extens˜ao bbh resultante da
compara¸c˜ao entre os genomas das Alphaproteobacterias Agrobacterium tumefaciens str.
C58 (at) e Sinorhizobium meliloti 1021 (sm).
################################
ATSM - bidirectional best hits
################################
===========================================================================================================
Gene Synonym gi start..end size product
===========================================================================================================
+_ Atu0001 17933926 203..1024 273aa hypothetical protein
+_ SMc02793 15963754 478..1299 273aa hypothetical protein
------------------------------------
+maf Atu0002 17933927 1056..1655 199aa Maf like protein
+maf SMc02792 15963755 1347..1946 199aa Maf like protein
------------------------------------
+aroE Atu0003 17933928 1648..2508 286aa shikimate 5 dehydrogenase
+aroE SMc02791 15963756 1939..2799 286aa shikimate 5 dehydrogenase
------------------------------------
+coaE Atu0004 17933929 2505..3089 194aa dephospho CoA kinase
+coaE SMc02790 15963757 2796..3380 194aa dephospho CoA kinase
------------------------------------
+dnaQ Atu0005 17933930 3110..3808 232aa DNA polymerase III subunit epsilon
+dnaQ SMc02789 15963758 3574..4302 242aa DNA polym eras e III subunit epsilon
------------------------------------
-secB Atu0006 17933931 3907..4389 160aa export protein SecB
-secB SMc02788 15963759 4408..4914 168aa export pr otei n SecB
------------------------------------
-fxsA Atu0007 17933932 4493..5029 178aa hypothetical protein
-_ SMc02787 15963760 5082..5657 191aa hypothetical protein
------------------------------------
+_ Atu0008 17933933 5215..5868 217aa hypothetical protein
+_ SMc02786 15963761 5792..6493 233aa PUTATIVE TRANSLOCASE TRANSMEMBRANE PROTEIN
------------------------------------
+mltA Atu0009 17933934 5865..6977 370aa membrane bound lytic murein transglycosylase
+_ SMc02785 15963762 6511..7629 372aa PUTATIVE LYTIC MUREIN TRANSGLYCOSYLASE A PROTEIN
------------------------------------
+_ Atu0010 17933935 6974..7543 189aa hypothetical protein
+_ SMc02784 15963763 7622..8188 188aa hypothetical protein
------------------------------------
Figura A.3: Trecho do arquivo atsm.bbh. As colunas informam da esquerda para a direita,
a fita, o nome do gene; o sinˆonimo do gene; o identificador no GenBank; as coordenadas
de DNA; o tamanho do gene e o nome do produto.
55
A Figura A.4 mostra um trecho do arquivo xacxcc.bkb resultante da compara¸c˜ao entre
Xanthomonas axonopodis pv. citri str. 306 (xac)e Xanthomonas campestris pv. campes-
tris str. ATCC 33913 (xcc).
===========================================================================================================================================
PRODUCT START..END GENE(STRAND) (STRAND)GENE START..END PRODUCT
===========================================================================================================================================
chromosomal replication initiator 42..1370 XAC0001 (+) <<<>>> (+) XCC0001 42..1370 chromosomal replication initiator
DNA polymerase III beta chai 1647..2747 XAC0002 (+) <<<>>> (+) XCC0002 1646..2746 DNA polymerase III beta chain
DNA replication and repair RecF 3799..4905 XAC0003 (+) <<<>>> (+) XCC0003 3633..4739 DNA replication and repair RecF protein
DNA gyrase subunit 5020..7464 XAC0004 (+) <<<>>> (+) XCC0004 4853..7297 DNA gyrase subunit B
hypothetical protein 7685..8368 XAC0005 (+) <<<>>> (+) XCC0005 7359..8201 hypothetical protein
hypothetical protein 8552..9358 XAC0006 (+) <<<>>> (+) XCC0006 8264..9070 hypothetical protein
hypothetical protein 9636..10829 XAC0007 (+) <<<>>> (+) XCC0007 9209..10405 hypothetical protein
TonB protein 10983..11654 XAC0008 (+) <<<>>> (+) XCC0008 10559..11230 TonB protein
biopolymer transport ExbB protein 11740..12501 XAC0009 (+) <<<>>> (+) XCC0009 11315..12076 biopo lymer transport ExbB protein
biopolymer transport ExbD1 protein 12548..12970 XAC0010 (+) <<<>>> (+) XCC0010 12123..12545 biop olyme r transport ExbD1 protein
biopolymer transport ExbD2 protein 12974..13387 XAC0011 (+) <<<>>> (+) XCC0011 12549..12959 biop olyme r transport ExbD2 protein
pyridoxal phosphate biosynthetic 13649..14416 XAC0012 (-) <<<>>> (-) XCC0012 14113..14883 pyridoxal phosphate biosyn
hypothetical protein 14424..14756 XAC0013 (-) <<<>>> (-) XCC0013 14891..15160 hypothetical protein
cardiolipin synthetas 14768..16228 XAC0014 (-) <<<>>> (-) XCC0014 15235..16695 cardiolipin synthetase
hypothetical protein 16671..17330 XAC0015 (+) # -
hypothetical protein 17330..17920 XAC0016 (+) # -
hypothetical protein 18131..19258 XAC0017 (-) <<<>>> (+) XCC0015 16981..18075 hypothetical protein
hypothetical protein 19442..20359 XAC0018 (-) <<<>>> (-) XCC0016 18170..18940 hypothetical protein
outer_membrane protein 20413..21753 XAC0019 (-) <<<>>> (-) XCC0017 19513..20853 outer membrane protein
hypothetical protein 21972..22664 XAC0020 (+) <<<>>> (+) XCC0018 21074..21766 hypothetical protein
Figura A.4: Exemplo de uma espinha dorsal entre os genomas dos organismos Xantho-
monas axonopodis pv. citri str. 306 (Xac) e Xanthomonas campestris pv. campestris str.
ATCC 33913 (Xcc). Cada s´ımbolo <<<>>> mostra um BBH pertencente a espinha dorsal.
O s´ımbolo # indica que o gene ´e espec´ıfico; o s´ımbolo * indica que o gene fez hit, mas
n˜ao fez BBH. Quando um gene aparece sem “casamento” e sem qualquer s´ımbolo, temos
uma transloca¸c˜ao, ou se ja, ele fez BBH, mas esse BBH n˜ao ficou aparente porque est´a
cruzando com outros, e esses outros n˜ao foram mostrados pela programa¸c˜ao dinˆamica.
56
A Figura A.5 mostra um trecho do arquivo de sa´ıda de extens˜ao exc resultante da com-
para¸c˜ao entre os genomas das Alphaproteobacterias Agrobacterium tumefaciens str. C58
(at) e Mesorhizobium loti MAFF303099 (ml).
##############################
AT genes with no hits in ML
##############################
==============================================================================================
Gene Synonym gi st art. .end size product
==============================================================================================
-_ Atu0013 17933938 10604..11206 200aa NAD(P)H flavin oxidoreductase
-_ Atu0028 17933953 31670..31831 53aa hypothetical protein
+_ Atu0042 17933967 43469..43774 101aa hypothetical protein
-_ Atu0056 17933978 59238..59627 129aa hypothetical protein
+_ Atu0058 17933979 62235..62492 85aa hypothetical protein
+_ Atu0067 17933986 70385..70729 114aa hypothetical protein
+nrdH Atu0068 17933987 70923..71174 83aa glutaredoxin rotein
+nrdI Atu0069 17933988 71188..71586 132aa hypothetical rotein
+nrdF Atu0071 17933990 73777..74751 324aa ribonucleotide diphosphate reductase b eta subunit
-_ Atu0076 17933995 78443..79132 229aa hypothetical protein
+_ Atu0083 17934002 86610..86831 73aa hypothetical protein
+_ Atu0094 17934013 98397..99086 229aa hypothetical protein
-_ Atu0105 17934024 109363..109557 64aa hypothetical protein
+_ Atu0107 17934026 110062..110223 53aa hypothetical protein
+_ Atu0115 17934034 120729..120932 67aa hypothetical protein
+_ Atu0116 17934035 121502..121912 136aa hypothetical protein
+_ Atu0117 17934036 122012..122473 153aa hypothetical protein
+_ Atu0118 17934037 122483..123988 501aa hypothetical protein
+_ Atu0144 17934062 148441..148662 73aa hypothetical protein
Figura A.5: Trecho do arquivo atml.exc. As colunas informam da esquerda para a direita,
a identifica¸c˜ao do gene; o sinˆonimo do gene; o identificador no GenBank; as coordenadas
de DNA; o tamanho do gene e o nome do produto.
57
A Figura A.6 mostra um trecho do arquivo de sa´ıda de extens˜ao k12 resultante da com-
para¸c˜ao entre os genomas das Alphaproteobacterias Agrobacterium tumefaciens str. C58
(at) e Sinorhizobium meliloti 1021 (sm).
Gene Synonym start product best hit e-value [regions]
================================================================================================
- Atu0001 203 hypothetical p rote in 1e-118 [1 ]
maf Atu0002 1056 Maf like protein 1e-66 [1 ]
aroE Atu0003 1648 shikimate 5 dehydrogenase 1e-112 [1 ]
coaE Atu0004 2505 dephospho CoA kinase 2e-58 [1 ]
dnaQ Atu0005 3110 DNA polymerase III subunit epsilon 3e-88 [1 ]
secB Atu0006 3907 export protein SecB 2e-69 [1 ]
fxsA Atu0007 4493 hypothetical protein 2e-28 [1 ]
- Atu0008 5215 hypothetical protein 1e-88 [1 ]
mltA Atu0009 5865 membrane bound lytic murein transglycosy 1e-131 [1 ]
- Atu0010 6974 hypothetical protein 2e-53 [1 ]
- Atu0011 7540 transcriptional regulator 2e-45 [1 ]
gyrB Atu0012 8049 DNA gyrase subunit B 0 [1 ]
- Atu0013 10604 NAD(P)H flavin oxidoreductase 6e-61 [1 ]
hpcE Atu0014 11335 2 hydroxyhepta 2,4 diene 1,7 dioate isom 1e-26 [isolated]
depA Atu0015 12279 intracellular PHB depolymerase 0 [2 ]
- Atu0016 13605 hypothetical protein 5e-90 [2 ]
trpF Atu0017 14475 N (5 phosphoribosyl)anthranilate isomer 3e-85 [2 ]
trpB Atu0018 15139 tryptophan synthase subunit beta 0 [2 ]
trpA Atu0019 16376 tryptophan synthase subunit alpha 1e-125 [2 ]
accD Atu0020 17231 acetyl CoA carboxylase beta subunit 1e-144 [2 ]
folC Atu0021 18214 folylpolyglutamate synthase 0 [2 ]
trxA Atu0022 19641 thioredoxin C 1 6e-52 [2 ]
uvrD Atu0023 20039 ATP dependant DNA helicase 0 [2 ]
- Atu0024 23586 hypothetical protein 0 [2 ]
- Atu0025 26768 hypothetical protein 1e-95 [2 ]
- Atu0026 27520 hypothetical protein 1e-164 [2 ]
- Atu0027 29028 two component sensor kinase 0 [2 ]
- Atu0028 31670 hypothetical protein ===> NO HITS
ahcY Atu0029 31882 S adenosyl L homocysteine hydrolase 0 [2 ]
ptsH Atu0030 33411 phosphocarrier protein HPr 2e-33 [2 ]
- Atu0031 33698 PTS system, IIA component 3e-63 [2 ]
- Atu0032 34225 hypothetical protein 1e-28 [2 ]
Figura A.6: Trecho do arquivo atsm.k12 resultante da compara¸c˜ao entre Agrobacterium
tumefaciens str. C58 e Sinorhizobium meliloti 1021. As colunas informam da esquerda
para a direita o nome do gene; seu sinˆonimo; a coordenada de in´ıcio; o nome do produto;
o e-value do melhor hit, se o gene possuir hits; e as regi˜oes ort´ologas das quais o gene faz
parte.
58
A Figura A.7 mostra um trecho do arquivo de sa´ıda de extens˜ao mul resultante da com-
para¸c˜ao entre os genomas Xanthomonas axonopodis pv. citri str. 306 (xac) e Xanthomo-
nas campestris pv. campestris str. ATCC 33913 (xcc).
XAC 4312
XCC 4181
117
XACXCC20060502-1-Rc
1 36
1 36
42
36 36 1
35 34 1
34 33 1
33 32 1
32 31 1
31 29 1
30 28 1
30 27 0
30 26 0
29 28 0
29 27 1
29 26 0
28 28 0
28 27 0
28 26 1
27 25 1
26 24 1
25 23 1
24 22 1
Figura A.7: Trecho do arquivo xacxcc.mul resultante da compara¸c˜ao entre Xanthomonas
axonopodis pv. citri str. 306 e Xanthomonas campestris pv. campestris str. ATCC 33913.
Nas duas primerias linhas do arquivo temos o prefixo do nome dos genomas em c ompara¸c˜ao
e a quantidade de orfs em cada genoma. Na linha seguinte temos a quantidade de ROs
no arquivo. Para cada RO temos o c´odigo da regi˜ao; os genes de in´ıcio e fim da regi˜ao
em cada genoma; o n´umero de matches encontrados nessa regi˜ao e os matches em cada
linha. Cada linha c ontendo os matches informam da esquerda para a direita, o gene do
primeiro genoma; o gene do segundo genoma e se o match ´e um BBH.
59
A Figura A.8 mostra um trecho do arquivo de sa´ıda de extens˜ao reg resultante da com-
para¸c˜ao entre os genomas Xanthomonas axonopodis pv. citri str. 306 e Xanthomonas
campestris pv. campestris str. ATCC 33913.
>XACXCC2006036-55-Rc
4 matches
2kb in XAC - 3kb in XCC
=====================================================================
Gene Synonym (XAC) gi size product
=====================================================================
+_ XAC2122 21242857 274aa dehydrogenase
+_ XAC2123 21242858 217aa hypothetical protein
+_ XAC2124 21242859 200aa hypothetical protein
+gtrB XAC2125 21242860 237aa glycosyl transferase related protein
=====================================================================
Gene Synonym (XCC) gi size product
=====================================================================
-gtrB XCC1643 21231096 239aa glycosyl transferase related protein
-_ XCC1644 21231097 198aa hypothetical protein
-_ XCC1645 21231098 226aa hypothetical protein
-_ XCC1646 21231099 332aa dehydrogenase
=======
matches
=======
===============================================================================================
Gene Synonym start size e-value [ best hit ] product
===============================================================================================
+gtrB XAC2125 2481258 237 1e-58 [best ] glycosyl transferase related protein
-gtrB XCC1643 1918110 239 1e-58 [best ] glycosyl transferase related protein
------------------------------------------
+_ XAC2124 2480704 200 7e-55 [best ] hypothetical protein
-_ XCC1644 1918784 198 7e-55 [best ] hypothetical protein
------------------------------------------
+_ XAC2123 2480054 217 4e-56 [best ] hypothetical protein
-_ XCC1645 1919377 226 5e-56 [best ] hypothetical protein
------------------------------------------
+_ XAC2122 2479137 274 8e-64 [best ] dehydrogenase
-_ XCC1646 1920126 332 1e-63 [best ] dehydrogenase
------------------------------------------
Figura A.8: RO resultante da compara¸c˜ao entre os genomas dos organismos Xanthomonas
axonopodis pv. citri str. 306 (Xac) e Xanthomonas campestris pv. campestris str. ATCC
33913 (Xcc) Na primeira linha do arquivo temos o c´odigo do RO; na linha seguinte temos
o n´umero de matches na RO; em seguida temos o tamanho aproximado (em n´umero de
bases) da RO em cada genoma. Para cada genoma, ´e mostrada uma linha contendo os
genes que participam da RO. Em seguida cada par participante da RO ´e exibido. As
colunas informam da esquerda para a direita, a fita e o nome do gene; o sinˆonimo do
gene; a coordenada de in´ıcio; o tamanho; o e-value do melhor hit; a palavra “best” na
linha de cima do par indica que o gene de cima encontrou o gene de baixo do par como
melhor hit, acontecendo o mesmo para a palavra “best” na linha de baixo do par; Em
seguida temos o nome do produto do gene.
60
A Figura A.9 mostra um trecho do arquivo de sa´ıda de extens˜ao rns resultante da com-
para¸c˜ao entre os genomas das Alphaproteobacterias Sinorhizobium meliloti 1021 (sm) e
Mesorhizobium loti MAFF303099 (ml).
>SMML20060527-222-Pc
# of matches: 4
2kb in SM - 2kb in ML
===============================================================================================
Gene |Synonym start s ize e-value [ best hit ] product
===============================================================================================
-rpsI |SMc01803 1350279 155 7e-64 [best ] 30S ribosomal protein S9
-_ |mll8456 6948034 160 4e-64 [best ] 30S ribosomal protein S9
------------------------------------------
-rplM |SMc01804 1350749 154 3e-74 [best ] 50S ribosomal protein L13
-_ |mll8458 6948518 154 1e-74 [best ] 50S ribosomal protein L13
------------------------------------------
-_ |SMc01805 1351432 143 2e-35 [best ] hypothetical protein
-_ |mll8460 6949197 154 1e-35 [best ] hypothetical protein
------------------------------------------
+_ |SMc01806 1352032 273 1e-97 [best ] enoyl CoA hydratase
+_ |mlr8461 6949816 273 6e-98 [best ] enoyl CoA hydratase
------------------------------------------
Figura A.9: Exemplo de um run paralelo consistente entre os genomas dos organismos
Sinorhizobium meliloti 1021 (Sm) e Mesorhizobium loti MAFF303099 (Ml). Na primeira
linha do arquivo temos o c´odigo do run; na linha seguinte temos o n´umero de matches
no run; em seguida temos o tamanho aproximado (em n´umero de bases) do run em cada
genoma. Cada par mostrado ´e um match do run. As colunas informam da esquerda para
a direita, a fita e o nome do gene; o sinˆonimo do gene; a coordenada de in´ıcio; o tamanho;
o e-value do melhor hit; a palavra “best” na linha de cima do par indica que o gene de
cima encontrou o gene de baixo do par como melhor hit, acontecendo o mesmo para a
palavra “best” na linha de baixo do par; Em seguida temos o nome do produto do gene.
61
A Figura A.10 mostra um trecho do arquivo de sa´ıda de extens˜ao sre resultante da
compara¸c˜ao entre os genomas das Alphaproteobacterias Agrobacterium tumefaciens str.
C58 (at) e Sinorhizobium meliloti 1021 (sm).
>Region from 934 to 952
19 orfs
=====================================================================
Gene Synonym start..end product
=====================================================================
# +_ Atu0951 940649..941881 large terminase
# -_ Atu0952 942264..942923 hypothetical protein
# +_ Atu0953 943042..943350 hypothetical protein
# +gp34 Atu0954 943607..944773 phage head portal protein
# +_ Atu0955 944969..945289 hypothetical protein
# +gp35 Atu0956 945339..945911 phage prohead protease
# +gp36 Atu0957 945944..947212 phage phi C31 major capsid gp36 like protein
# -_ Atu0958 947184..948038 hypothetical protein
# +_ Atu0959 948215..948610 hypothetical protein
-_ Atu0960 948618..949724 MFS perme ase
# -_ Atu0961 949983..950693 hypothetical protein
# -_ Atu0962 950881..951285 hypothetical protein
# -_ Atu0963 951278..952276 hypothetical protein
# +_ Atu0964 952262..952900 hypothetical protein
# +_ Atu0965 952897..953781 hypothetical protein
# +_ Atu0966 953778..954212 hypothetical protein
# +_ Atu0967 954230..958030 hypothetical protein
# +_ Atu0968 958065..958271 hypothetical protein
# +_ Atu0969 958346..958645 hypothetical protein
Figura A.10: Regi˜ao espec´ıfica do genoma do organismo Agrobacterium tumefaci ens str.
C58 (At) em rela¸c˜ao ao genoma do organismo Sinorhizobium meliloti 1021 (Sm). Inicial-
mente temos as coordenadas de in´ıcio e fim da RE e na linha seguinte, temos a quantidade
de genes pertencentes a RE. Cada prote´ına predita marcada com # ´e uma prote´ına predita
espec´ıfica.
62
A Figura A.11 mostra o arquivo cbbh.pdf que ilustra graficamente o alinhamento obtido
pelo LCS entre os BBHs dos organismos Xanthomonas axonopodis pv. citri str. 306 e
Xanthomonas campestris pv. campestris str. ATCC 33913.
0
1e+06
2e+06
3e+06
4e+06
5e+06
0 1e+06 2e+06 3e+06 4e+06 5e+06
Xanthomonas campestris pv. campestris str. ATCC 33913
Xanthomonas axonopodis pv. citri str. 306
Best Reciprocs
BBHs orientations
Same
Inversion
Figura A.11: Plotagem do alinhamento obtido pelo LCS entre os BBHs dos genomas dos
organismos Xanthomonas axonopodis pv. citri str. 306 (Xac) e Xanthomonas campestris
pv. campestris str. ATCC 33913. (Xcc)
63
A Figura A.12 mostra o arquivo hbbh.pdf que ilustra graficamente os BBHs entre os
organismos Xanthomonas axonopodis pv. citri str. 306 e Xanthomonas campestris pv.
campestris str. ATCC 33913.
0 1e+06 2e+06 3e+06 4e+06 5e+06
BBHs
Figura A.12: Plotagem dos BBHs entre os genomas dos organismos Xanthomonas axo-
nopodis pv. citri str. 306 (Xac) e Xanthomonas ca mpestris pv. campestris str. ATCC
33913 (Xcc).
64
Apˆendice B
Detalhes operacionais para obter
par´alogos
A nova proposta de metodologia apresentada na Se¸c˜ao 4.1 para tentar determinar as
fam´ılias de genes par´alogos, resultou na implementa¸c˜ao de um conjunto de programas e
scripts pertencentes ao pacote denominado paralogs. Descreveremos nas se¸c˜oes seguin-
tes alguns detalhes dos programas e scripts desse pacote.
B.1 Pacote PARALOGS
O pacote paralogs cont´em um conjunto de programas e scripts que foram escritos na
linguagem C++ e Perl. Os programas escritos em C++ utilizaram o compilador g++ (GNU
software).
Conforme descrito na Se¸c˜ao 4.1, a metodologia consiste de duas fases (Agrupamento de
seq¨uˆencias e Busca hom´ologos). Os programas e scripts do pacote paralogs iniciam
no segundo passo da fase “Agrupamento de seq¨uˆencias”, que consiste em construir um
grafo G e determinar as cliques maximais nesse grafo. O primeiro passo dessa fase ´e
determinado pelo programa egg.
Os programas do pacote paralogs pertencentes a fase “Agrupamento de seq¨uˆencias” e
suas funcionalidades s˜ao descritas a seguir:
• cria arestas - programa que cria arestas de um grafo, a partir do arquivo gGgG.12,
resultante da compara¸c˜ao do genoma gG com ele mesmo. Os v´ertices do grafo s˜ao
os genes do genoma gG, e uma aresta entre os genes v e w existe, se v encon-
trou w como hit e vice-versa, conforme descrito em 4.1.1. O programa cont´em
ainda os parˆametros e-value e cobertura, que s˜ao utilizados para determinar se uma
aresta existe entre dois v´ertices de gG. A sa´ıda ´e um arquivo texto de extens˜ao
grafo original contendo o grafo no formato de lista de adjacˆencias, como entrada
para o programa que encontrar´a as componentes conexas nesse grafo.
• componentes - programa gerador de componentes conexas, a partir do arquivo de
extens˜ao grafo original (sa´ıda de cria arestas). O programa cria o arquivo
65
de extens˜ao comps contendo o grafo original sem os v´ertices de grau zero. Cada
componente ´e criada em um arquivo texto de extens˜ao comp com o nome composto
pelo nome do arquivo de extens˜ao grafo original e com um d´ıgito indicador do
n´umero da componente. A cria¸c˜ao do arquivo comps objetiva a utiliza¸c˜ao dessa
sa´ıda em um outro programa que “lˆe” componentes separadamente.
• cliques - programa que encontra as cliques maximais do subgrafo do grafo original
que representa o genoma, a partir do arquivo gGg.comps (sa´ıda de componentes).
A s aida consiste em arquivos textos com extens˜ao cfc. Cada arquivo das cliques
s˜ao identificados pelo d´ıgito indicador do n´umero da clique.
Exemplos de alguns arquivos de sa´ıda de cada programa listado na rela¸c˜ao acima podem
ser vistos em B.2.
A implementa¸c˜ao da fase “Busca Hom´ologos” 4.1.2 foi realizada utilizando os seguintes
programas e scripts:
• cria multi fasta.pl - script que cria arquivos multi-fasta, sem as seq¨uˆencias dis-
crepantes, a partir dos arquivos das cliques maximais (sa´ıda do programa cliques).
Para cada arquivo de entrada que passou pelo teste das seq¨uˆencias discrepantes, o
script gera um arquivo de sa´ıda com extens˜ao faa contendo as seq¨uˆencias no formato
FASTA. Para cada arquivo de extens˜ao faa, um arquivo de extens˜ao fqf ser´a cri-
ado, e armazenar´a inicialmente as prote´ınas nativas e posteriormente, as prote´ınas
agregadas. Um parˆametro importante desse script ´e o n´umero m´ınimo de prote´ınas
pertencentes a uma determinada fam´ılia. O valor padr˜ao ´e 2.
• cria hmms de cliques.pl - script que cria os modelos ocultos de Markov para
cada arquivo multi-fasta gerado por cria multi fasta.pl. A sa´ıda desse escript
s˜ao os arquivos de extens˜ao aln, dnd e hmm, resultantes da utiliza¸c˜ao dos programas
clustalW e hmmbuild. Em seguida utilizamos o programa hmmcalibrate para cada
arquivo de extens˜ao hmm para calibrar o determinado modelo.
• busca faa hmm.pl - script que agrega prote´ınas `as novas fam´ılias a partir dos arqui-
vos de extens˜ao fqf e hmm. O script gera para cada fam´ılia que passou pelo teste de
discrepantes (arquivos de extens˜ao fqf), um arquivo texto de extens˜ao ff contendo
informa¸c˜oes das prote´ınas nativas e agregadas; e mais a sa´ıda do arquivo clustalW
gerada para a fam´ılia.
Na Figura 4.2 temos uma ilustra¸c˜ao do fluxo de execu¸c˜ao da fase “Busca Hom´ologos”.
Trechos dos arquivos de sa´ıda de cada script listado na rela¸c˜ao acima podem ser vistos
na se¸c˜ao seguinte.
B.2 Exemplos de alguns arquivos de sa´ıda
Para ilustrarmos os exemplos dos arquivos de sa´ıda da se¸c˜ao anterior, utilizamos os geno-
mas Pseudomonas aeruginosa PA01 (Pa) e Synechocystis sp. PCC 6803 (Sp) que foram
utilizados em [5].
66
As figuras B.1 e B.2 mostram, respectivamente, o conte´udo do arquivo papa.10.comp
e um trecho do arquivo papa.comps, resultantes da execu¸c˜ao do programa componente
para o genoma Pseudomonas aeruginosa.
6
30
3234
5091
5098
5373
5383
Figura B.1: Componente conexa encontrada no grafo gerado a partir das prote´ınas do
genoma do organismo Pseudomonas aeruginosa (Pa). A primeira linha indica o n´umero
de prote´ınas pertencentes a essa componente. Cada linha seguinte indica o ´ındice da
prote´ına no arquivo de extens˜ao ptt.
5565
1 -1 0
2 -1 0
3 -1 0
4 1 1 4962
5 -1 0
6 -1 0
7 2 3 2076 1939 2075
8 -1 0
9 -1 0
10 -1 0
11 3 1 3240
12 -1 0
13 -1 0
14 -1 0
15 -1 0
16 -1 0
17 -1 0
18 4 1 943
19 5 1 1121
20 -1 0
21 -1 0
22 6 1 3197
23 7 12 2195 3627 862 1647 2117 5422 3254 2489 3565 1 136 5229 2678
24 -1 0
25 8 1 243
26 -1 0
27 -1 0
28 -1 0
29 9 3 2561 103 1646
30 10 3 3234 5383 5373
Figura B.2: Trecho do arquivo papa.comps. A primeira linha do arquivo indica o n´umero
de prote´ınas encontradas no arquivo de extens˜ao ptt. As linhas seguintes indicam da
esquerda para a direita, o ´ındice da prote´ına no arquivo de extens˜ao ptt; o n´umero da
componente conexa que a prot´eina pertence (-1 se n˜ao pertencer a nenhuma); a quantidade
de prote´ınas vizinhas na componente; e os ´ındices, segundo o arquivo ptt, das prote´ınas
vizinhas na componente.
67
As figuras B.3 e B.4 mostram o conte´udo dos arquivos spsp.155.cfc e spsp.155.fqf
resultantes, respectivamente, da execu¸c˜ao do programa cliques e multi fasta para o
genoma Synechocystis sp.
4
262
2592
2829
2173
Figura B.3: Clique maximal encontrada no grafo gerado para o genoma do organismo
Synechocystis sp. (Ssp).
3
262
2592
2829
Figura B.4: Fam´ılia encontrada ap´os eliminar as seq¨uˆencias discrepantes de sua clique
maximal.
A Figura B.5 mostra um trecho do arquivo spsp.155.ff resultante da execu¸c˜ao do script
busca faa hmm.pl para o genoma Synechocystis sp..
1651914 1524 1233 hypothetical protein
1001724 1629 1233 phytoene dehydrogenase
1001311 1506 1233 hypothetical protein
# 1001515 1416 1231 hypothetical protein
CLUSTAL W (1.83) multiple sequence alignment
gi|1651914|dbj|BAA16840.1| --------------MVPSNAESQSVVVIGAGIGGLTTAALLAQQGYRVKV
gi|1001311|dbj|BAA10798.1| ----------------MTVSPSYDAIVIGSGIGGLVTATQLVSKGLKVLV
gi|1001724|dbj|BAA10561.1| -------------------MITTDVVIIGAGHNGLVCAAYLLQRGLGVTL
gi|1001515|dbj|BAA10142.1| MVIRSGKTNLNPPCALMAPSSSCDCIIVGSGLSGLIAARNLSRVNYSVLV
: . :::*:* .** * * . * :
gi|1651914|dbj|BAA16840.1| YEQAAIVGGCASTFRRRGFIFDVGATQVAGLEPGGIHH-RIFRQLQVD-L
gi|1001311|dbj|BAA10798.1| LERYLIPGGSAGYFEREGYRFDVGASMIFGFGDRGTTN-LLTRALAAVGQ
gi|1001724|dbj|BAA10561.1| LEKREVPGGAATTEALMPELSPQFRFNRCAIDHEFIFLGPVLQELNLAQY
gi|1001515|dbj|BAA10142.1| IEAQERLGG-----RMYGEYLPSGQWIDRGGQWVGPTQDRFLALLNEYNI
* ** . . *
gi|1651914|dbj|BAA16840.1| -IVGGVG-QRLTTFGPFGFAP--RTPIRNLWLVGDSVHPGEG--TAGVSY
gi|1001311|dbj|BAA10798.1| -TYGPIPRRRLPGLLPMPFN---RTAIPGLYCVGDSTFPGQG--LNAVAF
gi|1001724|dbj|BAA10561.1| VYHLDMSLDQMMFLRPLPEIANYQTPIKNLYLTGAGTHPGGS--ISGMP-
gi|1001515|dbj|BAA10142.1| -WVGGGYAAFMPPGVWTSFGQALSAPVGRIHWAGTEIAPRWAGFFDGAIR
: :.: : .* * . .
gi|1651914|dbj|BAA16840.1| PQGLWHLQGSMQTLGDRLVEALKNHGGELFCSQRVEQIHCGQGYVEGVTV
gi|1001311|dbj|BAA10798.1| G-GINYPKGGVGQIAESLVAGLEKFGGKIRYGARVTKIIQENNQAIGVEL
gi|1001724|dbj|BAA10561.1| LEGIARPKGGTGALTEALVKLVQAQGGKILTDQTVKRVLVENNQAIGVEV
gi|1001515|dbj|BAA10142.1| NPEAELLHGGAGQIPQKIAAELGN---SILLGEPVIHIAQDDK---GVEV
:*. : : :. : . : . * :: : ** :
Figura B.5: Fam´ılia encontrada ap´os agregar uma nova prote´ına. A parte inicial do
arquivo consiste das informa¸c˜oes sobre a fam´ılia. Essas informa¸c˜oes indicam da esquerda
para a direita; o identificador da prote´ına no GenBank; o tamanho da prote´ına; o n´umero
COG da classifica¸c˜ao da prote´ına; e o nome do produto. Abaixo dessas informa¸c˜oes,
temos a concatena¸c˜ao do arquivo de sa´ıda resultante da execu¸c˜ao do programa clustalW
para as seq¨uˆencias da fam´ılia.
68
Referˆencias Bibliogr´aficas
[1] N. F. Almeida. Ferramentas para compara¸c˜ao genˆomica. Tese de doutorado, IC-
UNICAMP, 2002.
[2] N. F. Almeida e J. C. Setubal. Um modelo oculto de markov para encontrar promo-
tores em seq¨uˆencias de DNA. Relat´orio t´ecnico, Institute of Computing, University
of Campinas, Brazil, 1998.
[3] N. F. Almeida e J. C. Setubal. A set of tools for detailed syntatic pairwise comparison
of whole bacterial genomes, 2000. Manuscript.
[4] N. F. Almeida e J. C. Setubal. Detection of related genes in procaryotes using
syntenic regions. In DIMACS Workshop on Whole Genome Comparison. DIMACS
Center, Rutgers University, February 2001.
[5] N. F. Almeida, J. C. Setubal, M. H. Carvalho, e C. J. M. Viana. A method to
determine homologous protein families based on graph cliques and profiles. In 3th
Brazilian Workshop on Bioinformatics. October 2004. WOB Bras´ılia (poster).
[6] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, e D. J. Lipman. A basic local
alignment search tool. Journal of Molecular Biology, 215:403–410, 1990.
[7] S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zhang, W. Miller, e D. J.
Lipman. Gapped blast and psi-blast: a new generation of protein database search
programs. Nucleic Acid Research, 25:3389–3402, 1997.
[8] C. E. R. Alves, E. N. C´aceres, e S. W. Song. A BSP/CGM algorithm for finding
all maximal contiguous subsequence of a sequence of numbers. EUROPAR, 2006.
[9] R. V. Andrade, M. E. M. T. Walter, M. J. A. Carvalho, N. F. Almeida, M. M.
Br´ıgido, e M. S. S. Felipe et al. Overview and perspectives on the transcriptome of
paracoccidioides brasiliensis. Revista Iberoamericada de Micolog´ıa, 22:203–212, 2005.
[10] G. S. Ara´ujo. Filogenia de Proteomas. Disserta¸c˜ao de Mestrado, DCT-UFMS, 2003.
[11] A. Bateman, E. Birney, L. Cerruti, R. Durbin, L. Etwiller, S. R. Eddy, S. Griffiths-
Jones, K. L. Howe, M. Marshall, e E. L. Sonnhammer. The pfam protein families
database. Nucleic Acids Research, 30:276–280, 2002.
69
[12] M. M. Br´ıgido, M. M. T. Walter, A. G. Oliveira, M. K. Inoue, D. S. Anjos, E. F. O.
Sandes, J. J. Gondim, M. J. A. Carvalho, N. F. Almeida, e M. S. S. Felipe. Bioin-
formatics of the Paracoccidioides brasiliensis EST Project. Genetics and Molecular
Research, 4:203–215, 2005.
[13] S. B. Cannon e N. D. Young. OrthoParaMap: Distinguishing orthologs from paralogs
by integrating comparative genome data and gene phylogenies. BMC Bioinformatics,
4, 2003.
[14] T. H. Cormen, C. E. Leiserson, e R. L. Rivest. Introduction to Algorithms. MIT
Press/McGraw-Hill, Cambridge,MA/New York, 1990.
[15] A. C. Rasera da Silva, J. C. Setubal, e N. F. Almeida et al. Comparison of the
genomes of two xanthomonas pathogens with differing host specificities. Nature,
417(6887):459–463, May 2002.
[16] A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, e S. L. Salzberg.
Alignment of whole genomes. Nucleic Acids Research, 27:2369–2376, 1999.
[17] S. R. Eddy. Profile hidden markov models. Bioinformatics, 14:755–763, 1998.
[18] S. R. Eddy. What is a hidden markov model? Nature Biotechnology, 22:1315–1316,
2004.
[19] A. J. Enright, S. V. Dongen, e C. A. Ouzounis. An efficient algorithm for large-scale
detection of protein families. Nucleic Acids Research, 30:1575–1584, 2002.
[20] M. S. S. Felipe, M. E. M. T. Walter, M. M. Br´ıgido, e N. F. Almeida et al. Trans-
criptome characterization of the dimorphic and pathogenic fungus paracoccidioides
brasiliensis by est analysis. Yeast, 20(3):263–271, 2003.
[21] M. S. S. Felipe, M. E. M. T. Walter, M. M. Br´ıgido, e N. F. Almeida et al. Trans-
criptional profiles of the human pathogenic fungus paracoccidioides brasiliensis in
mycelium and yeast cells. Journal of B iological Chemistry, 280(26):24706–24714,
2005.
[22] M. Kellis. Computational Comparative Genomics: Genes, Regulation, Evolution.
Tese de doutorado, Massachusetts Institute of Technology, 2003.
[23] M. Kellis, N. Patterson, B. Birren, B. Berger, e E. S. Lander. Methods in comparative
genomics: genome correspondence, gene identification and motif discovery. Journal
of Computational Biology, 11:319–355, 2004.
[24] C. B. Monteiro-Vitorello, L. E. A. Camargo, J. C. Setubal, e N. F. Almeida et al.
The genome sequence of the gram-positive sugarcane pathogen leifsonia xyli subsp.
xyli. Molelular Plant-Microbe Interactions, 17(8):827–836, 2004.
[25] L. Montera. Regi˜oes Ort´ologas em M´ultiplos Genomas. Disserta¸c˜ao de Mestrado,
DCT-UFMS, 2004.
70
[26] L. M. Moreira, R. F. de Souza, N. F. Almeida, J. C. Setubal, J. C. F. Oliveira,
L. R. Furlan, J. A. Ferro, e A. C. R da Silva. Comparative genomics analyses of
citrus-associated bacteria. Annual Reviews Phytopathology, 42:163–184, 2004.
[27] Nomenclature Committee of the International Union of Biochemistry (NC-IUB). No-
menclature for incompletely specified bases in nucleic acid sequences.recomendations
1984. Europen Journal of Biochemistry., 150:1–5, 1985.
[28] P. A. Pevzner. Computational Molecular Biology. MIT Press, 2000.
[29] S. Rudd. Expressed Sequence Tags: alternative or complement to whole genome
sequences? TRENDS in Plant Science, 8:321–329, 2003.
[30] W. L. Ruzzo e M. Tompa. A linear time algorithm for finding all maximal sco-
ring subsequences. In Seventh International Conference on Intelligent Systems for
Molecular Biology. Heidelberg, Germany, 1999.
[31] S. L. Salzberg, A. L. Delcher, A. Phillippy, e J. Carlton. Fast algorithms for large-scale
genome alignment and comparison. Nucleic Acids Research, 30:2478–2483, 2002.
[32] S. L. Salzberg, S. Kurtz, A. Phillippy, A. L. Delcher, M. Smoot, M. Shumway, e
C. Antonescu. Versatile and open software for comparing large genomes. Genome
Biology, 5, 2004.
[33] S. L. Salzberg, D. B. Searls, e S. Kasif, editores. Computational Methods in Molecular
Biology, volume 32 de New comprehensive biochemistry. Elsevier, Netherlands, 1998.
[34] D. Sankoff. Gene and genome duplication. Current Opinion in Genetics & Develop-
ment, 11:681–684, 2001.
[35] J. C. Setubal. Computational analyses fo bacterial genomes: tasks, techinques, and
tools. Relat´orio t´ecnico, Institute of Computing, University of Campinas, Brazil,
2002.
[36] J. C. Setubal e J. Meidanis. Introduction to Computational Molecular Biology. PWS
Publishing Co., 1997.
[37] M. A. Van Sluys, J. C. Setubal, e N. F. Almeida et al. Comparative analyses of the
complete genome sequences of pierce’s disease and citrus variegated chlorosis strains
of xylella fastidiosa. Journal of Bacteriology, 185(3):1018–1026, 2003.
[38] G. D. Stormo e G. W. Hartzell. Identifying Protein-Binding Sites from Unaligned
DNA Fragments. PNAS , 86:1183–1187, 1989.
[39] J. Tamames. Evolution of gene order c onservation in prokaryotes. Genome Biology,
2(6), 2001.
[40] R. L. Tatusov, M. Y. Galperin, D. A. Natale, e E. V. Koonin. The COG database:
a tool for genome-scale analysis of protein functions and evolution. Nucleic Acids
Research, 28:33–36, 2000.
71
[41] G. P. Telles, M. M. Br´ıgido, N. F. Almeida, C. J. M. Viana, D. A. S. Anjos, e M. E.
M. T. Walter. A method for comparing three genomes. Lectu re Notes in Computer
Science, 3594:160–169, 2005.
[42] J. D. Thompson, D. G. Higgins, e T. J. Gibson. Clustalw: improving the sensitivity
of progressive multiple sequence alignment through sequence weighting, position-
specific gap penalties and weight matrix choice. Nucleic Acids Research, 22:4673–
4680, 1994.
[43] A. T. R.de Vasconcelos, C. A. M. Russo, e C. J. M. Viana et al. Mammibase: a
mammalian mitochondrial genome database. In 2nd International Conference on
Bioinformatics and Computational Biology. October 2004. Icobicobi - Angra dos
Reis, RJ (poster).
[44] A. T. R.de Vasconcelos, C. A. M. Russo, e C. J. M. Viana et al. Mammibase: a
mitochondrial genome database for mammalian phylogenetic studies. Bioinformatics,
21:2566–2567, May 2005.
[45] D. W. Wood, J. C. Setubal, N. F. Almeida, e et al. Sequencing and analysis of the
agrobacterium tumefaciens genome. In 10th Int’l congress on Molecular plant-microbe
interactions. 2001. Madison, WI (poster).
[46] D. W. Wo od, J. C. Setubal, e N. F. Almeida et al. The genome of the natural genetic
engineer agrobacterium tumefaciens c58. Science, 294(5550):2317–2323, December
2001.
[47] G. G. Zerlotini, D. A. S. Anjos, M. E. M. T. Walter, M. M. Br´ıgido, G. P. Telles,
C. J. M. Viana, e N. F. Almeida. A method for obtaining orthologous genes among
three genomes. 2006. In Preparation.
[48] Documenta¸c˜ao on-line de EGG. Dispon´ıvel em URL: http://egg.dct.ufms.br/egg.
Acesso em 14 de julho de 2006.
[49] National center for biotechnology information - NCBI. Dispon´ıvel em URL:
http://www.ncbi.nlm.nih.gov/. Acesso em 5 de junho de 2006.
[50] STRING - Search Tool for the Retrieval of Interacting Genes/Proteins. Dispon´ıvel
em URL: http://string.embl.de/. Acesso em 10 de agosto de 2006.
72
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo