Mostrar registro simples

dc.contributor.advisorWirth, Gilson Inaciopt_BR
dc.contributor.authorMallmann, Rafael Mendespt_BR
dc.date.accessioned2012-10-24T01:38:00Zpt_BR
dc.date.issued2010pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/56841pt_BR
dc.description.abstractBancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas.pt_BR
dc.description.abstractBioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.en
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectMicroeletrônicapt_BR
dc.subjectDNA sequence scanningen
dc.subjectAplicação dos computadorespt_BR
dc.subjectSmith-Watermanen
dc.subjectEdit distanveen
dc.subjectLevenshtein distanceen
dc.subjectDynamic programmingen
dc.subjectSystolic arrayen
dc.subjectFPGAen
dc.subjectASICen
dc.subjectVLSIen
dc.subjectProtein sequencesen
dc.subjectQuery sequenceen
dc.subjectSubject sequenceen
dc.titleArquiteturas em hardware para o alinhamento local de sequências biológicaspt_BR
dc.title.alternativeHardware architectures for local biological sequence alignment en
dc.typeDissertaçãopt_BR
dc.identifier.nrb000860245pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Microeletrônicapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2010pt_BR
dc.degree.levelmestradopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples