Search

The quest for understanding how proteins evolve and function has been a prominent and costly human endeavor. With advances in genomics and use of bioinformatics tools, the diversity of proteins in present day genomes can now be studied more efficiently than ever before. This thesis describes computational methods suitable for large-scale protein classification of many proteomes of diverse species. Specifically, we focus on methods that combine unsupervised learning (clustering) techniques with the knowledge of molecular phylogenetics, particularly that of orthology. In chapter 1 we introduce the biological context of protein structure, function and evolution, review the state-of-the-art sequence-based protein classification methods, and then describe methods used to validate the predictions. Finally, we present the outline and objectives of this thesis. Evolutionary (phylogenetic) concepts are instrumental in studying subjects as diverse as the diversity of genomes, cellular networks, protein structures and functions, and functional genome annotation. In particular, the detection of orthologous proteins (genes) across genomes provides reliable means to infer biological functions and processes from one organism to another. Chapter 2 evaluates the available computational tools, such as algorithms and databases, used to infer orthologous relationships between genes from fully sequenced genomes. We discuss the main caveats of large-scale orthology detection in general as well as the merits and pitfalls of each method in particular. We argue that establishing true orthologous relationships requires a phylogenetic approach which combines both trees and graphs (networks), reliable species phylogeny, genomic data for more than two species, and an insight into the processes of molecular evolution. Also proposed is a set of guidelines to aid researchers in selecting the correct tool. Moreover, this review motivates further research in developing reliable and scalable methods for functional and phylogenetic classification of large protein collections. Chapter 3 proposes a framework in which various protein knowledge-bases are combined into unique network of mappings (links), and hence allows comparisons to be made between expert curated and fully-automated protein classifications from a single entry point. We developed an integrated annotation resource for protein orthology, ProGMap (Protein Group Mappings, http://www.bioinformatics.nl/progmap), to help researchers and database annotators who often need to assess the coherence of proposed annotations and/or group assignments, as well as users of high throughput methodologies (e.g., microarrays or proteomics) who deal with partially annotated genomic data. ProGMap is based on a non-redundant dataset of over 6.6 million protein sequences which is mapped to 240,000 protein group descriptions collected from UniProt, RefSeq, Ensembl, COG, KOG, OrthoMCL-DB, HomoloGene, TRIBES and PIRSF using a fast and fully automated sequence-based mapping approach. The ProGMap database is equipped with a web interface that enables queries to be made using synonymous sequence identifiers, gene symbols, protein functions, and amino acid or nucleotide sequences. It incorporates also services, namely BLAST similarity search and QuickMatch identity search, for finding sequences similar (or identical) to a query sequence, and tools for presenting the results in graphic form. Graphs (networks) have gained an increasing attention in contemporary biology because they have enabled complex biological systems and processes to be modeled and better understood. For example, protein similarity networks constructed of all-versus-all sequence comparisons are frequently used to delineate similarity groups, such as protein families or orthologous groups in comparative genomics studies. Chapter 4.1 presents a benchmark study of freely available graph software used for this purpose. Specifically, the computational complexity of the programs is investigated using both simulated and biological networks. We show that most available software is not suitable for large networks, such as those encountered in large-scale proteome analyzes, because of the high demands on computational resources. To address this, we developed a fast and memory-efficient graph software, netclust (http://www.bioinformatics.nl/netclust/), which can scale to large protein networks, such as those constructed of millions of proteins and sequence similarities, on a standard computer. An extended version of this program called Multi-netclust is presented in chapter 4.2. This tool that can find connected clusters of data presented by different network data sets. It uses user-defined threshold values to combine the data sets in such a way that clusters connected in all or in either of the networks can be retrieved efficiently. Automated protein sequence clustering is an important task in genome annotation projects and phylogenomic studies. During the past years, several protein clustering programs have been developed for delineating protein families or orthologous groups from large sequence collections. However, most of these programs have not been benchmarked systematically, in particular with respect to the trade-off between computational complexity and biological soundness. In chapter 5 we evaluate three best known algorithms on different protein similarity networks and validation (or 'gold' standard) data sets to find out which one can scale to hundreds of proteomes and still delineate high quality similarity groups at the minimum computational cost. For this, a reliable partition-based approach was used to assess the biological soundness of predicted groups using known protein functions, manually curated protein/domain families and orthologous groups available in expert-curated databases. Our benchmark results support the view that a simple and computationally cheap method such as netclust can perform similar to and in cases even better than more sophisticated, yet much more costly methods. Moreover, we introduce an efficient graph-based method that can delineate protein orthologs of hundreds of proteomes into hierarchical similarity groups de novo. The validity of this method is demonstrated on data obtained from 347 prokaryotic proteomes. The resulting hierarchical protein classification is not only in agreement with manually curated classifications but also provides an enriched framework in which the functional and evolutionary relationships between proteins can be studied at various levels of specificity. Finally, in chapter 6 we summarize the main findings and discuss the merits and shortcomings of the methods developed herein. We also propose directions for future research. The ever increasing flood of new sequence data makes it clear that we need improved tools to be able to handle and extract relevant (orthological) information from these protein data. This thesis summarizes these needs and how they can be addressed by the available tools, or be improved by the new tools that were developed in the course of this research.

The quest for understanding how proteins evolve and function has been a prominent and costly human endeavor. With advances in genomics and use of bioinformatics tools, the diversity of proteins in present day genomes can now be studied more efficiently than ever before. This thesis describes computational methods suitable for large-scale protein classification of many proteomes of diverse species. Specifically, we focus on methods that combine unsupervised learning (clustering) techniques with the knowledge of molecular phylogenetics, particularly that of orthology. In chapter 1 we introduce the biological context of protein structure, function and evolution, review the state-of-the-art sequence-based protein classification methods, and then describe methods used to validate the predictions. Finally, we present the outline and objectives of this thesis. Evolutionary (phylogenetic) concepts are instrumental in studying subjects as diverse as the diversity of genomes, cellular networks, protein structures and functions, and functional genome annotation. In particular, the detection of orthologous proteins (genes) across genomes provides reliable means to infer biological functions and processes from one organism to another. Chapter 2 evaluates the available computational tools, such as algorithms and databases, used to infer orthologous relationships between genes from fully sequenced genomes. We discuss the main caveats of large-scale orthology detection in general as well as the merits and pitfalls of each method in particular. We argue that establishing true orthologous relationships requires a phylogenetic approach which combines both trees and graphs (networks), reliable species phylogeny, genomic data for more than two species, and an insight into the processes of molecular evolution. Also proposed is a set of guidelines to aid researchers in selecting the correct tool. Moreover, this review motivates further research in developing reliable and scalable methods for functional and phylogenetic classification of large protein collections. Chapter 3 proposes a framework in which various protein knowledge-bases are combined into unique network of mappings (links), and hence allows comparisons to be made between expert curated and fully-automated protein classifications from a single entry point. We developed an integrated annotation resource for protein orthology, ProGMap (Protein Group Mappings, http://www.bioinformatics.nl/progmap), to help researchers and database annotators who often need to assess the coherence of proposed annotations and/or group assignments, as well as users of high throughput methodologies (e.g., microarrays or proteomics) who deal with partially annotated genomic data. ProGMap is based on a non-redundant dataset of over 6.6 million protein sequences which is mapped to 240,000 protein group descriptions collected from UniProt, RefSeq, Ensembl, COG, KOG, OrthoMCL-DB, HomoloGene, TRIBES and PIRSF using a fast and fully automated sequence-based mapping approach. The ProGMap database is equipped with a web interface that enables queries to be made using synonymous sequence identifiers, gene symbols, protein functions, and amino acid or nucleotide sequences. It incorporates also services, namely BLAST similarity search and QuickMatch identity search, for finding sequences similar (or identical) to a query sequence, and tools for presenting the results in graphic form. Graphs (networks) have gained an increasing attention in contemporary biology because they have enabled complex biological systems and processes to be modeled and better understood. For example, protein similarity networks constructed of all-versus-all sequence comparisons are frequently used to delineate similarity groups, such as protein families or orthologous groups in comparative genomics studies. Chapter 4.1 presents a benchmark study of freely available graph software used for this purpose. Specifically, the computational complexity of the programs is investigated using both simulated and biological networks. We show that most available software is not suitable for large networks, such as those encountered in large-scale proteome analyzes, because of the high demands on computational resources. To address this, we developed a fast and memory-efficient graph software, netclust (http://www.bioinformatics.nl/netclust/), which can scale to large protein networks, such as those constructed of millions of proteins and sequence similarities, on a standard computer. An extended version of this program called Multi-netclust is presented in chapter 4.2. This tool that can find connected clusters of data presented by different network data sets. It uses user-defined threshold values to combine the data sets in such a way that clusters connected in all or in either of the networks can be retrieved efficiently. Automated protein sequence clustering is an important task in genome annotation projects and phylogenomic studies. During the past years, several protein clustering programs have been developed for delineating protein families or orthologous groups from large sequence collections. However, most of these programs have not been benchmarked systematically, in particular with respect to the trade-off between computational complexity and biological soundness. In chapter 5 we evaluate three best known algorithms on different protein similarity networks and validation (or 'gold' standard) data sets to find out which one can scale to hundreds of proteomes and still delineate high quality similarity groups at the minimum computational cost. For this, a reliable partition-based approach was used to assess the biological soundness of predicted groups using known protein functions, manually curated protein/domain families and orthologous groups available in expert-curated databases. Our benchmark results support the view that a simple and computationally cheap method such as netclust can perform similar to and in cases even better than more sophisticated, yet much more costly methods. Moreover, we introduce an efficient graph-based method that can delineate protein orthologs of hundreds of proteomes into hierarchical similarity groups de novo. The validity of this method is demonstrated on data obtained from 347 prokaryotic proteomes. The resulting hierarchical protein classification is not only in agreement with manually curated classifications but also provides an enriched framework in which the functional and evolutionary relationships between proteins can be studied at various levels of specificity. Finally, in chapter 6 we summarize the main findings and discuss the merits and shortcomings of the methods developed herein. We also propose directions for future research. The ever increasing flood of new sequence data makes it clear that we need improved tools to be able to handle and extract relevant (orthological) information from these protein data. This thesis summarizes these needs and how they can be addressed by the available tools, or be improved by the new tools that were developed in the course of this research.

In this thesis we describe different approaches aiding in the utilization of the exponentially growing amount of information available in the life sciences. Briefly, we address two issues in molecular biology, on sequence analysis, and on text mining. The former issue addresses the problem how to determine remote sequence homology especially when the sequence similarity is very low. For this a visualisation tool is introduced that combines sequence alignment, domain prediction and phylogeny. The second topic on text mining centres on the question how to unambiguously formulate queries for efficient information retrieval. It tackles the problem of gene nomenclature — one in two gene symbols being ambiguous - by introducing a new text-clustering- and taxonomy-based disambiguation methodology.

In this thesis we describe different approaches aiding in the utilization of the exponentially growing amount of information available in the life sciences. Briefly, we address two issues in molecular biology, on sequence analysis, and on text mining. The former issue addresses the problem how to determine remote sequence homology especially when the sequence similarity is very low. For this a visualisation tool is introduced that combines sequence alignment, domain prediction and phylogeny. The second topic on text mining centres on the question how to unambiguously formulate queries for efficient information retrieval. It tackles the problem of gene nomenclature — one in two gene symbols being ambiguous - by introducing a new text-clustering- and taxonomy-based disambiguation methodology.

The thesis focuses on two bioinformatics research topics: the development of tools for an efficient and reliable identification of single nucleotides polymorphisms (SNPs) and polymorphic simple sequence repeats (SSRs) from expressed sequence tags (ESTs) (Chapter 2, 3 and 4), and the subsequent implementation of these tools in a pipeline for narrowing down QTL intervals to facilitate the identification of candidate genes for the QTL (Chapter 5). Chapter 1 provides an introduction to molecular markers, SNP and SSR markers, illustrated by a number of applications of molecular markers, as well as existing programs for their detection. After analysis of existing problems and programs for the detection SNPs, a new algorithm is described to reliably identify SNPs and indels in EST data from diploid and polyploid species (Chapter 2). The algorithm is implemented in a program called QualitySNP. This program uses three filters to identify reliable SNPs: filter one screens for potential SNPs by requiring at least two sequences per represented allele; filter two uses a haplotype-based strategy to filter out clusters with paralogs and false SNPs caused by sequence errors; finally, filter three calculates a confidence score for every putative SNP according to the number of occurrences of each allele in high and low quality regions. For the detection of non-synonymous SNPs (nsSNP), synonymous SNPs and SNPs in UTRs, a program was developed as well. Furthermore, these programs were implemented in a pipeline that includes the identification of SNPs and nsSNPs, as well as a storage and retrieval system. Using this pipeline, large numbers of SNPs could be identified in potato ESTs. QualitySNP is available for running on LINUX and UNIX systems; the program, user manual and examples are available at http://www.bioinformatics.nl/tools/snpweb/ . Chapter 3 describes a web-based implementation of the QualitySNP algorithm, called HaploSNPer, which is a tool for the detection of alleles and SNPs in user-specified input sequences from both diploid and polyploid species. HaploSNPer tries to find homologous sequences in user-specified sequence databases using a user-supplied seed sequence, or in a collection of input sequences. All alleles and associated SNPs are identified on clusters of these homologous sequences using QualitySNP. HaploSNPer provides a user-friendly interface for visualization of SNPs and alleles, which allows the selection of informative SNPs and allele specific makers. Currently HaploSNPer is available for nine animal and thirteen plant species, and is available from http://www.bioinformatics.nl/tools/haplosnper/ . Chapter 4 presents a new tool, called PolySSR, to identify polymorphic SSRs rather than just SSRs based on public EST sequence data derived from heterozygotes and/or different genotypes. Based on PolySSR a pipeline was developed to automatically develop primers for putatively polymorphic SSR markers, taking into account SNPs in the SSR flanking regions, thus improving the success rate of the potential markers. Furthermore, SSR positions in coding or UTR regions of genes are identified by the pipeline. The pipeline also includes a searchable database for these SSRs. The value of PolySSR was demonstrated by the fact that nearly all tested SSRs predicted to be polymorphic were indeed validated as polymorphic, and also most designed primers produced clear amplicons. Large numbers of polymorphic SSRs were identified from publicly available ESTs in potato, tomato, rice, Arabidopsis, brassica and chicken using the pipeline. They are stored into a database, which is available at http://www.bioinformatics.nl/tools/polyssr/ . PolySSR not only decreases the cost of designing and testing primers, it also brings a new approach to use the redundancy and heterozygosity of ESTs for developing SSRs that was ignored before. Analysis of the data obtained with polySSR showed that a larger percentage of short SSRs identified in the species used in the study were polymorphic than that of long SSRs. From this it is clear that in the past we have ‘forgotten’ a whole class of putatively informative markers. QualitySNP and PolySSR have been implemented into a pipeline called GeneTagger to find candidate genes underlying a QTL using the strategy of narrowing the QTL interval (Chapter 5). The pipeline first detects the syntenic region of a QTL interval in the species under study in a model species based on marker sequences linked to the QTL. Next, within the syntenic regions identified in the model species genes are identified that might have a function related to the QTL or genes within the regions that are not part of a large gene family. Based on their map position in the model species a number of genes are selected for marker development. To facilitate marker development, ESTs derived from the target species are analyzed using QualitySNP, PolySSR and other tools. Based on identified genetic variations in the selected genes, molecular markers can be developed for accurate fine-mapping of the QTL and ultimately identification of the gene underlying the QTL effect. The pipeline has been used to narrow the clubroot resistance QTL. The tool is available from the website http://www.bioinformatics.nl/tools/genetagger/ . Finally, merits and shortcomings of the tools that have been developed as well as related bioinformatics questions that arose during these studies are discussed in Chapter 6.

The thesis focuses on two bioinformatics research topics: the development of tools for an efficient and reliable identification of single nucleotides polymorphisms (SNPs) and polymorphic simple sequence repeats (SSRs) from expressed sequence tags (ESTs) (Chapter 2, 3 and 4), and the subsequent implementation of these tools in a pipeline for narrowing down QTL intervals to facilitate the identification of candidate genes for the QTL (Chapter 5). Chapter 1 provides an introduction to molecular markers, SNP and SSR markers, illustrated by a number of applications of molecular markers, as well as existing programs for their detection. After analysis of existing problems and programs for the detection SNPs, a new algorithm is described to reliably identify SNPs and indels in EST data from diploid and polyploid species (Chapter 2). The algorithm is implemented in a program called QualitySNP. This program uses three filters to identify reliable SNPs: filter one screens for potential SNPs by requiring at least two sequences per represented allele; filter two uses a haplotype-based strategy to filter out clusters with paralogs and false SNPs caused by sequence errors; finally, filter three calculates a confidence score for every putative SNP according to the number of occurrences of each allele in high and low quality regions. For the detection of non-synonymous SNPs (nsSNP), synonymous SNPs and SNPs in UTRs, a program was developed as well. Furthermore, these programs were implemented in a pipeline that includes the identification of SNPs and nsSNPs, as well as a storage and retrieval system. Using this pipeline, large numbers of SNPs could be identified in potato ESTs. QualitySNP is available for running on LINUX and UNIX systems; the program, user manual and examples are available at http://www.bioinformatics.nl/tools/snpweb/ . Chapter 3 describes a web-based implementation of the QualitySNP algorithm, called HaploSNPer, which is a tool for the detection of alleles and SNPs in user-specified input sequences from both diploid and polyploid species. HaploSNPer tries to find homologous sequences in user-specified sequence databases using a user-supplied seed sequence, or in a collection of input sequences. All alleles and associated SNPs are identified on clusters of these homologous sequences using QualitySNP. HaploSNPer provides a user-friendly interface for visualization of SNPs and alleles, which allows the selection of informative SNPs and allele specific makers. Currently HaploSNPer is available for nine animal and thirteen plant species, and is available from http://www.bioinformatics.nl/tools/haplosnper/ . Chapter 4 presents a new tool, called PolySSR, to identify polymorphic SSRs rather than just SSRs based on public EST sequence data derived from heterozygotes and/or different genotypes. Based on PolySSR a pipeline was developed to automatically develop primers for putatively polymorphic SSR markers, taking into account SNPs in the SSR flanking regions, thus improving the success rate of the potential markers. Furthermore, SSR positions in coding or UTR regions of genes are identified by the pipeline. The pipeline also includes a searchable database for these SSRs. The value of PolySSR was demonstrated by the fact that nearly all tested SSRs predicted to be polymorphic were indeed validated as polymorphic, and also most designed primers produced clear amplicons. Large numbers of polymorphic SSRs were identified from publicly available ESTs in potato, tomato, rice, Arabidopsis, brassica and chicken using the pipeline. They are stored into a database, which is available at http://www.bioinformatics.nl/tools/polyssr/ . PolySSR not only decreases the cost of designing and testing primers, it also brings a new approach to use the redundancy and heterozygosity of ESTs for developing SSRs that was ignored before. Analysis of the data obtained with polySSR showed that a larger percentage of short SSRs identified in the species used in the study were polymorphic than that of long SSRs. From this it is clear that in the past we have ‘forgotten’ a whole class of putatively informative markers. QualitySNP and PolySSR have been implemented into a pipeline called GeneTagger to find candidate genes underlying a QTL using the strategy of narrowing the QTL interval (Chapter 5). The pipeline first detects the syntenic region of a QTL interval in the species under study in a model species based on marker sequences linked to the QTL. Next, within the syntenic regions identified in the model species genes are identified that might have a function related to the QTL or genes within the regions that are not part of a large gene family. Based on their map position in the model species a number of genes are selected for marker development. To facilitate marker development, ESTs derived from the target species are analyzed using QualitySNP, PolySSR and other tools. Based on identified genetic variations in the selected genes, molecular markers can be developed for accurate fine-mapping of the QTL and ultimately identification of the gene underlying the QTL effect. The pipeline has been used to narrow the clubroot resistance QTL. The tool is available from the website http://www.bioinformatics.nl/tools/genetagger/ . Finally, merits and shortcomings of the tools that have been developed as well as related bioinformatics questions that arose during these studies are discussed in Chapter 6.