Search

The triplet distance is a distance measure that compares two rooted trees on the same set of leaves byenumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal ordifferent. We present an algorithm that computes the triplet distance between two rooted binary trees in timeO (n log2n). The algorithm is related to an algorithm for computing the quartet distance between two unrootedbinary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotictime complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments thatthe triplet distance algorithm can be implemented to give a competitive wall-time running time. The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.

The neighbour-joining method is a widely used method for phylogenetic reconstruction which scales to thousands of taxa. However, advances in sequencing technology have made data sets with more than 10,000 related taxa widely available. Inference of such large phylogenies takes hours or days using the Neighbour-Joining method on a normal desktop computer because of the O(n^3) running time. RapidNJ is a search heuristic which reduce the running time of the Neighbour-Joining method significantly but at the cost of an increased memory consumption making inference of large phylogenies infeasible. We present two extensions for RapidNJ which reduce the memory requirements and \makebox{allows} phylogenies with more than 50,000 taxa to be inferred efficiently on a desktop computer. Furthermore, an improved version of the search heuristic is presented which reduces the running time of RapidNJ on many data sets.

The objective in molecular docking is to determine the best binding mode of two molecules in silico. A common applica- tion of molecular docking is in drug discovery where a large number of ligands are docked against a protein to identify potential drug candidates. This is a computationally in- tensive problem especially if flexibility of the molecules are taken into account. In this paper we show how MolDock, which is a high accuracy method for flexible molecular dock- ing using a variant of differential evolution, can be paral- lelised on both CPU and GPU. The methods presented for parallelising the workload result in an average speedup of 3.9x on a 4-core CPU and 27.4x on a comparable CUDA enabled GPU when docking 133 ligands of different sizes. Furthermore, the presented parallelisation schemes are gen- erally applicable and can easily be adapted to other common flexible docking methods.

Bioinformatics focuses on developing computational methods forcollecting, handling and analyzing biological data. Because the amount ofdata is often very large and the models used for analysis are complex,the demand for efficient methods exploiting modern computer hardware isincreasing.In the past ten years we have been moving from single core to multi-core processorarchitectures, and recently Graphics Processing Units (GPUs) with hundreds of coreshave also become available for general purpose computation. Making existing andnew algorithms exploit these multi-core architectures is one of today’s majorchallenges in e.g. bioinformatics. At the Bioinformatics Research Center (BiRC), weare currently working on two projects involving the exploitation of modern multi-corearchitectures:1. In molecular docking we aim to identify small proteins called ligands which showstrong interaction with a target protein molecule. Such ligands potentially altersthe function of the (disease causing) target protein and can therefore be used in amodern drug discovery process. Evaluation of ligands against a target moleculerequires a moderate amount of computation, but we often need to evaluatethousands of ligands against several target molecules, requiring use of expensivecomputer clusters. By using GPUs to exploit the parallel nature of moleculardocking, we reduce the hardware requirements of large scale molecular dockingsignificantly.2. Hidden Markov Models (HMMs) is a statistical tool used in a wide range ofapplications within bioinformatics for modeling sequential data assumed tooriginate from a Markov process; e.g. gene annotation, alignments and inferringcoalescence processes among species. Because of their computational efficiency,HMMs are one of few methods used for genome wide analysis, where sequencesoften consist of millions of characters. Nevertheless analysis times are still oftenmeasured in days, weeks or months, and the models must therefore be keptrelatively simple. By exploiting SSE instructions and the multi-core architectureof modern CPUs we decrease the running time of the analyses significantly andthereby make analyses of more complex models feasible.

The fingerprint of a molecule is a bitstring based on its structure, constructed such that structurally similar molecules will have similar fingerprints. Molecular fingerprints can be used in an initial phase for identifying novel drug candidates by screening large databases for molecules with fingerprints similar to a query fingerprint. In this paper, we present a method which efficiently finds all fingerprints in a database with Tanimoto coefficient to the query fingerprint above a user defined threshold. The method is based on two novel data structures for rapid screening of large databases: the kD grid and the Multibit tree. The kD grid is based on splitting the fingerprints into k shorter bitstrings and utilising these to compute bounds on the similarity of the complete bitstrings. The Multibit tree uses hierarchical clustering and similarity within each cluster to compute similar bounds. We have implemented our method and tested it on a large data set from the industry. Our experiments show that our method yields a three-fold speed-up over previous methods.

GeneRecon is a tool for fine-scale association mapping using a coalescence model. GeneRecon takes as input case-control data from phased or unphased SNP and micro-satellite genotypes. The posterior distribution of disease locus position is obtained by Metropolis Hastings sampling in the state space of genealogies. Input format, search strategy, and the sampled statistics can be configured through the Guile Scheme programming language embedded in GeneRecon, making GeneRecon highly configurable.

Background Coalescent simulations are playing a large role in interpreting large scale intra- polymorphism surveys and for planning and evaluating association studies. Coalescent of data sets under different models can be compared to the actual data to test different evolutionary factors and thus get insight into these. Results We have created the CoaSim application as a flexible environment for Monte various types of genetic data under equilibrium and non-equilibrium coalescent variety of applications. Interaction with the tool is through the Guile version scripting language. Scheme scripts for many standard and advanced applications these can easily be modified by the user for a much wider range of applications. interface with less functionality and flexibility is also included. It is primarily exploratory and educational tool. Conclusions CoaSim is a powerful tool because of its flexibility and ease of use. This is illustrated varied uses of the application, e.g. evaluation of association mapping methods, bootstrapping, and design and choice of markers for specific questions.

A widely used method for constructing phylogenetic trees is the neighbour-joining method of Saitou and Nei. We develope heuristics for speeding up the neighbour-joining method which generate the same phylogenetic trees as the original method. All heuristics are based on using a quad-tree to guide the search for the next pair of nodes to join, but di#er in the information stored in quad-tree nodes, the way the search is performed, and in the way the quad-tree is updated after a join. We empirically evaluate the performance of the heuristics on distance matrices obtained from the Pfam collection of alignments, and compare the running time with that of the QuickTree tool, a well-known and widely used implementation of the standard neighbour-joining method. The results show that the presented heuristics can give a significant speed-up over the standard neighbour-joining method, already for medium sized instances.