Rozprawy doktorskie na temat „Homology search”

Genomic search tools can provide valuable insights into the chemical structure, evolutionary origin and biochemical function of genetic material. A homology search algorithm compares a protein or nucleotide query sequence to each entry in a large sequence database and reports alignments with highly similar sequences. The exponential growth of public data banks such as GenBank has necessitated the development of fast, heuristic approaches to homology search. The versatile and popular blast algorithm, developed by researchers at the US National Center for Biotechnology Information (NCBI), uses a four-stage heuristic approach to efficiently search large collections for analogous sequences while retaining a high degree of accuracy. Despite an abundance of alternative approaches to homology search, blast remains the only method to offer fast, sensitive search of large genomic collections on modern desktop hardware. As a result, the tool has found widespread use with millions of queries posed each day. A significant investment of computing resources is required to process this large volume of genomic searches and a cluster of over 200 workstations is employed by the NCBI to handle queries posed through the organisation's website. As the growth of sequence databases continues to outpace improvements in modern hardware, blast searches are becoming slower each year and novel, faster methods for sequence comparison are required. In this thesis we propose new techniques for fast yet accurate homology search that result in significantly faster blast searches. First, we describe improvements to the final, gapped alignment stages where the query and sequences from the collection are aligned to provide a fine-grain measure of similarity. We describe three new methods for aligning sequences that roughly halve the time required to perform this computationally expensive stage. Next, we investigate improvements to the first stage of search, where short regions of similarity between a pair of sequences are identified. We propose a novel deterministic finite automaton data structure that is significantly smaller than the codeword lookup table employed by ncbi-blast, resulting in improved cache performance and faster search times. We also discuss fast methods for nucleotide sequence comparison. We describe novel approaches for processing sequences that are compressed using the byte packed format already utilised by blast, where four nucleotide bases from a strand of DNA are stored in a single byte. Rather than decompress sequences to perform pairwise comparisons, our innovations permit sequences to be processed in their compressed form, four bases at a time. Our techniques roughly halve average query evaluation times for nucleotide searches with no effect on the sensitivity of blast. Finally, we present a new scheme for managing the high degree of redundancy that is prevalent in genomic collections. Near-duplicate entries in sequence data banks are highly detrimental to retrieval performance, however existing methods for managing redundancy are both slow, requiring almost ten hours to process the GenBank database, and crude, because they simply purge highly-similar sequences to reduce the level of internal redundancy. We describe a new approach for identifying near-duplicate entries that is roughly six times faster than the most successful existing approaches, and a novel approach to managing redundancy that reduces collection size and search times but still provides accurate and comprehensive search results. Our improvements to blast have been integrated into our own version of the tool. We find that our innovations more than halve average search times for nucleotide and protein searches, and have no signifcant effect on search accuracy. Given the enormous popularity of blast, this represents a very significant advance in computational methods to aid life science research.

Tato práce se zabývá vyhledáváním homologních enzymů v proteinových databázích, jejímž cílem je navrhnout nástroj poskytující takové vyhledávání. Čtenář se seznámí se základní teorií týkající se proteinů, enzymů, homologie, ale také s existujícími nástroji pro vyhledávání homologních proteinů a enzymů. Dále je popsáno ohodnocení nalezených existujících nástrojů pro vyhledávání homologních enzymů. Pro potřeby vyhodnocení byla vytvořena datová sada spolu s algoritmem pro vyhodnocení vyýsledků jednotlivých nástrojů. Další částí práce je návrh a implementace nové metody pro vyhledávání homologních enzymů společně s jejím vyhodnocením. Jsou popsány dva algoritmy (One-by-One a MSA) pro vyhledávání homologních enzymů, jejichž porovnání ukazuje, že MSA algoritmus je zanedbatelně lepší z hlediska přesnosti než One-by-One algoritmus zatímco z hlediska rychlosti vítězí One-by-One algoritmus.

Due to increasing numbers of non-coding RNA (ncRNA) being discovered recently, there is interest in identifying homologs of a given structured RNA sequence. Exhaustive homology searching for structured RNA molecules using covariance models is infeasible on genome-length sequences. Hence, heuristic methods are employed, but they largely ignore structural information in the query. We present a novel method, which uses secondary structure information, to perform homology searches for a structured RNA molecule. We define the concept of a pair seed and theoretically model alignments of random and related paired regions to compute expected sensitivity and specificity. We show that our method gives theoretical gains in sensitivity and specificity compared to a BLAST-based heuristic approach. We provide experimental verification of this gain.

We also show that pair seeds can be effectively combined with the spaced seeds approach to nucleotide homology search. The hybrid search method has theoretical specificity superior to that of the BLAST seed. We provide experimental evaluation of our hypotheses. Finally, we note that our method is easily modified to process pseudo-knotted regions in the query, something outside the scope of covariance model based methods.

In recent years there has been a growing interest in the field of non-coding RNA. This surge is a direct consequence of the discovery of a huge number of new non-coding genes, and of the finding that many of these transcripts are involved in key cellular functions. In this context, accurately detecting and comparing RNA sequences becomes extremely important. Aligning nucleotide sequences is one of the main requisite when searching for homologous genes. Accurate alignments reveal evolutionary relationships, conserved regions and more generally, any biologically relevant pattern. Comparing RNA molecules is, however, a challenging task. The nucleotide alphabet is simpler and therefore less informative than that of proteins. Moreover for many non-coding RNAs, evolution is likely to be mostly constrained at the structure level and not on the sequence level. This results in a very poor sequence conservation impeding the comparison of these molecules. These difficulties define a context where new methods are urgently needed in order to exploit experimental results at their full potential. These are the issues I have tried to address in my PhD. I have started by developing a novel algorithm able to reveal the homology relationship of distantly related ncRNA genes, and then I have applied the approach thus defined in combination with other sophisticated data mining tools to discover novel non-coding genes and generate genome-wide ncRNA predictions.
En los últimos años el interés en el campo de los ARN no codificantes ha crecido mucho a causa del enorme aumento de la cantidad de secuencias no codificantes disponibles y a que muchos de estos transcriptos han dado muestra de ser importantes en varias funciones celulares. En este contexto, es fundamental el desarrollo de métodos para la correcta detección y comparativa de secuencias de ARN. Alinear nucleótidos es uno de los enfoques principales para buscar genes homólogos, identificar relaciones evolutivas, regiones conservadas y en general, patrones biológicos importantes. Sin embargo, comparar moléculas de ARN es una tarea difícil. Esto es debido a que el alfabeto de nucleótidos es más simple y por ello menos informativo que el de las proteínas. Además es probable que para muchos ARN la evolución haya mantenido la estructura en mayor grado que la secuencia, y esto hace que las secuencias sean poco conservadas y difícilmente comparables. Por lo tanto, hacen falta nuevos métodos capaces de utilizar otras fuentes de información para generar mejores alineamientos de ARN. En esta tesis doctoral se ha intentado dar respuesta exactamente a estas temáticas. Por un lado desarrollado un nuevo algoritmo para detectar relaciones de homología entre genes de ARN no codificantes evolutivamente lejanos. Por otro lado se ha hecho minería de datos mediante el uso de datos ya disponibles para descubrir nuevos genes y generar perfiles de ARN no codificantes en todo el genoma.

Humoral and cells surface molecules of the mammalian immune system, grouped into the Immunoglobulin Gene Superfamily, share protein structure and gene sequence homologies with molecules found among diverse phylogenetic groups. In histocompatibility studies, the gorgonian coral Swiftia exserta has recently demonstrated specific alloimmunity with memory (Salter-Cid and Bigger, 1991. Biological Bulletin Vol 181). In an attempt to shed light on the origins of this gene family and the evolution of the vertebrate immune response, genomic DNA from Swiftia exserta was isolated, purified, and analyzed by Southern blot hybridization with mouse gene probes corresponding to two molecules of the Immunoglobulin Gene Superfamily, the Thy-1 antigen, and the alpha-3 domain of the MHC Class I histocompatibility marker. Hybridizations were conducted under low to non-stringent conditions to allow binding of mismatched homologs that may exist between the mouse gene probes and the Swiftia DNA. Removal of non-specific binding (sequences less than 70% homologous) occurred in washing steps. Results show that with the probes selected, the method chosen, and the conditions applied, no evidence of sequences of 70% or greater homology to the mouse Thy-1 or MHC Class I alpha-3 genes exist in Swiftia exserta genome.

Orientador : Prof. Dr. Roberto Tadeu Raittz
Coorientadores : Dra. Jeroniza Nunes Marchaukoski e Dr. Vinícius Almir Weiss
Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Educação Profissional e Tecnológica, Programa de Pós-Graduação em Bioinformática. Defesa: Curitiba, 16/09/2016
Inclui referências ao final dos capítulos
Resumo: Uma das principais análises envolvendo sequências biológicas, imprescindíveis e complexas, é a análise de homologia. A necessidade de desenvolver técnicas e ferramentas computacionais que consigam predizer com mais eficiência grupos de ortólogos e, ao mesmo tempo, lidar com grande volume de informações biológicas, ainda é um grande gargalo a ser superado pela bioinformática. Atualmente, não existe uma única ferramenta eficiente na detecção desses grupos, pois ainda requerem muito esforço computacional e tempo. Metodologias já consolidadas, como o BLAST 'todos contra todos', RBH e ferramentas como o OrthoMCL, demandam um alto custo computacional e falham quando há ortologia, necessitando de uma intervenção manual sofisticada. Diante desse cenário, neste trabalho, aprensentamos um breve review referente às técnicas, desenvolvidas entre 2011 até metade de 2017, para a detecção de ortólogos, descrevendo 12 ferramentas e contextualizando os principais problemas ainda a serem superados. A maioria das ferramentas utiliza o algoritmo BLAST como algoritmo padrão predição de homologia entre sequências. Apresentamos também uma nova abordagem para a clusterização de homólogos, a ferramenta RAFTS3groups. Para validarmos a ferramenta utilizamos como base de dados o UniProtKB/Swiss-Prot com outras ferramentas de clusterização o UCLUST e CD-HIT. RAFTS3groups mostrou-se ser mais de 4 vezes mais rápido que o CD-HIT e equiparável em volume de clusters e de tempo à ferramenta UCLUST. Para análise e consolidação de homologia, introduzimos uma nova aplicação auxiliar à ferramenta RAFTS3groups, na clusterização de ortólogos, o script DivideCluster. Comparamos com o método BLAST 'todos contra todos', analisando 9 genomas completos de Herbaspirillum spp. disponíveis no NCBI genbank. RAFTS3groups mostrou-se tão eficiente quanto o método, apresentando cerca de 96% de correlação entre os resultados de clusterização de core e pan genoma obtidos. Palavras-chave: homologia, clusterização, alignment-free, k-means, RAFTS3.
Abstract: One of the main tests involving biological sequences, essential and complex, is the analysis of homology. The study of homologous genes involved in processes such as cell cycle, DNA repair in simpler organisms, even with large evolutionary distance, there are genes that are shared between primates, yeasts and bacteria, which we call (core-genome). The need to develop computational tools and techniques that can predict more efficiently ortologs groups and handle large volume of biological information is still a problem to be resolved by Bioinformatics. We don't have a single powerful tool in detecting groups that still require a lot of effort and computing time. Tools, already consolidated, as the BLAST ' 'all-against-all' ', RBH, OrthoMCL, demand a high computational cost and fail when there is orthology, requiring manual intervention. In this scenario, in this work we presents a brief review on main techniques, developed between 2011 until early 2016, for the detection of orthologs groups, describing 12 tools and being developed currently and the main problems main problems still to be overcome. We note that most tools uses the BLAST as default prediction of homology between sequences. We also present a new approach for the analysis of homology, the RAFTS3groups tool. We use as the database UniProtKB /Swiss-Prot with the clustering tools the UCLUST and the CD-HIT. RAFTS3groups proved to be more than 4 times faster than CD-HIT and comparable in volume to clusters and time with UCLUST tool. In Homology analysis we introduced a new clustering strategy of orthology, the DivideCluster algorithm aplication built into the RAFTS3groups. Compared with the BLAST 'all-against-all', analyzing 9 complete genomes from Herbaspirillum spp. available by NCBI genbank. RAFTS3groups was shown to be as efficient as the method, showing approximately 96% of the correlation among the clustering results of core and pan genome obtained. Key-words: homology, clustering, alignment-free, k-means clustering, RAFTS3.

Non-coding RNAs are the most abundant class of RNAs found throughout genomes. These RNAs are key players of gene regulation and thus, the func- tion of whole organisms. Numerous methods have been developed so far for detecting novel classes of ncRNAs or finding homologs to the known ones. Because of their abundance, the sequence availability of these RNAs is rapidly increasing, as is the case for example for microRNAs. However, for classes of them, still only incomplete information is available, invertebrates 7SK snRNA for instance. Consequently, a lot of false positive outputs are produced in the former case, and more accurate annotation methods are needed for the latter cases to improve derivable knowledge. This makes the accuracy of gathering correct homologs a challenging task and it leads directly to a not less important problem, the curation of these data. Finding solutions for the aforementioned problems is more complex than one would expect as these RNAs are characterized not only by sequences informa- tion but also structure information, in addition to distinct biological features. In this work, data curation methods and sensitive homology search are shown as complementary methods to solve these problems. A careful curation and annotation method revealed new structural information in the invertebrates 7SK snRNA, which pushes the investigation in the area forward. This has been reflected by detecting new high potential 7SK RNA genes in different invertebrates groups. Moreover, the gaps between homology search and well- curated data on the one side, and between experimental and computational outputs on the other side, are closed. These gaps were bridged by a curation method applied to the microRNA data, which was then turned into a com- prehensive workflow implemented into an automated pipeline. MIRfix is a microRNA curation pipeline considering the detailed sequence and structure information of the metazoan microRNAs, together with biological features related to the microRNA biogenesis. Moreover, this pipeline can be integrated into existing methods and tools related to microRNA homology search and data curation. The application of this pipeline on the biggest open source microRNA database revealed its high capacity in detecting wrong annotated pre-miRNA, eventually improving alignment quality of the majority of the available data. Additionally, it was tested with artificial datasets highlighting the high accuracy in predicting the pre-miRNA components, miRNA and miRNA*.:Chapter 1: Introduction Chapter 2: Biological and Computational background 2.1 Biology 2.1.1 Non-coding RNAs 2.1.2 RNA secondary structure 2.1.3 Homology versus similarity 2.1.4 Evolution 2.2 The role of computational biology 2.2.1 Alignment 2.2.1.1 Pairwise alignment 2.2.1.2 Multiple sequence alignment (MSA) 2.2.2 Homology search 2.2.2.1 Sequence-based 2.2.2.2 Structure-based 2.2.3 RNA secondary structure prediction Chapter 3: Careful curation for snRNA 3.1 Biological background 3.2 Introduction to the problem 3.3 Methods 3.3.1 Initial seeds and models construction 3.3.2 Models anatomy then merging 3.4 Results 3.4.1 Refined model of arthropod 7SK RNA 3.4.1.1 5’ Stem 3.4.1.2 Extension of Stem A 3.4.1.3 Novel stem B in invertebrates 3.4.1.4 3’ Stem 3.4.2 Invertebrates model conserves the HEXIM1 binding site 3.4.3 Computationally high potential 7SK RNA candidate . 3.4.4 Sensitivity of the final proposed model 3.5 Conclusion Chapter 4: Behind the scenes of microRNA driven regulation 4.1 Biological background 4.2 Databases and problems 4.3 MicroRNA detection and curation approaches Chapter 5: Initial microRNA curation 5.1 Introduction 5.2 Methods 5.2.1 Data pre-processing 5.2.2 Initial seeds creation 5.2.3 Main course 5.3 Results and discussion 5.4 Conclusion Chapter 6: MIRfix pipeline 6.1 Introduction 6.2 Methods 6.2.1 Inputs and Outputs 6.2.2 Prediction of the mature sequences 6.2.3 The original precursor and its alternative 6.2.4 The validation of the precursor 6.2.5 Alignment processing 6.3 Results and statistics 6.4 Applications 6.4.1 Real life examples and artificial data tests 6.4.2 miRNA and miRNA* prediction 6.4.3 Covariance models 6.5 Conclusion Chapter 7: Discussion

In the field of proteomic mass spectrometry, proteins can be sequenced by two independent yet complementary algorithms: de novo sequencing which uses no prior knowledge and database search which relies upon existing protein databases. In the case where an organism’s protein database is not available, the software Spider was developed in order to search sequence tags produced by de novo sequencing against a database from a related organism while accounting for both errors in the sequence tags and mutations. This thesis further develops Spider by using the concept of reconstruction in order to predict the real sequence by considering both the sequence tags and their matched homologous peptides. The significant value of these reconstructed sequences is demonstrated. Additionally, the runtime is greatly reduced and separated into independent caching and matching steps. This new approach allows for the development of an efficient algorithm for search. In addition, the algorithm’s output can be used for new applications. This is illustrated by a contribution to a complete protein sequencing application.

The 7SK small nuclear RNA (snRNA) is a key player in the regulation of polymerase (pol) II transcription. The 7SK RNA was long believed to be specific to vertebrates where it is highly conserved. Homologs in basal deuterostomes and a few lophotrochozoan species were only recently reported. On longer timescales, 7SK evolves rapidly with only few conserved sequence and structure motifs. Previous attempts to identify the Drosophila homolog thus have remained unsuccessful despite considerable efforts. Here we report on the discovery of arthropod 7SK RNAs using a novel search strategy based on pol III promoters, as well as the subsequent verification of its expression. Our results demonstrate that a 7SK snRNA featuring 2 highly structured conserved domains was present already in the bilaterian ancestor.

A detailed annotation of non-protein coding RNAs is typically missing in initial releases of newly sequenced genomes. Here we report on a comprehensive ncRNA annotation of the genome of Trichoplax adhaerens, the presumably most basal metazoan whose genome has been published to-date. Since blast identified only a small fraction of the best-conserved ncRNAs—in particular rRNAs, tRNAs and some snRNAs—we developed a semi-global dynamic programming tool, GotohScan, to increase the sensitivity of the homology search. It successfully identified the full complement of major and minor spliceosomal snRNAs, the genes for RNase P and MRP RNAs, the SRP RNA, as well as several small nucleolar RNAs. We did not find any microRNA candidates homologous to known eumetazoan sequences. Interestingly, most ncRNAs, including the pol-III transcripts, appear as single-copy genes or with very small copy numbers in the Trichoplax genome.