Skip navigation
Use este identificador para citar ou linkar para este item: http://repositorio.unb.br/handle/10482/31605
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2017_DanielSundfeldLima.pdf12,55 MBAdobe PDFVisualizar/Abrir
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorMelo, Alba Cristina Magalhães Alves de-
dc.contributor.authorLima, Daniel Sundfeld-
dc.date.accessioned2018-04-10T19:40:51Z-
dc.date.available2018-04-10T19:40:51Z-
dc.date.issued2018-04-10-
dc.date.submitted2017-12-19-
dc.identifier.citationLIMA, Daniel Sundfeld. Alinhamento primário e secundário de sequências biológicas em arquiteturas de alto desempenho. 2017. xx, 167 f., il. Tese (Doutorado em Informática)—Universidade de Brasília, Brasília, 2017.pt_BR
dc.identifier.urihttp://repositorio.unb.br/handle/10482/31605-
dc.descriptionTese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017.pt_BR
dc.description.abstractO alinhamento múltiplo primário de sequências biológicas é um problema muito importante em Biologia Molecular, pois permite que sejam detectadas similaridades e diferenças entre um conjunto de sequências. Esse problema foi provado NP-Completo e, por essa razão, geralmente algoritmos heurísticos são usados para resolvê-lo. No entanto, a obtenção da solução ótima é bastante desejada e, por essa razão, existem alguns algoritmos exatos que solucionam esse problema para um número reduzido de sequências. As sequências de RNA, diferente do DNA, não possuem dupla-hélice e podem dobrar-se, pois seus nucleotídeos podem formar pares de bases. É conhecido na Biologia Molecular que a função dessa estrutura está ligada à sua conformação espacial, e não à composição de seus nucleotídeos. Obter a estrutura secundária (2D) de uma sequência de RNA também exige uma grande quantidade de recursos computacionais, até mesmo para um pequeno número de sequências. Desta forma, as arquiteturas de alto desempenho são muito importantes para a obtenção dos resultados em um tempo factível. A presente tese visa investigar os problemas do alinhamento múltiplo primário e do alinhamento em pares secundário, utilizando arquiteturas de alto desempenho para acelerar a obtenção de resultados. Para o alinhamento primário ótimo de múltiplas sequências, propusemos na presente Tese o PA-Star, uma estratégia multithreaded baseada no algoritmo A-Star que usa uma política sensível à localidade de atribuição de trabalho às threads. De modo a lidar com o alto uso de memória, nossa estratégia PA-Star usa tanto memória RAM como disco. Para o alinhamento estrutural (2D) de sequências de RNA, propusemos o Foldalign 2.5, que é uma estratégia multithreaded heurística baseada no algoritmo exato de Sankoff, capaz de obter o alinhamento estrutural de grandes sequências em tempo reduzido. Finalmente, propusemos o CUDA-Sankoff, que é capaz de obter o alinhamento estrutural ótimo entre duas sequências de RNA em GPU (Graphics Processing Unit).pt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES).pt_BR
dc.language.isoPortuguêspt_BR
dc.rightsAcesso Abertopt_BR
dc.titleAlinhamento primário e secundário de sequências biológicas em arquiteturas de alto desempenhopt_BR
dc.typeTesept_BR
dc.subject.keywordAlinhamento de sequênciaspt_BR
dc.subject.keywordAlgoritmospt_BR
dc.subject.keywordRNApt_BR
dc.subject.keywordBiologia molecularpt_BR
dc.rights.licenseA concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.pt_BR
dc.description.abstract1The primary multiple sequence Alignment is a very important problem in Molecular Biology since it is able to detect similarities and differences in a set of sequences. This problem has been proven NP-Hard and, for this reason, heuristic algorithms are usually used to solve it. Nevertheless, obtaining the optimal solution is highly desirable and there are indeed some exact algorithms that solve this problem for a reduced number of sequences. The RNA sequences are different than the DNA, they do not have double helix, their nucleotides can form base pairs and the sequence can fold on itself. It is known in the Molecular Biology that, the function of the RNA is related to its spatial structure. Calculating the secondary structure of RNA sequences also demand a high amount of computational resources, even for a small number of sequences. The High Performance Computing (HPC) Platforms can be used in order to produce results faster. The current thesis aims to investigate the primary multiple sequence alignment and the secondary pairwise sequence alignment, using High Performance Architectures to accelerate and obtaining results in reasonable time. For the primary multiple sequence alignment, we propose the PA-Star, a multithreaded solution based on the A-Star algorithm using a locality sensitive hash to distribute the workload among the threads. Due to the high RAM memory usage required by the algorithm, our strategy can also uses disk. For the RNA structural alignment, we proposed the Foldalign 2.5, a multithreaded solution that uses heuristics to reduce the Sankoff Algorithm complexity, and can obtain the pairwise structural alignment of large sequences in reduced time. Finally, we proposed CUDASankoff, that obtains the optimal pairwise structural alignment for RNA sequences using a GPU (Graphics Processing Unit).pt_BR
dc.description.unidadeInstituto de Ciências Exatas (IE)pt_BR
dc.description.unidadeDepartamento de Ciência da Computação (IE CIC)pt_BR
dc.description.ppgPrograma de Pós-Graduação em Informáticapt_BR
Aparece nas coleções:Teses, dissertações e produtos pós-doutorado

Mostrar registro simples do item Visualizar estatísticas



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.