Autor(es): Leitão, Natacha Alexandra Pinheiro
Data: 2015
Identificador Persistente: http://hdl.handle.net/10451/20632
Origem: Repositório da Universidade de Lisboa
Assunto(s): Tecnologias de NGC; Algoritmos; Mapeamento de reads; Teses de mestrado - 2015; Departamento de Informática
Tese de mestrado, Bioinformática e Biologia Computacional (Bioinformática), Universidade de Lisboa, Faculdade de Ciências, 2015
O ácido desoxirribonucleico (DNA) é das macromoléculas biológicas mais conhecidas na sociedade, e continua a ser um grande alvo de investigação. No início dos anos 90 do século passado, o Projeto do Genoma Humano começou com o objetivo de sequenciar a informação contida no DNA. Passado treze anos, e cinquenta anos depois deWatson e Crick terem revelado a estrutura em hélice dupla do DNA, a primeira sequência genómica humana foi apresentada quase na sua totalidade; o Projeto do Genoma Humano chegara ao fim, mas não sem mudar as ciências biológicas e a investigação biomédica. O desenvolvimento das tecnologias de sequenciação e a disponibilidade de sequências genómicas de organismos modelo, para além do humano, levou a que a resequenciação se tornasse um método bastante utilizado para ler a informação guardada no genoma. Hoje em dia, a nova geração de tecnologias de sequenciação (NGS Technologies) permitem a produção rápida e a baixo custo de milhares de milhões de pequenos fragmentos de DNA em bruto — usualmente referidos como reads — e um passo importante na análise destes dados é alinhar as reads à sequência de um genoma de referência para determinar o local onde pertencem, isto é, fazer o seu mapeamento. O processo de mapear a vasta quantidade de pequenos fragmentos de DNA, com algumas centenas de bases, a uma sequência genómica, por vezes bastante comprida (por exemplo, o genoma humano tem mais de 3 milhões de pares de bases) é computacionalmente dispendioso. Mais, neste processo é fundamental distinguir entre erros técnicos de sequenciação e variações genéticas que ocorreram naturalmente (e que por vezes levam a doenças) no sujeito da amostra. Para fazer frente ao desafio, muitas ferramentas têm vindo a ser desenvolvidas utilizando abordagens algorítmicas diferentes, sendo que algumas delas incluem a informação sobre a qualidade associada a cada base sequenciada, o que reporta a probabilidade de estar errada. Um dos métodos utilizados no mapeamento envolve procurar ao longo da sequência genómica de referência uma subsequência de uma read; depois, é feito o alinhamento entre a read inteira e a correspondente zona do genoma. Neste trabalho, esta correspondência é baseada numa tabela de dispersão (hash table) — uma estrutura de dados que associa chaves de pesquisa a valores—que guarda pequenas subsequências do genoma e as correspondentes posições na sequência, funcionando como um índice remissivo. Vários algoritmos para criar as chaves de pesquisas—subsequências—para cada read foram implementados em Java, onde a ideia principal é que associando mais do que uma chave a cada read aumentamos a hipótese de encontrar o local a que ela pertence, e consequentemente de mapear todo conjunto de dados. Neste sentido, a nossa solução para o mapeamento de reads é baseado no paradigma da programação modular, em que cada módulo é responsável por uma parte de uma série de tarefas onde duas se destacam: a criação de chaves de pesquisa e o alinhamento. Na criação de chaves de pesquisa os nossos algoritmos têm em conta a semelhança entre as bases do DNA e/ou os valores de qualidade associados às bases que compõem a read, onde partindo de uma subsequência a troca com as restantes bases permite gerar novas chaves de pesquisa. Também implementámos um método existente na literatura que divide a read em partes iguais e sobrepostas. Para o alinhamento foram implementadas três versões do método deNeedleman-Wunsch, um algoritmo de programação dinâmica específico para o alinhamento global de sequências biológicas, que tem em conta inserções e deleções de bases no genoma da amostra em relação ao de referência. Ao alinhamento entre as duas sequências é somada uma pontuação que mede a semelhança entre elas; deste modo, numa implementação simples apenas existem duas situações: há correspondência entre a base da read e a do genoma ou não, havendo uma penalização. Quando recorremos a uma matriz de semelhança de bases, encontrando a mesma base no alinhamento das sequências é dada a pontuação máxima, se as bases forem estruturalmente parecidas é dada uma pontuação menor, e em caso de não haver de todo correspondência há uma penalização. Por fim, implementámos uma versão baseada numa existente na literatura, que inclui a probabilidade de cada uma das quatro bases poder ser a correta no cálculo da pontuação em relação à sequência genómica, e as inserções e deleções (que levam há falta de correspondência, ou seja, a um intervalo entre a sequências) têm uma penalização maior. Dado que temos vários algoritmos para a criação de chaves e para o alinhamento, uma vantagem da nossa abordagem modular é podermos experimentar combinações diferentes entre eles. As combinações possíveis foram testadas com conjuntos de dados artificiais—as reads foram retiradas de posições conhecidas de uma sequência de referência —, construídos com valores de qualidade reais e com a simulação dos erros técnicos de sequenciação mais comuns. A avaliação dos resultados incluiu o tempo de execução — escalabilidade —, se mapeou todas as reads do conjunto de dados — cobertura —, e se mapeou todas as reads no local correto do genoma de referência—precisão. Em relação ao último parâmetro ainda se considerou o facto da read ter sido mapeada a mais do que uma posição e se foi mapeada a um ou a mais possíveis locais com uma pontuação de alinhamento relevante, ou seja, cujo alinhamento tenha resultado de uma correspondência superior a 85%. Considerar várias posições de mapeamento para uma read é um aspeto importante, por um lado, o número de fragmentos de DNA repetidos ao longo do genoma de várias espécies é um problema, por outro, alguns protocolos de NGS dependem da quantidade de reads mapeadas a um local (como o do ChIP-Seq). Contudo, o mapeamento incorreto pode levar a erros nos passos seguintes da análise dos dados, como a falsa deteção de polimorfismos de nucleótido único (SNPs, do inglês single nucleotide polymorphisms) e do número de cópias variantes (CNVs, do inglês copy number variants). Algumas ferramentas foram criadas orientadas para a precisão devolvendo a melhor localização para cada read, descartando os reads restantes. No entanto, outras focadas na detecção de SNPs e de variações de nucleótido único (SNVs, do inglês single nucleotide variations) têm em conta os vários locais de mapeamento, sendo que o conjunto das bases mapeadas a uma dada posição confere um grau de certeza. Por fim, da avaliação feita ao nosso protótipo para mapeamento de reads concluímos que é preciso melhorar a escalabilidade para que seja possível aplicarmos a ferramenta a conjuntos de dados reais com uma dimensão bastante superior à testada. Uma vez que utilizámos dados artificiais, tal como esperado a cobertura foi total, ou seja, todas as reads foram mapeadas à sequência de referência. As chaves de pesquisa correspondentes a partes sobrepostas das reads levaram a uma precisão perfeita — 100% das reads dos conjuntos simulados foram mapeadas ao seu local de origem na sequência de referência — e a que mais reads tenham encontrado a sua melhor posição, o que chega a ser cerca de 94% de um conjunto de dados. A versão do método de alinhamento de Needleman-Wunsch enriquecido com uma matriz de semelhança de bases conduzmais reads a descobrirem outras localizações possíveis, o que é reflectido num aumento até 7%, tendo aceite variações nucleotídicas no alinhamento. Reads reais de Escherichia coli UTI89 foram mapeadas ao seu genoma, o que nos permitiu confirmar as nossas observações sobre a escalabilidade. No entanto, apesar dos resultados obtidos com os dados artificiais, com este conjunto de dados apenas as chaves de pesquisa criadas a partir de partes sobrepostas tornaram possível que as respetivas reads encontrassem o melhor e outros possíveis locais no genoma. Estes resultados melhoraram quando se combinou o algoritmo com a versão do método de alinhamento de Needleman-Wunsch enriquecido com uma matriz de semelhança de bases, levando a que 28% das reads encontrasse a sua melhor posição e 11% outras possíveis posições. Por outro lado, quanto maior o número de chaves associado a cada read maior o número de reads mapeadas, resultando num cobertura de 100%. O trabalho futuro deverá incluir o melhoramento da escalabilidade — o que poderá incluir soluções de computação na nuvem —, a gravação dos resultados do mapeamento num ficheiro de formato SAM e a adaptação da ferramenta a reads emparelhadas, cujo mapeamento exige uma distância máxima entre elas o que torna o mapeamento mais fiável. Adicionalmente, a característica modular do nosso protótipo permite experimentar outros algoritmos, para as tarefas de criar chaves de pesquisa e alinhar as sequências, e expandir a ferramenta para outras funções, que sejam específicas da aplicação de NGS que produziu os dados (por exemplo, Bisulfite-seq). O código da implementação encontra-se disponível num repositório público1.
Mapping is a computationally expensive process, because it involves aligning a large amount of reads with a few hundreds of base to a wide reference genome (e.g., the human genome has over 3 million base-pairs). Moreover, a major challenge is to distinguish technical sequencing errors from biological variations that may occur in the sample. The work presented in this thesis aims to face the mapping challenges by developing a tool that explores and enhances hash-based approaches to increase the search space over the reference genome with the generation of multiple keys for each read, taking into account quality information and/or biological constraints in the alignment; these keys generating algorithms were combined with different read alignment strategies based in the Needleman-Wunsch method in a read mapping pipeline. Finally, we evaluated our prototype regarding scalability — the time required to be executed —, coverage — the percentage of reads that are effectively mapped — and precision — mapping reads to the correct location in the reference genome — with simulated datasets. Although in terms of scalability much work has to be done, all the algorithmic combinations led to a perfect coverage of the simulated datasets. As for precision, we observed that generating multiple keys by dividing the reads in overlapping pieces is the best approach, leading to 100% of the reads to be mapped at their original location. On the other hand, relying on a base similarity matrix to perform the alignment led to more reads discovering other possible locations, resulting in a 7% increase; this is a particularly interesting result when dealing with real datasets because of the repetitive DNA sequences and genetic variations, that may occur within the genome. We also mapped real reads of Escherichia coli UTI89 to its genome sequence, allowing us to confirm the observations about scalability, to realise that the algorithmic combination from above is more suited to find a best and other possible locations for the reads within the genome, accounting for the 28% and 11% of reads obtained respectively for each task. Moreover, by assigning more than one key to the reads we improved the coverage to 100%.
