Proteinortho: detection of (co-)orthologs in large-scale analysis.

Lechner M, Findeiss S, Steiner L, Marz M, Stadler PF, Prohaska SJ. · 2011

Read Proteinortho: detection of (co-)orthologs in large-scale analysis. by Lechner M, Findeiss S, Steiner L, Marz M, Stadler PF, Prohaska SJ. (2011) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc3114741.txt.

Introduction

Marcus Lechner and colleagues presented a computer program for finding matching genes across species in a 2011 paper in BMC Bioinformatics. Matching genes inherited from a shared ancestor help researchers compare genomes and guess gene function. With genome counts rising fast, older tools needed too much memory for the job.

Their program refines a best-match search method and spreads work across the cores of ordinary computers, cutting memory needs sharply. Tested on more than seven hundred bacterial genomes, it found a small set of proteins present in nearly every one of them. Because it runs on standard hardware, labs can compute fresh matches for their own data instead of waiting for database updates.

Catalog record

CREATORLechner M, Findeiss S, Steiner L, Marz M, Stadler PF, Prohaska SJ.
YEAR2011
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC3114741

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Proteinortho: Detection of (Co-)orthologs in large-scale analysis By Marcus Lechner, Sven Findeiß, Lydia Steiner, Manja Marz, Peter F Stadler, Sonja J Prohaska Published in: BMC Bioinformatics DOI: 10.1186/1471-2105-12-124 ABSTRACT Background Orthology analysis is an important part of data analysis in many areas of bioinformatics such as comparative genomics and molecular phylogenetics. The ever-increasing flood of sequence data, and hence the rapidly increasing number of genomes that can be compared simultaneously, calls for efficient software tools as brute-force approaches with quadratic memory requirements become infeasible in practise. The rapid pace at which new data become available, furthermore, makes it desirable to compute genome-wide orthology relations for a given dataset rather than relying on relations listed in databases. Results The program Proteinortho described here is a stand-alone tool that is geared towards large datasets and makes use of distributed computing techniques when run on multi-core hardware. It implements an extended version of the reciprocal best alignment heuristic. We apply Proteinortho to compute orthologous proteins in the complete set of all 717 eubacterial genomes available at NCBI at the beginning of 2009. We identified thirty proteins present in 99% of all bacterial proteomes. Conclusions Proteinortho significantly reduces the required amount of memory for orthology analysis compared to existing tools, allowing such computations to be performed on off-the-shelf hardware. BACKGROUND Genome annotation largely depends on the determination of sequence intervals that are homologous, and if possible, orthologous to sequences of known identity and function in related genomes. Orthologous genes (orthologs) are derived from a common ancestor by a speciation event [1]. Orthologs are of particular interest because they can be expected to have maintained at least part of their (ancestral) biological function. For protein-coding genes, several well-known databases, including InParanoid[2], OrthoMCL-DB[3], COG-database[4], Homogene[5], eggNOG[6], OMA Browser[7] and Ensembl Compara[8] compile such information. Their content is restricted to data previously published in comprehensive databases of protein sequences such as UniProt[9]. Updates with additional proteomic data thus are published relatively infrequently. Modern high-throughput technologies, however, produce huge amounts of protein data and even larger amounts of transcript data that are computationally translated to putative polypeptide sequences. Oftentimes, therefore, it would be desirable to generate the orthology relation for a particular dataset, so that the availability of orthology data does not limit the set of species or genes that can be included. The computation of genome-wide orthology data, however, is a challenging and time consuming task with the currently available tools. In many cases, orthologs cannot be identified unambiguously by means of sequence comparison. The main difficulty arises from the presence of paralogs (homologous genes within the same genome) which can make it very difficult to recognize the correct ortholog among the other homologs. Gene duplications following the speciation, furthermore, create two or more genes in one lineage that are, collectively, orthologous to one or more genes in another lineage. Such genes are known as co-orthologs [10]. The most widely used approach to identify (putative) orthologs between two species is the reciprocal best alignment heuristic [11-15]. This approach was more recently extended e.g. in OrthoMCL[16] and MultiParanoid[17] to detect (co-)orthologs within multiple species. All these tools, however, are limited to relatively small sets of species. In practise, analyzing the complete proteomes of more than about 50 prokaryote species goes beyond the capabilities of standard hardware and requires access to supercomputer resources. This limitation arises from both, technical issues such as insufficient parallelization and the algorithmic design that requires all reasonable alignments for each input protein to be held in the memory for efficient access in the clustering stage. Proteinortho is specifically designed to deal with hundreds of species together containing millions of proteins. It achieves this performance both by optimizing the implementation and by modifying the reciprocal best alignment method in a way that allows alignment processing on the fly. RESULTS AND DISCUSSION Orthology prediction Theory As for other approaches to large-scale orthology detection, the starting point is a complete collection of pairwise comparisons, typically performed using blast. For simplicity of presentation, we assume that the individual sequences that are compared represent proteins, although algorithms and pipelines are applicable also to other sequence data such as non-coding RNA genes or conserved DNA regions. Typically, the results of pairwise comparisons are ranked by similarity, for instance based on blast statistics, evolutionary distances, or genome rearrangement analysis [7,16,18]. High-ranking alignments across multiple species then have to be combined in order to determine orthologous groups. However, these groups usually do not readily provide detailed insights since they can contain large numbers of related genes for each species. Hence, meaningful units have to be identified. For this purpose, a variety of clustering algorithms has been applied to determine Clusters of Orthologous Groups (COGs). The MCL-algorithm for instance uses a stochastic flow simulation to determine meaningful COGs [16,19,20]. In addition, MultiParanoid explicitly searches and tags in-paralogs, i.e., recent paralogs that represent species-specific gene expansions. This strategy requires to directly compare proteins within each species. Alternatively, data were curated by manual postprocessing [4]. We will argue here that orthology determination can be understood as the problem of finding nearly disjoint maximal nearly-complete multipartite subgraphs in an edge-weighted directed graph whose vertices are the proteins in the input set, and whose edges connect certain pairs of similar proteins of different species. The edge weights ωx→y encode the similarity of x and y. In our implementation, the bit score of the blast alignment (x → y) will serve as edge weight. An E-value cut-off is used beyond which blast alignments are not included into . In order to motivate our point of view, we first consider an idealized dataset (see Figure 1) in which (1) each protein x (from species A) has at most one ortholog in any other species B ≠ A, (2) if y ∈ B is an ortholog of x ∈ A, then a blast search of x against B yields at least one alignment and (3) the unique best alignment of query x against B is the true ortholog y of x. In this case, the well-know "reciprocal best alignment heuristic" (RBAH), also known as "reciprocal best hits" (RBH) [11], can be used to retrieve the correct ortholog set. To see this, we construct a subgraph of as follows: For each protein x in species A and a given species B ≠ A we retain only the arc with maximal weight:(1) [Figure: Orthology relations. Idealized dataset for two species A and B. Proteins x ∈ A and y ∈ B are depicted by open boxes. Orthology relations between proteins x and y are represented by grey shadows. Arrows indicate alignments above a certain cut-off from the search of x against B. Solid lines refer to the best alignments. Cases (1), (2), and (3) cannot occur by definition in an idealized dataset, but of course do appear in real life applications.] The symmetric subgraph of , containing only reciprocal best alignments, can be regarded as an undirected graph ϒRBAH. By construction, any two vertices are connected by edges in ϒRBAH if and only if they are orthologs. A set of orthologs therefore corresponds to a complete multipartite subgraph of in which every species is represented at most once. Furthermore, we note that

Read the complete text