UNIVERSIDADE DE BRASLIA FACULDADE DE .Hidden Markov Models are a powerful tool for protein organization

  • View
    212

  • Download
    0

Embed Size (px)

Text of UNIVERSIDADE DE BRASLIA FACULDADE DE .Hidden Markov Models are a powerful tool for protein...

  • i

    UNIVERSIDADE DE BRASLIA

    FACULDADE DE TECNOLOGIA

    DEPARTAMENTO DE ENGENHARIA ELTRICA

    IMPLEMENTAO EM HARDWARE DE UM

    ACELERADOR HIBRIDO VITERBI-PLAN7/ALGORITMO

    DAS DIVERGNCIAS PARA COMPARAO DE

    PROTEINAS

    JUAN FERNANDO EUSSE GIRALDO

    ORIENTADOR: RICARDO PEZZUOL JACOBI

    DISSERTAO DE MESTRADO EM ENGENHARIA ELTRICA

    PUBLICAO: PPGENE.DM - 403A/09

    BRASLIA/DF: NOVEMBRO 2009

  • ii

    UNIVERSIDADE DE BRASLIA

    FACULDADE DE TECNOLOGIA

    DEPARTAMENTO DE ENGENHARIA ELTRICA

    IMPLEMENTAO EM HARDWARE DE UM ACELERADOR

    HIBRIDO VITERBI-PLAN7/ALGORITMO DAS

    DIVERGNCIAS PARA COMPARAO DE PROTEINAS

    JUAN FERNANDO EUSSE GIRALDO

    DISSERTAO SUBMETIDA AO DEPARTAMENTO DE

    ENGENHARIA ELTRICA DA FACULDADE DE TECNOLOGIA DA

    UNIVERSIDADE DE BRASLIA COMO PARTE DOS REQUISITOS

    NECESSRIOS PARA A OBTENO DO GRAU DE MESTRE.

    APROVADO POR:

    _______________________________

    Prof. Ricardo Pezzuol Jacobi Ph.D (CIC/UnB)

    (Orientador)

    _______________________________

    Prof. Ivan Saraiva Silva Ph. D (DIMAP/UFRN)

    (Examinador Externo)

    _______________________________

    Prof. Carlos Llanos Ph. D (ENM/UnB)

    (Examinador Externo)

    BRASILIA/DF, 16 DE NOVEMBRO DE 2009

  • iii

    FICHA CATALOGRFICA

    EUSSE GIRALDO, JUAN FERNANDO

    Implementao Em Hardware De Um Acelerador Hibrido Viterbi-Plan7/Algoritmo Das

    Divergncias Para Comparao De Protenas.

    xvii, 225p., 210 x 297 mm (ENE/FT/UnB, Mestre, Dissertao de Mestrado Universidade

    de Braslia. Faculdade de Tecnologia.

    Departamento de Engenharia Eltrica.

    1. Comparao de Protenas 2.Acelerao

    3. Divergncias 4.Viterbi Plan7

    5. VHDL 6. FPGA

    I. ENE/FT/UnB II. Ttulo (srie)

    REFERNCIA BIBLIOGRFICA

    EUSSE., J. F. (2009). Implementao Em Hardware De Um Acelerador Hibrido Viterbi-

    Plan7/Algoritmo Das Divergncias Para Comparao De Protenas. Dissertao de

    Mestrado em Engenharia Eltrica, Publicao PPGENE.DM-403A/09, Departamento de

    Engenharia Eltrica, Universidade de Braslia, Braslia, DF, 219p.

    CESSO DE DIREITOS

    AUTOR: Juan Fernando Eusse Giraldo.

    TTULO: Implementao Em Hardware De Um Acelerador Hibrido Viterbi-

    Plan7/Algoritmo Das Divergncias Para Comparao De Protenas.

    GRAU: Mestre ANO: 2009

    concedida Universidade de Braslia permisso para reproduzir cpias desta dissertao

    de mestrado e para emprestar ou vender tais cpias somente para propsitos acadmicos e

    cientficos. O autor reserva outros direitos de publicao e nenhuma parte dessa dissertao

    de mestrado pode ser reproduzida sem autorizao por escrito do autor.

    ____________________________

    Juan Fernando Eusse Giraldo

    SCLN 407 Bloco C, Asa Norte

    70855-530 Braslia DF Brasil.

  • iv

    AGRADECIMENTOS

    Ao meu orientador, professor Ricardo Pezzuol Jacobi, pela oportunidade de desenvolver o

    meu conhecimento sob a sua orientao, pela pacincia e pela ajuda prestada durante o

    tempo de estudo.

    A professora Nahri Moreano, suas explicaes e sua inteligncia fizeram possvel a feliz

    terminao do trabalho.

    A professora Alba Cristina Magalhaes de Melo pelas dicas que ajudaram a feliz concluso

    deste trabalho.

    A minha famlia pelo apoio neste passo to importante da minha vida.

    Para Marcela por estar siempre a mi lado, por amarme tal como soy y por que se siempre

    estaremos juntos.

    Aos colegas do LAICO/LDCI/LTSD pelas suas contribuies e pelo timo ambiente de

    trabalho.

    Para os meus amigos especialmente para o Augusto, o Edcelio, o Vladimir, o Sergio, o

    Diego, o Sebastian e a Juliana. Sem seu apoio e carinho constante no seria quem eu sou.

  • v

    Para Torres, quien sin darse cuenta cambio la vida de

    muchas personas y que nunca ser olvidado.

  • vi

    ABSTRACT

    HARDWARE IMPLEMENTATION OF A HYBRID VITERBI-

    PLAN7/DIVERGENCE PROTEIN COMPARISSON ACCELERATOR IN VHDL

    Author: Juan Fernando Eusse Giraldo

    Advisor: Ricardo Pezzuol Jacobi

    Electrical Engeneering Graduate Program

    Braslia, November 2009

    Hidden Markov Models are a powerful tool for protein organization and identification

    because they allow identifying and classifying highly representative structures and

    functional units inside the amino acid chains that form them. The Viterbi algorithm is one

    of the most used algorithms in protein comparison and identification using Hidden Markov

    Models, and is implemented inside the open source software HMMER [1][2], which is

    widely used among the scientific community. Due to the exponential growth in the size of

    protein databases in the past years, the necessity to accelerate software execution to reduce

    comparison and search times rose. In this master thesis, a hardware accelerator is

    implemented in VHDL in order to reduce those processing times in the protein comparison

    and search processes. The implemented accelerator uses a new algorithm which enables

    the system (Hardware+Software) to economize processing time by reducing the number of

    calculations needed to perform a comparison. The accelerator not only produces the

    similarity score for a sequence when compared against a profileHMM but also produces

    the parameters to limit the region of the Dynamic Programming Matrices that must be

    reprocessed to generate the alignment. The implemented accelerator produces a maximum

    gain of up to 182 times when compared to unaccelerated software. A new performance

    measurement strategy is introduced in this work, which not only takes into account the

  • vii

    acceleration achieved by the hardware, but also the post-processing stages that follows

    hardware made comparisons.

  • viii

    RESUMO

    IMPLEMENTAO EM HARDWARE DE UM ACELERADOR HIBRIDO

    VITERBI-PLAN7/ALGORITMO DAS DIVERGNCIAS PARA COMPARAO

    DE PROTEINAS

    Autor: Juan Fernando Eusse Giraldo

    Orientador: Ricardo Pezzuol Jacobi

    Programa de Ps-graduao em Engenharia Eltrica

    Braslia, Novembro de 2009

    Os Modelos Ocultos de Markov (HMM Hidden Markov Models) constituem uma

    poderosa ferramenta para mapeamento e organizao de protenas, uma vez que permitem

    reconhecer estruturas altamente representativas e unidades funcionais dentro das cadeias de

    aminocidos que as conformam. O Viterbi um dos principais algoritmos para

    comparao e identificao de protenas (sequncias de aminocidos) baseados em HMM,

    e implementado dentro do software livre HMMER [1][2], muito utilizado na comunidade

    cientfica. Nos ltimos anos, devido ao crescimento exponencial das bases de dados que

    armazenam protenas, surge a necessidade de acelerar a execuo do software para reduzir

    os tempos de processamento dos algoritmos de comparao. Neste trabalho de mestrado,

    realizada a acelerao do software HMMER para alinhamento de sequncias biolgicas

    atravs da implementao de um acelerador em hardware. O acelerador proposto utiliza

    um novo algoritmo chamado de Algoritmo das Divergncias, o qual permite ao sistema

    completo (Hardware+Software) economizar uma grande quantidade de clculos para gerar

    os alinhamentos de protenas. O Hardware produz a medida de similaridade da protena

    com o modelo HMM e os ndices inicial e final da poro de interesse da sequncia de

    aminocidos como uma primeira etapa de filtragem. Isto, quando gerado pelo acelerador,

  • ix

    significa uma economia de processamento adicional para o software, o qual tem que

    reprocessar dita regio para gerar o alinhamento da sequncia com o profileHMM, e

    contribui com a acelerao da execuo do algoritmo. O Acelerador atinge ganhos de at

    182x quando comparado com o software no acelerado. Alm disso, o trabalho prope

    uma nova medida para a comparao do desempenho e realiza medies exatas acerca da

    acelerao atingida ao integrar o acelerador ao fluxo de execuo do software.

  • x

    SUMRIO

    1- INTRODUO ........................................................................................... 1

    2 - OBJETIVOS ............................................................................................... 3

    2.1 - OBJETIVO GERAL ............................................................................................... 3

    2.2 - OBJETIVOS ESPECFICOS ................................................................................. 3

    3 - REVISO BIBLIOGRFICA ................................................................. 5

    3.1 - CONCEITOS BSICOS PARA ANLISE DE SEQUNCIAS BIOLGICAS

    ........................................................................................................................................... 5

    3.1.1 - Alinhamentos ..................................................................................................... 6

    3.1.2 - Programao dinmica ..................................................................................... 8

    3.2 - ALGORITMOS PARA ALINHAMENTO DE PROTENAS ............................ 8

    3.2.1 - Alinhamento de pares (pairwise alingment) .................................................... 9

    3.2.1.1 - Algor