title: Interpretation and approximation tools for big, dense Markov chain transition matrices in population genetics.
abstract: BACKGROUND
  Markov chains are a common framework for individual-based state and time discrete models in evolution. Though they played an important role in the development of basic population genetic theory, the analysis of more complex evolutionary scenarios typically involves approximation with other types of models. As the number of states increases, the big, dense transition matrices involved become increasingly unwieldy. However, advances in computational technology continue to reduce the challenges of "big data", thus giving new potential to state-rich Markov chains in theoretical population genetics.
  
  
  RESULTS
  Using a population genetic model based on genotype frequencies as an example, we propose a set of methods to assist in the computation and interpretation of big, dense Markov chain transition matrices. With the help of network analysis, we demonstrate how they can be transformed into clear and easily interpretable graphs, providing a new perspective even on the classic case of a randomly mating, finite population with mutation. Moreover, we describe an algorithm to save computer memory by substituting the original matrix with a sparse approximate while preserving its mathematically important properties, including a closely corresponding dominant (normalized) eigenvector. A global sensitivity analysis of the approximation results in our example shows that size reduction of more than 90 % is possible without significantly affecting the basic model results. Sample implementations of our methods are collected in the Python module mamoth.
  
  
  CONCLUSIONS
  Our methods help to make stochastic population genetic models involving big, dense transition matrices computationally feasible. Our visualization techniques provide new ways to explore such models and concisely present the results. Thus, our methods will contribute to establish state-rich Markov chains as a valuable supplement to the diversity of population genetic models currently employed, providing interesting new details about evolution e.g. under non-standard reproductive systems such as partial clonality.
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Katja
authors.identifier: 0000-0001-9052-3179
authors.initials: K
authors.lastname: Reichel
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Valentin
authors.initials: V
authors.lastname: Bahier
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Cédric
authors.initials: C
authors.lastname: Midoux
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Nicolas
authors.initials: N
authors.lastname: Parisey
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Jean-Pierre
authors.initials: JP
authors.lastname: Masson
authors.affiliation: INRA, UMR1349 Institute for Genetics, Environment and Plant Protection, 35650 Le Rheu, France.
authors.forename: Solenn
authors.initials: S
authors.lastname: Stoeckel
keywords: Compositional data; Discrete stochastic model; Eigenvector; Network analysis; Population genetics; Sparse approximation; de Finetti diagram