Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(bit parallel algorithms). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Soares Neto, Domingos. Filtros para a busca e extração de padrões aproximados em cadeias biológicas.

Degree: Mestrado, Ciência da Computação, 2008, University of São Paulo

Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados, assim como algoritmos e estruturas de dados essenciais ao seu estudo. Em especial, estudamos a extremamente versátil árvore dos sufixos, assim como uma de suas generalizações e sua estrutura irmã: o vetor dos sufixos. Grande parte do texto é dedicada aos filtros baseados em q-gramas para a busca aproximada de padrões e algumas de suas mais recentes variações. Estão cobertos os algoritmos bit-paralelos de Myers e Baeza-Yates-Gonnet para a busca de padrões; os algoritmos de Sagot para a extração de padrões; os algoritmos de filtragem de Ukkonen, Jokinen-Ukkonen, Burkhardt-Kärkkäinen, entre outros.

This thesis deals with computational formulations and algorithms for the extraction and search of patterns from biological strings. In particular, the present text focuses on the following problems, both considered under Hamming and Levenshtein distances: 1. How to find the positions where a given pattern approximatelly occurs in a given string; 2. How to extract patterns which approximatelly occurs in a certain number of strings from a given set. The first problem, for which there are many polinomial time algorithms, has been receiving a lot of attention since the 60s and entered a new era of discoveries with the advent of computational biology, in the 80s, and the widespread of the Internet and its search engines: both events brought new challenges to be faced by virtue of the large volume of data usually held by such applications and its time constraints. The second problem, much younger, is very challenging due to its computational complexity, approximation hardness and the size of the input data usually held by the most common applications. This problem is also very interesting due to its potential of application. In this work we show…

Advisors/Committee Members: Soares, Jose Augusto Ramos.

Subjects/Keywords: algoritmos bit-paralelos; algoritmos de filtragem; approximate string matching; árvores dos sufixos; bit-parallel algorithms; busca aproximada de padrões; extração de padrões; filter algorithms; motifs; motifs; patterns extraction; q-gramas; q-grams; suffix array; suffix tree; vetor dos sufixos

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Soares Neto, D. (2008). Filtros para a busca e extração de padrões aproximados em cadeias biológicas. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19102009-002745/ ;

Chicago Manual of Style (16th Edition):

Soares Neto, Domingos. “Filtros para a busca e extração de padrões aproximados em cadeias biológicas.” 2008. Masters Thesis, University of São Paulo. Accessed October 20, 2019. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19102009-002745/ ;.

MLA Handbook (7th Edition):

Soares Neto, Domingos. “Filtros para a busca e extração de padrões aproximados em cadeias biológicas.” 2008. Web. 20 Oct 2019.

Vancouver:

Soares Neto D. Filtros para a busca e extração de padrões aproximados em cadeias biológicas. [Internet] [Masters thesis]. University of São Paulo; 2008. [cited 2019 Oct 20]. Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19102009-002745/ ;.

Council of Science Editors:

Soares Neto D. Filtros para a busca e extração de padrões aproximados em cadeias biológicas. [Masters Thesis]. University of São Paulo; 2008. Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19102009-002745/ ;

.