Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear
Uloženo v:
| Hlavní autor: | |
|---|---|
| Datum vydání: | 2008 |
| Médium: | Doctoral thesis |
| Jazyk: | por |
| Zdroj: | Repositório Institucional da UnB |
| DOI: | http://dx.doi.org/10.26512/2008.T.1213 |
| Download full: | http://repositorio.unb.br/handle/10482/1213 http://dx.doi.org/10.26512/2008.T.1213 |
Shrnutí: | Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. |
| _version_ | 1871442504970141696 |
|---|---|
| author | Corrêa, Jan Mendonça |
| author_browse | Corrêa, Jan Mendonça |
| author_facet | Corrêa, Jan Mendonça |
| author_role | author |
| bitstream.checksum.fl_str_mv | 1f33d862081703c73ca93cae5ea50d48 b2cd6a47688b73dab7b491ae28a8adfc faf479f2bc4220ad42f6d513b7e3e1f1 |
| bitstream.checksumAlgorithm.fl_str_mv | MD5 MD5 MD5 |
| bitstream.url.fl_str_mv | http://repositorio.unb.br/bitstream/10482/1213/1/TESE_2008_JanMendoncaCorrea.pdf http://repositorio.unb.br/bitstream/10482/1213/2/license.txt http://repositorio.unb.br/bitstream/10482/1213/3/TESE_2008_JanMendoncaCorrea.pdf.txt |
| collection | Repositório Institucional da UnB |
| contributor_str_mv | Melo, Alba Cristina Magalhães Alves de |
| dc.contributor.advisor1.fl_str_mv | Melo, Alba Cristina Magalhães Alves de |
| dc.contributor.author.fl_str_mv | Corrêa, Jan Mendonça |
| dc.date.accessioned.fl_str_mv | 2009-02-12T17:40:50Z |
| dc.date.available.fl_str_mv | 2009-02-12T17:40:50Z |
| dc.date.created.fl_str_mv | 2008-05 |
| dc.date.issued.fl_str_mv | 2008-05 |
| dc.date.submitted.none.fl_str_mv | 2008-05 |
| dc.identifier.citation.fl_str_mv | CORRÊA, Jan Mendonça. Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear. 2008. 151 f. Tese (Doutorado em Engenharia Elétrica)-Universidade de Brasília, Brasília, 2008. |
| dc.identifier.doi.none.fl_str_mv | http://dx.doi.org/10.26512/2008.T.1213 |
| dc.identifier.uri.fl_str_mv | http://repositorio.unb.br/handle/10482/1213 |
| dc.language.iso.fl_str_mv | por |
| dc.rights.driver.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.source.none.fl_str_mv | reponame:Repositório Institucional da UnB instname:Universidade de Brasília (UnB) instacron:UNB |
| dc.subject.keyword.none.fl_str_mv | Biologia computacional Bioinformática Alinhamento de sequências |
| dc.subject.keyword.pt_BR.fl_str_mv | Arquitetura em FPGA Sequências biológicas Espaço linear Arquitetura wavefront |
| dc.title.alternative.pt_BR.fl_str_mv | FPGA architectures for biological sequence comparison in linear space |
| dc.title.pt_BR.fl_str_mv | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| dc.type.driver.fl_str_mv | info:eu-repo/semantics/doctoralThesis |
| dc.type.status.fl_str_mv | info:eu-repo/semantics/publishedVersion |
| description | Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. |
| eu_rights_str_mv | openAccess |
| format | doctoralThesis |
| id | UNB_ce2ffadf21812cc8fef4f7db1be2f6b4 |
| identifier_str_mv | CORRÊA, Jan Mendonça. Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear. 2008. 151 f. Tese (Doutorado em Engenharia Elétrica)-Universidade de Brasília, Brasília, 2008. |
| instacron_str | UNB |
| institution | UNB |
| instname_str | Universidade de Brasília (UnB) |
| language | por |
| network_acronym_str | UNB |
| network_name_str | Repositório Institucional da UnB |
| oai_identifier_str | oai:repositorio.unb.br:10482/1213 |
| publishDate | 2008 |
| publishDateSort | 2008 |
| reponame_str | Repositório Institucional da UnB |
| repository.mail.fl_str_mv | repositorio@unb.br |
| repository.name.fl_str_mv | Repositório Institucional da UnB - Universidade de Brasília (UnB) |
| repository_id_str | |
| spelling | Corrêa, Jan MendonçaMelo, Alba Cristina Magalhães Alves de2009-02-12T17:40:50Z2009-02-12T17:40:50Z2008-052008-052008-05CORRÊA, Jan Mendonça. Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear. 2008. 151 f. Tese (Doutorado em Engenharia Elétrica)-Universidade de Brasília, Brasília, 2008.http://repositorio.unb.br/handle/10482/1213http://dx.doi.org/10.26512/2008.T.1213Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008.O alinhamento de seqüências biológicas é uma das operações mais básicas em bioinformática, tendo por objetivo determinar a similaridade entre as seqüências. A solução deste problema envolve geralmente a comparação de seqüências através de programação dinâmica. Este tipo de comparação gera resultados ótimos mas possui complexidade quadrática de tempo, justificando métodos para sua aceleração em hardware como o FPGA. Na presente tese foram projetadas arquiteturas wavefront em FPGA utilizando espaço linear para três diferentes algoritmos. O primeiro algoritmo foi o de Smith-Waterman. Ele foi implementado na forma de um vetor wavefront e foi utilizado na aceleração da fase inicial de um algoritmo de alinhamento. Esta arquitetura foi capaz de recuperar o maior escore e posição em espaço linear. Esta arquitetura foi sintetizada em FPGA e o melhor resultado da arquitetura foi 246,9 vezes mais rápido que em software, demonstrando a utilidade da arquitetura. A seguir, foi projetada uma arquitetura para a recuperação do escore ótimo do algoritmo de programação dinâmica DIALIGN também em espaço linear. Foram obtidos resultados até 383,41 vezes superiores ao programa em software. Para recuperar o alinhamento ótimo no DIALIGN é necessário espaço quadrático. Assim, foi projetada uma variante do DIALIGN capaz de recuperar o alinhamento de duas seqüências em espaço linear. Após a implementação em hardware, os resultados obtidos foram até 141,38 vezes mais rápido que a implementação em software. ______________________________________________________________________________________ ABSTRACTThe alignment of biological sequences is one of the more basic operations in bioinformatics. Its purpose is to find the similarity between sequences. The solution to this problem generally involves sequence comparison through dynamic programming. This kind of comparison yields optimal results but has quadratic time complexity thus justifying its hardware acceleration in FPGA. In this thesis, linear space wavefront architectures were designed in FPGA for three different algorithms. The first algorithm was Smith-Waterman. It was implemented in a wavefront array and utilized to accelerate the initial phase of a sequence alignment algorithm. This architecture was able to retrieve the largest score and its position in linear space. It was synthesized in FPGA and the best result was 246,9 times faster than software, showing the appropriateness of the architecture. Also, an architecture to retrieve the optimal DIALIGN score in linear space was designed. The results were up to 383,41 times better than software. The retrieval of the optimal alignment for DIALIGN needs quadratic space. Therefore, a variant for the DIALIGN dynamic programming algorithm was proposed to retrieve the alignment in linear space. This variant was implemented in hardware and the results were up to 141,38 times faster than the software implementation.Faculdade de Tecnologia (FT)Departamento de Engenharia Elétrica (FT ENE)Programa de Pós-Graduação em Engenharia ElétricaArquiteturas em FPGA para comparação de sequências biológicas em espaço linearFPGA architectures for biological sequence comparison in linear spaceinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/doctoralThesisArquitetura em FPGASequências biológicasEspaço linearArquitetura wavefrontBiologia computacionalBioinformáticaAlinhamento de sequênciasBRAinfo:eu-repo/semantics/openAccessporreponame:Repositório Institucional da UnBinstname:Universidade de Brasília (UnB)instacron:UNBORIGINALTESE_2008_JanMendoncaCorrea.pdfTESE_2008_JanMendoncaCorrea.pdfapplication/pdf1697042http://repositorio.unb.br/bitstream/10482/1213/1/TESE_2008_JanMendoncaCorrea.pdf1f33d862081703c73ca93cae5ea50d48MD51open accessLICENSElicense.txtlicense.txttext/plain1865http://repositorio.unb.br/bitstream/10482/1213/2/license.txtb2cd6a47688b73dab7b491ae28a8adfcMD52open accessTEXTTESE_2008_JanMendoncaCorrea.pdf.txtTESE_2008_JanMendoncaCorrea.pdf.txtExtracted texttext/plain253714http://repositorio.unb.br/bitstream/10482/1213/3/TESE_2008_JanMendoncaCorrea.pdf.txtfaf479f2bc4220ad42f6d513b7e3e1f1MD53open access10482/12132026-02-25 14:45:24.282open accessoai:repositorio.unb.br:10482/1213TGljZW5zZSBncmFudGVkIGJ5IEphcXVlbGluZSBPbGl2ZWlyYSAoamFxdWVvbGl2ZWlyYW1AZ21haWwuY29tKSBvbiAyMDA4LTEyLTA0VDE4OjUwOjEyWiAoR01UKToKCsOJIG5lY2Vzc8OhcmlvIGNvbmNvcmRhciBjb20gYSBsaWNlbsOnYSBkZSBkaXN0cmlidWnDp8OjbyBuw6NvLWV4Y2x1c2l2YSwKYW50ZXMgcXVlIG8gZG9jdW1lbnRvIHBvc3NhIGFwYXJlY2VyIG5vIFJlcG9zaXTDs3Jpby4gUG9yIGZhdm9yLCBsZWlhIGEKbGljZW7Dp2EgYXRlbnRhbWVudGUuIENhc28gbmVjZXNzaXRlIGRlIGFsZ3VtIGVzY2xhcmVjaW1lbnRvIGVudHJlIGVtCmNvbnRhdG8gYXRyYXbDqXMgZGU6IHJlcG9zaXRvcmlvQGJjZS51bmIuYnIgb3UgMzMwNy0yNDExLgoKTElDRU7Dh0EgREUgRElTVFJJQlVJw4fDg08gTsODTy1FWENMVVNJVkEKCkFvIGFzc2luYXIgZSBlbnRyZWdhciBlc3RhIGxpY2Vuw6dhLCBvL2EgU3IuL1NyYS4gKGF1dG9yIG91IGRldGVudG9yIGRvcwpkaXJlaXRvcyBkZSBhdXRvcik6CgphKSBDb25jZWRlIMOgIFVuaXZlcnNpZGFkZSBkZSBCcmFzw61saWEgbyBkaXJlaXRvIG7Do28tZXhjbHVzaXZvIGRlCnJlcHJvZHV6aXIsIGNvbnZlcnRlciAoY29tbyBkZWZpbmlkbyBlbSBiYWl4byksIGNvbXVuaWNhciBlL291CmRpc3RyaWJ1aXIgbyBkb2N1bWVudG8gZW50cmVndWUgKGluY2x1aW5kbyBvIHJlc3Vtby9hYnN0cmFjdCkgZW0KZm9ybWF0byBkaWdpdGFsIG91IGltcHJlc3NvIGUgZW0gcXVhbHF1ZXIgbWVpby4KCmIpIERlY2xhcmEgcXVlIG8gZG9jdW1lbnRvIGVudHJlZ3VlIMOpIHNldSB0cmFiYWxobyBvcmlnaW5hbCwgZSBxdWUKZGV0w6ltIG8gZGlyZWl0byBkZSBjb25jZWRlciBvcyBkaXJlaXRvcyBjb250aWRvcyBuZXN0YSBsaWNlbsOnYS4gRGVjbGFyYQp0YW1iw6ltIHF1ZSBhIGVudHJlZ2EgZG8gZG9jdW1lbnRvIG7Do28gaW5mcmluZ2UsIHRhbnRvIHF1YW50byBsaGUgw6kKcG9zc8OtdmVsIHNhYmVyLCBvcyBkaXJlaXRvcyBkZSBxdWFscXVlciBvdXRyYSBwZXNzb2Egb3UgZW50aWRhZGUuCgpjKSBTZSBvIGRvY3VtZW50byBlbnRyZWd1ZSBjb250w6ltIG1hdGVyaWFsIGRvIHF1YWwgbsOjbyBkZXTDqW0gb3MKZGlyZWl0b3MgZGUgYXV0b3IsIGRlY2xhcmEgcXVlIG9idGV2ZSBhdXRvcml6YcOnw6NvIGRvIGRldGVudG9yIGRvcwpkaXJlaXRvcyBkZSBhdXRvciBwYXJhIGNvbmNlZGVyIMOgIFVuaXZlcnNpZGFkZSBkZSBCcmFzw61saWEgb3MgZGlyZWl0b3MKcmVxdWVyaWRvcyBwb3IgZXN0YSBsaWNlbsOnYSwgZSBxdWUgZXNzZSBtYXRlcmlhbCBjdWpvcyBkaXJlaXRvcyBzw6NvIGRlCnRlcmNlaXJvcyBlc3TDoSBjbGFyYW1lbnRlIGlkZW50aWZpY2FkbyBlIHJlY29uaGVjaWRvIG5vIHRleHRvIG91CmNvbnRlw7pkbyBkbyBkb2N1bWVudG8gZW50cmVndWUuCgpTZSBvIGRvY3VtZW50byBlbnRyZWd1ZSDDqSBiYXNlYWRvIGVtIHRyYWJhbGhvIGZpbmFuY2lhZG8gb3UgYXBvaWFkbwpwb3Igb3V0cmEgaW5zdGl0dWnDp8OjbyBxdWUgbsOjbyBhIFVuaXZlcnNpZGFkZSBkZSBCcmFzw61saWEsIGRlY2xhcmEgcXVlCmN1bXByaXUgcXVhaXNxdWVyIG9icmlnYcOnw7VlcyBleGlnaWRhcyBwZWxvIHJlc3BlY3Rpdm8gY29udHJhdG8gb3UKYWNvcmRvLgoKQSBVbml2ZXJzaWRhZGUgZGUgQnJhc8OtbGlhIGlkZW50aWZpY2Fyw6EgY2xhcmFtZW50ZSBvKHMpIHNldSAocykgbm9tZSAocykKY29tbyBvIChzKSBhdXRvciAoZXMpIG91IGRldGVudG9yIChlcykgZG9zIGRpcmVpdG9zIGRvIGRvY3VtZW50bwplbnRyZWd1ZSwgZSBuw6NvIGZhcsOhIHF1YWxxdWVyIGFsdGVyYcOnw6NvLCBwYXJhIGFsw6ltIGRhcyBwZXJtaXRpZGFzIHBvcgplc3RhIGxpY2Vuw6dhLgo=Repositório InstitucionalPUBhttps://repositorio.unb.br/oai/requestrepositorio@unb.bropendoar:2026-02-25T17:45:24Repositório Institucional da UnB - Universidade de Brasília (UnB) |
| spellingShingle | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear Corrêa, Jan Mendonça Arquitetura em FPGA Sequências biológicas Espaço linear Arquitetura wavefront Biologia computacional Bioinformática Alinhamento de sequências |
| status_str | publishedVersion |
| title | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| title_full | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| title_fullStr | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| title_full_unstemmed | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| title_short | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| title_sort | Arquiteturas em FPGA para comparação de sequências biológicas em espaço linear |
| topic | Arquitetura em FPGA Sequências biológicas Espaço linear Arquitetura wavefront Biologia computacional Bioinformática Alinhamento de sequências |
| url | http://repositorio.unb.br/handle/10482/1213 http://dx.doi.org/10.26512/2008.T.1213 |