research-article

A fast solver for modeling the evolution of virus populations

Authors:

Gerhard Niederbrucker,

Wilfried N. GanstererAuthors Info & Claims

SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 74, Pages 1 - 11

https://doi.org/10.1145/2063384.2063483

Published: 12 November 2011 Publication History

Abstract

Solving Eigen's quasispecies model for the evolution of virus populations involves the computation of the dominant eigenvector of a matrix whose size N grows exponentially with the chain length of the virus to be modeled. Most biologically interesting chain lengths are so far well beyond the reach of existing algorithms and hardware.

We show how to exploit the special properties of the problem under consideration and design a fast and accurate solver which reduces the complexity to Θ(N log₂ N). Our solver is even faster than existing approximative strategies and contrary to those it can also be applied to more general formulations of the quasispecies model. Substantial further improvements and high parallelism can be achieved for special fitness landscapes in the evolution model.

Beyond theoretical analysis, we evaluate the performance of our new solver experimentally on a GPU with an OpenCL implementation and illustrate that it achieves speedup factors of more than 10⁷ over standard approaches.

References

[1]

Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. Introduction to Algorithms, 2nd ed. McGraw-Hill Higher Education, 2001.

Digital Library

[2]

Drake, J. Rates of spontaneous mutation among RNA viruses. Proceedings of The National Academy of Sciences 90, 9 (1993), 4171--4175.

[3]

Dress, A. W. M., and Rumschitzki, D. S. Evolution on sequence space and tensor products of representation spaces. Acta Applicandae Mathematicae 11 (1988), 103--115.

[4]

Drineas, P., Drinea, E., and Huggins, P. S. An experimental evaluation of a Monte-Carlo algorithm for singular value decomposition. Proceedings of the 8th Panhellenic conference on Informatics (2003), 279--296.

Digital Library

[5]

Eigen, M. Selforganization of matter and the evolution of biological macromolecules. Naturwissenschaften 58 (1971), 465--523.

[6]

Eigen, M. Error catastrophe and antiviral strategy. Proceedings of the National Academy of Sciences of the United States of America 99, 21 (2002), 13374--13376.

[7]

Eigen, M., and Schuster, P. A principle of natural self-organization. Naturwissenschaften 64 (1977), 541--565.

[8]

Fino, B., and Algazi, V. Unified matrix treatment of the fast Walsh-Hadamard transform. IEEE Transactions on Computers C-25, 11 (1976), 1142--1146.

Digital Library

[9]

Mascagni, M., and Karaivanova, A. A parallel quasi-monte carlo method for computing extremal eigenvalues. Monte Carlo and Quasi-Monte Carlo Methods 2000 (2000), 369--380.

[10]

Niederbrucker, G., and Gansterer, W. N. Efficient solution of evolution models for virus populations. Procedia Computer Science 4 (2011), 126--135.

[11]

Nowak, M., and Schuster, P. Error thresholds of replication in finite populations mutation frequencies and the onset of Muller's ratchet. Journal of Theoretical Biology 137, 4 (1989), 375--395.

[12]

Rumschitzki, D. S. Spectral properties of Eigen evolution matrices. Journal of Mathematical Biology 24 (1987), 667--680.

[13]

Schuster, P. Prediction of RNA secondary structures: from theory to models and real molecules. Reports on Progress in Physics 69 (May 2006), 1419--1477.

[14]

Schuster, P. The mathematics of Darwinian systems. 2008. Appendix for the book: Manfred Eigen, 'From Strange Simplicity to Complex Familiarity, Vol.I'.

[15]

Schuster, P. Mathematical modeling of evolution. Solved and open problems. Theory in Biosciences 130 (2011), 71--89.

[16]

Seneta, E. Non-negative Matrices and Markov Chains (Springer Series in Statistics). Springer, January 2006.

[17]

Swetina, J., and Schuster, P. Self-replication with errors: A model for polynucleotide replication. Biophysical Chemistry 16, 4 (1982), 329--345.

[18]

van Loan, C. F. The ubiquitous Kronecker product. J. Comput. Appl. Math. 123 (November 2000), 85--100.

Digital Library

Cited By

Georg PGrasedyck LKlever MSchill RSpang RWettig T(2022)Low-rank tensor methods for Markov chains with applications to tumor progression modelsJournal of Mathematical Biology10.1007/s00285-022-01846-986:1Online publication date: 2-Dec-2022
https://doi.org/10.1007/s00285-022-01846-9

Index Terms

A fast solver for modeling the evolution of virus populations

Recommendations

A scalable, numerically stable, high-performance tridiagonal solver using GPUs
SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

In this paper, we present a scalable, numerically stable, high-performance tridiagonal solver. The solver is based on the SPIKE algorithm for partitioning a large matrix into small independent matrices, which can be solved in parallel. For each small ...
Enhancing differential evolution algorithm using leader-adjoint populations
Abstract
The performance of differential evolution (DE) significantly depends on the settings of mutation strategies and control parameters. Inappropriate settings may cause an imbalance between exploration and exploitation of the algorithm, thus ...
GPU-accelerated preconditioned iterative linear solvers

This work is an overview of our preliminary experience in developing a high-performance iterative linear solver accelerated by GPU coprocessors. Our goal is to illustrate the advantages and difficulties encountered when deploying GPU technology to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

November 2011

866 pages

ISBN:9781450307710

DOI:10.1145/2063384

Conference Chair:
Scott Lathrop
University of Chicago
,
Program Chairs:
Jim Costa
Sandia National Laboratories
,
William Kramer
National Center for Supercomputing Applications

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Austrian Science Fund

Conference

SC '11

Sponsor:

SIGARCH
IEEE-CS

SC '11: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 18, 2011

Washington, Seattle

Acceptance Rates

SC '11 Paper Acceptance Rate 74 of 352 submissions, 21%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Georg PGrasedyck LKlever MSchill RSpang RWettig T(2022)Low-rank tensor methods for Markov chains with applications to tumor progression modelsJournal of Mathematical Biology10.1007/s00285-022-01846-986:1Online publication date: 2-Dec-2022
https://doi.org/10.1007/s00285-022-01846-9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents