Dissertação

{en_GB=Fast mapping and querying over large scale typing data} {} EVALUATED

{pt=A introdução do High-Throughput DNA Sequencing(HTS) criou um novo paradigma na tipagem microbiana e nos estudos de estrutura genonima populacional. O HTS têm a capacidade de sequenciar os genomas em milhares de strains, onde surgiu a necessidade de criar formas eficazes de representar as relações destas. Uma dessas formas é a análise do Polimorfismo de nucleotídeo unico (SNP), onde resulta perfis que contem milhares de loci que podem ser usados para a vigilância de doenças infecciosas, investigação de surtos e na historia natural de uma infecção. Para definir esses perfis é necessário mapear os dados obtidos pelo o HTS, identificar os genes mais relevantes e por fim, consultar as bases de dados já existentes para verificar se os strains jé existem e/ou obter os strains similares ao que esta a ser analisado. Dado o grande volume de dados obtidos pelo o HTS, o tamanho das bases de dados e a urgência destas análises, nomeadamente, na presença de surtos, torna-se um grande desafio computacional o mapeamento e a pesquisa em tempo util. Neste trabalho é proposto uma nova abordagem para solucionar este problema sem utilizar metodos clássicos de approximate string matching. Esta abordagem irá utilizar código lineares, nomeadamente Reed Muller Code (RM), para agrupar SNPs nas regiões das palavras de código., en=High-Throughput DNA Sequencing (HTS) methods gave rise to a paradigm shift in microbial typing and genomic population structure studies. The ability to partially sequence the genomes of hundreds to thousands of strains created the need for effective ways to represent relationships between strains. Single Nucleotide Polymorphism (SNP) analysis and whole or core genome MultiLocus Sequence Typing (wgMLST or cgMLST), result in profiles that have thousands of loci which can be used for outbreak investigation, epidemiological surveillance of clones of interest and bacterial population or evolutionary studies. The first step to define these profiles is to map reads obtained through genome sequencing, identify relevant genes, and query existing typing databases to find if the strain being analyzed has been identified already, or if it is a new strain. Given the size of existing typing databases, the data volume resulting from HTS, and the urgency of these analyses, namely when in presence of outbreaks, the inherent computational problem of mapping and querying typing data has become a big challenge. To solve this issue, this work intends to demonstrate and proof a new approach that relies on Linear Codes, specifically on Reed-Muller codes.}
{pt=Polimorfismo de Nucleotídeo Único, Códigos Lineares, Distância de Hamming, Código Reed-Muller, en=Single Nucleotide Polymorphism, Linear Codes, Hamming Distance, Reed-Muller Codes, Approximate String Matching}

Novembro 5, 2018, 13:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Luís Manuel Silveira Russo

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Alexandre Paulo Lourenço Francisco

Departamento de Engenharia Informática (DEI)

Professor Auxiliar