MOTIVATION: Accurate orthology inference is a fundamental step in many phylogenetics and comparative analysis. Many methods have been proposed, including OMA (Orthologous MAtrix). Yet substantial challenges remain, in particular in coping with fragmented genes or genes evolving at different rates after duplication, and in scaling to large datasets. With more and more genomes available, it is necessary to improve the scalability and robustness of orthology inference methods. RESULTS: We present improvements in the OMA algorithm: (i) refining the pairwise orthology inference step to account for same-species paralogs evolving at different rates, and (ii) minimizing errors in the pairwise orthology verification step by testing the consistency of pairwise distance estimates, which can be problematic in the presence of fragmentary sequences. In addition we introduce a more scalable procedure for hierarchical orthologous group (HOG) clustering, which are several orders of magnitude faster on large datasets. Using the Quest for Orthologs consortium orthology benchmark service, we show that these changes translate into substantial improvement on multiple empirical datasets. AVAILABILITY AND IMPLEMENTATION: This new OMA 2.0 algorithm is used in the OMA database ( http://omabrowser.org ) from the March 2017 release onwards, and can be run on custom genomes using OMA standalone version 2.0 and above ( http://omabrowser.org/standalone ). CONTACT: [email protected] or [email protected].

BACKGROUND: We analyze phylogenetic tree building methods from molecular sequences (PTMS). These are methods which base their construction solely on sequences, coding DNA or amino acids. RESULTS: Our first result is a statistically significant evaluation of 176 PTMSs done by comparing trees derived from 193138 orthologous groups of proteins using a new measure of quality between trees. This new measure, called the Intra measure, is very consistent between different groups of species and strong in the sense that it separates the methods with high confidence. The second result is the comparison of the trees against trees derived from accepted taxonomies, the Taxon measure. We consider the NCBI taxonomic classification and their derived topologies as the most accepted biological consensus on phylogenies, which are also available in electronic form. The correlation between the two measures is remarkably high, which supports both measures simultaneously. CONCLUSIONS: The big surprise of the evaluation is that the maximum likelihood methods do not score well, minimal evolution distance methods over MSA-induced alignments score consistently better. This comparison also allows us to rank different components of the tree building methods, like MSAs, substitution matrices, ML tree builders, distance methods, etc. It is also clear that there is a difference between Metazoa and the rest, which points out to evolution leaving different molecular traces. We also think that these measures of quality of trees will motivate the design of new PTMSs as it is now easier to evaluate them with certainty.

Since the publication of our article (Roth, Gonnet, and Dessimoz: BMC Bioinformatics 2008 9: 518), we have noticed several errors, which we correct in the following.

BACKGROUND: OMA is a project that aims to identify orthologs within publicly available, complete genomes. With 657 genomes analyzed to date, OMA is one of the largest projects of its kind. RESULTS: The algorithm of OMA improves upon standard bidirectional best-hit approach in several respects: it uses evolutionary distances instead of scores, considers distance inference uncertainty, includes many-to-many orthologous relations, and accounts for differential gene losses. Herein, we describe in detail the algorithm for inference of orthology and provide the rationale for parameter selection through multiple tests. CONCLUSION: OMA contains several novel improvement ideas for orthology inference and provides a unique dataset of large-scale orthology assignments.

MOTIVATION: Inference of the evolutionary relation between proteins, in particular the identification of orthologs, is a central problem in comparative genomics. Several large-scale efforts with various methodologies and scope tackle this problem, including OMA (the Orthologous MAtrix project). RESULTS: Based on the results of the OMA project, we introduce here the OMA Browser, a web-based tool allowing the exploration of orthologous relations over 352 complete genomes. Orthologs can be viewed as groups across species, but also at the level of sequence pairs, allowing the distinction among one-to-one, one-to-many and many-to-many orthologs. AVAILABILITY: http://omabrowser.org.

In recent years the phylogenetic relationship of mammalian orders has been addressed in a number of molecular studies. These analyses have frequently yielded inconsistent results with respect to some basal ordinal relationships. For example, the relative placement of primates, rodents, and carnivores has differed in various studies. Here, we attempt to resolve this phylogenetic problem by using data from completely sequenced nuclear genomes to base the analyses on the largest possible amount of data. To minimize the risk of reconstruction artifacts, the trees were reconstructed under different criteria-distance, parsimony, and likelihood. For the distance trees, distance metrics that measure independent phenomena (amino acid replacement, synonymous substitution, and gene reordering) were used, as it is highly improbable that all of the trees would be affected the same way by any reconstruction artifact. In contradiction to the currently favored classification, our results based on full-genome analysis of the phylogenetic relationship between human, dog, and mouse yielded overwhelming support for a primate-carnivore clade with the exclusion of rodents.

Measuring evolutionary distances between DNA or protein sequences forms the basis of many applications in computational biology and evolutionary studies. Of particular interest are distances based on synonymous substitutions, since these substitutions are considered to be under very little selection pressure and therefore assumed to accumulate in an almost clock-like manner. SynPAM, the method presented here, allows the estimation of distances between coding DNA sequences based on synonymous codon substitutions. The problem of estimating an accurate distance from the observed substitution pattern is solved by maximum-likelihood with empirical codon substitution matrices employed for the underlying Markov model. Comparisons with established measures of synonymous distance indicate that SynPAM has less variance and yields useful results over a longer time range.

BACKGROUND: The estimation of the difference between two evolutionary distances within a triplet of homologs is a common operation that is used for example to determine which of two sequences is closer to a third one. The most accurate method is currently maximum likelihood over the entire triplet. However, this approach is relatively time consuming. RESULTS: We show that an alternative estimator, based on pairwise estimates and therefore much faster to compute, has almost the same statistical power as the maximum likelihood estimator. We also provide a numerical approximation for its variance, which could otherwise only be estimated through an expensive re-sampling approach such as bootstrapping. An extensive simulation demonstrates that the approximation delivers precise confidence intervals. To illustrate the possible applications of these results, we show how they improve the detection of asymmetric evolution, and the identification of the closest relative to a given sequence in a group of homologs. CONCLUSION: The results presented in this paper constitute a basis for large-scale protein cross-comparisons of pairwise evolutionary distances.

BACKGROUND: Transcription factor binding site (TFBS) prediction is a difficult problem, which requires a good scoring function to discriminate between real binding sites and background noise. Many scoring functions have been proposed in the literature, but it is difficult to assess their relative performance, because they are implemented in different software tools using different search methods and different TFBS representations. RESULTS: Here we compare how several scoring functions perform on both real and semi-simulated data sets in a common test environment. We have also developed two new scoring functions and included them in the comparison. The data sets are from the yeast (S. cerevisiae) genome. Our new scoring function LLBG (least likely under the background model) performs best in this study. It achieves the best average rank for the correct motifs. Scoring functions based on positional bias performed quite poorly in this study. CONCLUSION: LLBG may provide an interesting alternative to current scoring functions for TFBS prediction.

BACKGROUND: Codon substitution probabilities are used in many types of molecular evolution studies such as determining Ka/Ks ratios, creating ancestral DNA sequences or aligning coding DNA. Until the recent dramatic increase in genomic data enabled construction of empirical matrices, researchers relied on parameterized models of codon evolution. Here we present the first empirical codon substitution matrix entirely built from alignments of coding sequences from vertebrate DNA and thus provide an alternative to parameterized models of codon evolution. RESULTS: A set of 17,502 alignments of orthologous sequences from five vertebrate genomes yielded 8.3 million aligned codons from which the number of substitutions between codons were counted. From this data, both a probability matrix and a matrix of similarity scores were computed. They are 64 x 64 matrices describing the substitutions between all codons. Substitutions from sense codons to stop codons are not considered, resulting in block diagonal matrices consisting of 61 x 61 entries for the sense codons and 3 x 3 entries for the stop codons. CONCLUSION: The amount of genomic data currently available allowed for the construction of an empirical codon substitution matrix. However, more sequence data is still needed to construct matrices from different subsets of DNA, specific to kingdoms, evolutionary distance or different amount of synonymous change. Codon mutation matrices have advantages for alignments up to medium evolutionary distances and for usages that require DNA such as ancestral reconstruction of DNA sequences and the calculation of Ka/Ks ratios.

MOTIVATION: We announce the availability of the second release of Darwin v. 2.0, an interpreted computer language especially tailored to researchers in the biosciences. The system is a general tool applicable to a wide range of problems. RESULTS: This second release improves Darwin version 1.6 in several ways: it now contains (1) a larger set of libraries touching most of the classical problems from computational biology (pairwise alignment, all versus all alignments, tree construction, multiple sequence alignment), (2) an expanded set of general purpose algorithms (search algorithms for discrete problems, matrix decomposition routines, complex/long integer arithmetic operations), (3) an improved language with a cleaner syntax, (4) better on-line help, and (5) a number of fixes to user-reported bugs. AVAILABILITY: Darwin is made available for most operating systems free of char ge from the Computational Biochemistry Research Group (CBRG), reachable at http://chrg.inf.ethz.ch. CONTACT: [email protected]

Abstract Motivation: The construction of evolutionary trees is one of the major problems in computational biology, mainly due to its complexity. Results: We present a new tree construction method that constructs a tree with minimum score for a given set of sequences, where the score is the amount of evolution measured in PAM distances. To do this, the problem of tree construction is reduced to the Traveling Salesman Problem (TSP). The input for the TSP algorithm are the pairwise distances of the sequences and the output is a circular tour through the optimal, unknown tree plus the minimum score of the tree. The circular order and the score can be used to construct the topology of the optimal tree. Our method can be used for any scoring function that correlates to the amount of changes along the branches of an evolutionary tree, for instance it could also be used for parsimony scores, but it cannot be used for least squares fit of distances. A TSP solution reduces the space of all possible trees to \batchmode \documentclass[fleqn,10pt,legalpaper]{article} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsmath} \pagestyle{empty} \begin{document} \(2^{n}\) \end{document}. Using this order, we can guarantee that we reconstruct a correct evolutionary tree if the absolute value of the error for each distance measurement is smaller than \batchmode \documentclass[fleqn,10pt,legalpaper]{article} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsmath} \pagestyle{empty} \begin{document} \(\frac{x}{2}\) \end{document}, where \batchmode \documentclass[fleqn,10pt,legalpaper]{article} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsmath} \pagestyle{empty} \begin{document} \(x\) \end{document}is the length of the shortest edge in the tree. For data sets with large errors, a dynamic programming approach is used to reconstruct the tree. Finally simulations and experiments with real data are shown. Availability: The software may be used via our cbrg server at http://cbrg.inf.ethz.ch/MultAlign. Contact: [email protected] Supplementary information: An html and postscript version of this paper is available at http://chantal.nobilitas.com/(Papers section). * To whom correspondence should be addressed.

We present algorithms for efficient searching of regular expressions on preprocessed text, using a Patricia tree as a logical model for the index. We obtain searching algorithms that run in logarithmic expected time in the size of the text for a wide subclass of regular expressions, and in sublinear expected time for any regular expression. This is the first such algorithm to be found with this complexity.

In 1980 Schwartz gave a fast probabilistic method which tests if a matrix of polynomials over Z is singular or not. The method is based on the idea of signature functions which are mappings of mathematical expressions into finite rings. In Schwartz's paper, they were polynomials over Z into GF(p). Because computation in GF(p) is very fast compared with computing with polynomials, Schwartz's method yields an enormous speedup both in theory and in practice. Therefore it is desirable to extend the class of expressions for which we can find effective signature functions. In the mid 80's Gonnet extended the class of expressions, for which signature functions could be found, to include a restricted class of elementary functions and integer roots. In this paper we present and compare methods for constructing signature functions for expressions containing algebraic numbers. Some experimental results are given.

The purpose of this paper is to build a framework and give algorithms to solve queries of the form obj E Prop where the object obj is expressible in terms of other given objects.We develop an algebra of properties, PROP, in which we carry out computations.We present a set of rules (axioms Axl -Ax7) for the behaviour of the basic functions on properties.In addition, we represent the algorithmic components such as if and while by the algebra operations meet and join.We conclude by proposing an implementation of the algebra PROP.

We introduce a family of simple and fast algorithms for solving the classical string matching problem, string matching with don't care symbols and complement symbols, and multiple patterns. In addition we solve the same problems allowing up to k mismatches. Among the features of these algorithms are that they are real time algorithms, they don't need to buffer the input, and they are suitable to be implemented in hardware.

The following problem is studied: How, and to what extent, can the retrieval speed of external hashing be improved by storing a small amount of extra information in internal storage? Several algorithms that guarantee retrieval in one access are developed and analyzed. In the first part of the paper, a restricted class of algorithms is studied, and a lower bound on the amount of extra storage is derived. An algorithm that achieves this bound, up to a constant difference, is also given. In the second part of the paper a number of restrictions are relaxed and several more practical algorithms are developed and analyzed. The last one, in particular, is very simple and efficient, allowing retrieval in one access using only a fixed number of bits of extra internal storage per bucket. The amount of extra internal storage depends on several factors, but it is typically very small: only a fraction of a bit per record stored. The cost of inserting a record is also analyzed and found to be low. Taking all factors into account, this algorithm is highly competitive for applications requiring very fast retrieval.

As part of a study of the general issue of complexity of comparison based problems, as well as interest in the specific problem, we consider the task of performing the basic priority queue operations on a heap. We show that in the worst case: $\lg \lg n \pm O(1)$ comparisons are necessary and sufficient to insert an element into a heap. (This improves the previous upper and lower bounds of $\lg n$ and $O(1)$.) $\lg n + \log ^ * n \pm O(1)$ comparisons are necessary and sufficient to replace the maximum in a heap. (This improves the previous upper and lower bounds of $2\lg n$ and $\lg n$.) $1.625n + O(\lg n\log ^ * n)$ comparisons are sufficient to create a heap. $1.37 \ldots n$ comparisons are necessary not only in the worst case but also on the average. Here lg indicates the logarithm base 2 and $\log ^ * $ denotes the iterated logarithm or number of times the logarithm base 2 may be taken before the quantity is at most 0.

We present an improved version of the original insertion and deletion algorithm for symmetric binary B-trees. We perform the analysis of the insertion algorithm using a fringe analysis method, and obtain bounds on the expected number of transformations per insertion and on the expected number of balanced nodes. We also examine empirically the expected costs to search, insert, and delete keys in symmetric binary B-trees.

We devise several procedures based on signatures (or hashing functions) to determine equivalence of expressions in Random Polynomial Time (also called Probabilistic Polynomial Time) (RPT). These procedures return as result: “equivalent” or “not-equivalent”. The result “not-equivalent” is always correct, while the result “equivalent” is correct with probability at least 1-e. This probability depends on a random number generator and is independent of the problem being solved. In all our procedures, the value e can be made arbitrarily small. This method works for determining equivalence over an important class of functions as well as answering other questions like linearity, polynomial dependence, squareness, independence, etc.

We present several algorithms to search data bases that consist of text. The algorithms apply mostly to very large data bases that are difficult to structure.We describe algorithms which search the original data base without transformation and hence could be used as general text searching algorithms. We also describe algorithms requiring pre-processing, the best of them achieving a logarithmic behaviour. These efficient algorithms solve the "plagiarism" problem among n papers.The problem of misspellings, ambiguous spellings, simple errors, endings, positional information, etc is nicely treated using signature functions.

We introduce a new class of binary search trees, the height-ratio-balanced binary search trees, as the height based analogy of weight (−ratio) balanced binary search trees. They form a proper subclass of the class of binary search trees, but not a logarithmic one, indeed an n node height-ratio balanced tree of order α,0≤α≤1/3, has a worse case height of μmgr]eμ+0(1), where μ=(−2ln(α/(1-a))ln(n)}1/2. This result indicates that these naturally defined trees should not be used to implement the DICTIONARY operations, in practical situations.

Article Free Access Share on External hasing with limited internal storage Authors: Gaston H. Gonnet University of Waterloo, Canada University of Waterloo, CanadaView Profile , Per Åke Larson Åbo Akademi, Finland Åbo Akademi, FinlandView Profile Authors Info & Claims PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1982 Pages 256–261https://doi.org/10.1145/588111.588153Online:29 March 1982Publication History 6citation225DownloadsMetricsTotal Citations6Total Downloads225Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about (2+√)n = 3.412...n probes into a table. An accurate analysis of this technique is made by introducing a transform from a Poisson approximation to the exact (finite) distribution. This analysis also leads to the solution of an interesting parking problem.

An investigation ts made of the expected value of the maximum number of accesses needed to locate any element m a hashing file under various colhston resoluuon schemes This differs from usual worst-case considerations winch, for hashmg, would be the largest sequence of accesses for the worst possible file Asymptotic expressxons of these expected values are found for full and partly full tables For the open addressing scheme with a clustering-free model these values are found to be 0.6315... x n for a full table and = -logan for a partly full table, where n ts the number of records, m is the size of the table, and a = n/m.For the open addressing scheme which reorders the insertions to minimize the worst case, the lower bounds In n + 1 077... and [-a-~in(l -a)] are found for full and partly full tables, respectively FmaUy, for the separate chaining (or direct chaining) method both expected values are found to be ~.F-t(n).These results show that for these schemes, the actual behawor of the worst case in hash tables is quite good on the average.KEY WORDS AND PHRASES' table search, hashmg, analysts of algorithms, worst case, open addressing, separate chaining, direct chaining, asymptouc analysts, optimal hashing, mimmax hashing, expected value, average case CR CATEGORIES: 3.74

We consider techniques for self-organizing linear search, examining the behavior of methods under arbitrary and specific probability distributions. The notion of moving an element forward after it has been accessed k times in a row is introduced. One implementation performs the transformation after any k identical requests. A second essentially groups requests into batches of k, and performs the action only if all requests of a batch are the same. Adopting as the transformation, the move to front heuristic, the second approach is shown in general to be superior. We show that the batched approach, with $k = 2$, leads to an average search time no greater than 1.21... times that of the optimal ordering. For the more direct approach, a ratio of 1.36... is shown under the same constraints. The simple move to front heuristic (i.e., $k = 1$) is also examined. It is shown that for a particular distribution this scheme can lead to an average number of probes $\pi/2$ times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behavior.

We consider techniques for adapting linear lists so that the more frequently accessed elements are found near the front, even though we are not told the probabilities of various elements being accessed. The main results are discussed in two sections. Perhaps the most interesting deals with techniques which move an element toward the front only after it has been requested k times in a row. The other, technically more difficult, section deals with the analysis of the heuristic which moves an element to the head of the list each time it is accessed. The behaviour of this scheme under a number of interesting probability distributions is discussed. Two basic approaches to the technique of moving an element forward after it has been accessed k times in a row are discussed. The first performs the transformation after any k identical requests. The second essentially groups requests into batches of at least k, and performs the action only if the last k requests of a batch are the same. Adopting as the transformation, the moving of the requested element to the front of the list, the second approach is shown to lead to faster average search time under all nontrivial probability distributions for k ≥2. It is also shown that the "periodic" approach, with k = 2, never leads to an average search time greater than 1.21.. times that of the optimal ordering. For the more direct approach, a ratio of 1.36.. is shown under the same constraints. In studying the simple move to front heuristic (i.e. k = 1), it is shown that for a particular distribution this scheme can lead to an average number of probes π/2 times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behaviour.

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that, even with a full table, only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme and the minimax problem of ordering the table so as to minimize the length of the longest probe sequence to find any element. Both arranging problems can be translated to assignment problems. A unified algorithm is presented for these, together with the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.

A periodic network is a queuing network whose steady-state behavior is not constant in time, but repeats itself in a cycle. This behavior may be caused by the introduction of periodic servers, e.g., paging drums. The model presented is a generalization of some other models of queuing networks, and provides a more general definition of steady-state behavior. A theoretical solution is presented. Examples of theoretical and approximate solutions are presented for a well-known queuing network model of a computer system.

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that even with a full table only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme (which is a maximum flow problem) and the minimax problem of arranging the table so as to minimize the length of the longest probe sequence to find any element. A unified algorithm is presented for both of these as well as the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.