An adaptive pseudospectral method for wave packet dynamics.

We solve the time-dependent Schrödinger equation for molecular dynamics using a pseudospectral method with global, exponentially decaying, Hagedorn basis functions. The approximation properties of the Hagedorn basis depend strongly on the scaling of the spatial coordinates. Using results from control theory we develop a time-dependent scaling which adaptively matches the basis to the wave packet. The method requires no knowledge of the Hessian of the potential. The viability of the method is demonstrated on a model for the photodissociation of IBr, using a Fourier basis in the bound state and Hagedorn bases in the dissociative states. Using the new approach to adapting the basis we are able to solve the problem with less than half the number of basis functions otherwise necessary. We also present calculations on a two-dimensional model of CO(2) where the new method considerably reduces the required number of basis functions compared to the Fourier pseudospectral method.

Increasing the efficiency of variance component quantitative trait loci analysis by using reduced-rank identity-by-descent matrices.

Recent technological development in genetics has made large-scale marker genotyping fast and practicable, facilitating studies for detection of QTL in large general pedigrees. We developed a method that speeds up restricted maximum-likelihood (REML) algorithms for QTL analysis by simplifying the inversion of the variance-covariance matrix of the trait vector. The method was tested in an experimental chicken pedigree including 767 phenotyped individuals and 14 genotyped markers on chicken chromosome 1. The computation time in a chromosome scan covering 475 cM was reduced by 43% when the analysis was based on linkage only and by 72% when linkage disequilibrium information was included. The relative advantage of using our method increases with pedigree size, marker density, and linkage disequilibrium, indicating even greater improvements in the future.

A Flexible Computational Framework Using R and Map-Reduce for Permutation Tests of Massive Genetic Analysis of Complex Traits.

In quantitative trait locus (QTL) mapping significance of putative QTL is often determined using permutation testing. The computational needs to calculate the significance level are immense, 104 up to 108 or even more permutations can be needed. We have previously introduced the PruneDIRECT algorithm for multiple QTL scan with epistatic interactions. This algorithm has specific strengths for permutation testing. Here, we present a flexible, parallel computing framework for identifying multiple interacting QTL using the PruneDIRECT algorithm which uses the map-reduce model as implemented in Hadoop. The framework is implemented in R, a widely used software tool among geneticists. This enables users to rearrange algorithmic steps to adapt genetic models, search algorithms, and parallelization steps to their needs in a flexible way. Our work underlines the maturity of accessing distributed parallel computing for computationally demanding bioinformatics applications through building workflows within existing scientific environments. We investigate the PruneDIRECT algorithm, comparing its performance to exhaustive search and DIRECT algorithm using our framework on a public cloud resource. We find that PruneDIRECT is vastly superior for permutation testing, and perform 2 ×105 permutations for a 2D QTL problem in 15 hours, using 100 cloud processes. We show that our framework scales out almost linearly for a 3D QTL search.

Efficient algorithms for quantitative trait loci mapping problems.

Rapid advances in molecular genetics push the need for efficient data analysis. Advanced algorithms are necessary for extracting all possible information from large experimental data sets. We present a general linear algebra framework for quantitative trait loci (QTL) mapping, using both linear regression and maximum likelihood estimation. The formulation simplifies future comparisons between and theoretical analyses of the methods. We show how the common structure of QTL analysis models can be used to improve the kernel algorithms, drastically reducing the computational effort while retaining the original analysis results. We have evaluated our new algorithms on data sets originating from two large F(2) populations of domestic animals. Using an updating approach, we show that 1-3 orders of magnitude reduction in computational demand can be achieved for matrix factorizations. For interval-mapping/composite-interval-mapping settings using a maximum likelihood model, we also show how to use the original EM algorithm instead of the ECM approximation, significantly improving the convergence and further reducing the computational time. The algorithmic improvements makes it feasible to perform analyses which have previously been deemed impractical or even impossible. For example, using the new algorithms, it is reasonable to perform permutation testing using exhaustive search on populations of 200 individuals using an epistatic two-QTL model.

Fast and accurate detection of multiple quantitative trait Loci.

We present a new computational scheme that enables efficient and reliable quantitative trait loci (QTL) scans for experimental populations. Using a standard brute-force exhaustive search effectively prohibits accurate QTL scans involving more than two loci to be performed in practice, at least if permutation testing is used to determine significance. Some more elaborate global optimization approaches, for example, DIRECT have been adopted earlier to QTL search problems. Dramatic speedups have been reported for high-dimensional scans. However, since a heuristic termination criterion must be used in these types of algorithms, the accuracy of the optimization process cannot be guaranteed. Indeed, earlier results show that a small bias in the significance thresholds is sometimes introduced. Our new optimization scheme, PruneDIRECT, is based on an analysis leading to a computable (Lipschitz) bound on the slope of a transformed objective function. The bound is derived for both infinite- and finite-size populations. Introducing a Lipschitz bound in DIRECT leads to an algorithm related to classical Lipschitz optimization. Regions in the search space can be permanently excluded (pruned) during the optimization process. Heuristic termination criteria can thus be avoided. Hence, PruneDIRECT has a well-defined error bound and can in practice be guaranteed to be equivalent to a corresponding exhaustive search. We present simulation results that show that for simultaneous mapping of three QTLS using permutation testing, PruneDIRECT is typically more than 50 times faster than exhaustive search. The speedup is higher for stronger QTL. This could be used to quickly detect strong candidate eQTL networks.

MAPfastR: quantitative trait loci mapping in outbred line crosses.

MAPfastR is a software package developed to analyze quantitative trait loci data from inbred and outbred line-crosses. The package includes a number of modules for fast and accurate quantitative trait loci analyses. It has been developed in the R language for fast and comprehensive analyses of large datasets. MAPfastR is freely available at: http://www.computationalgenetics.se/?page_id=7.

Efficient algorithms for multidimensional global optimization in genetic mapping of complex traits.

We present a two-phase strategy for optimizing a multidimensional, nonconvex function arising during genetic mapping of quantitative traits. Such traits are believed to be affected by multiple so called quantitative trait loci (QTL), and searching for d QTL results in a d-dimensional optimization problem with a large number of local optima. We combine the global algorithm DIRECT with a number of local optimization methods that accelerate the final convergence, and adapt the algorithms to problem-specific features. We also improve the evaluation of the QTL mapping objective function to enable exploitation of the smoothness properties of the optimization landscape. Our best two-phase method is demonstrated to be accurate in at least six dimensions and up to ten times faster than currently used QTL mapping algorithms.

Assessing a multiple QTL search using the variance component model.

Development of variance component algorithms in genetics has previously mainly focused on animal breeding models or problems in human genetics with a simple data structure. We study alternative methods for constrained likelihood maximization in quantitative trait loci (QTL) analysis for large complex pedigrees. We apply a forward selection scheme to include several QTL and interaction effects, as well as polygenic effects, with up to five variance components in the model. We show that the implemented active set and primal-dual schemes result in accurate solutions and that they are robust. In terms of computational speed, a comparison of two approaches for approximating the Hessian of the log-likelihood shows that the method using an average information matrix is the method of choice for the five-dimensional problem. The active set method, with the average information method for Hessian computation, exhibits the fastest convergence with an average of 20 iterations per tested position, where the change in variance components <0.0001 was used as convergence criterion.

Accurate time propagation for the Schrodinger equation with an explicitly time-dependent Hamiltonian.

Several different numerical propagation techniques for explicitly time-dependent Hamiltonians are discussed and compared, with the focus on models of pump-probe experiments. The quality of the rotating wave approximation is analyzed analytically, and we point out under which circumstances the modeling becomes inaccurate. For calculations with the fully time-dependent Hamiltonian, we show that for multistate systems, with either time or space dependence in the interstate coupling, the fourth order truncated Magnus expansion can be reformulated so that no commutators appear. Our results show that the split-operator method should only be used when low accuracy is acceptable. For accurate and efficient time stepping, the Magnus-Lanczos approach appears to be the best choice.