Papers

Submitted Manuscripts:
  • Metric learning for phylogenetic tree construction
    N. Eriksson and Y. Yao.
    • »abstract
    • pdf
    • arXiv
    • data
      • We introduce new methods for phylogenetic tree construction by using metric learning to optimize the power of phylogenetic invariants on trees with four leaves. Phylogenetic invariants are polynomials in the joint probabilities which vanish under a model of evolution on a phylogenetic tree. They have been used for tree construction with only partial success partly because a good scoring metric is not known. We give algorithms for selecting a good set of invariants and for learning a metric on this set of invariants which optimally distinguishes the different quartet tree models. Our learning algorithms involve linear and semidefinite programming on data simulated over a wide range of parameters. We provide extensive tests of the learned metrics on simulated data from phylogenetic trees with four leaves under the Jukes-Cantor and Kimura 3-parameter models of DNA evolution. Our method greatly improves on other uses of invariants and is better than neighbor-joining. In particular, we obtain metrics trained on trees with short internal branches which perform much better than neighbor joining on this challenging region of parameter space.
Refereed Articles:
  • Viral population estimation using pyrosequencing
    N. Eriksson, L. Pachter, Y. Mitsuya, S.Y. Rhee, C. Wang, B. Gharizadeh, M. Ronaghi, R.W. Shafer, and N. Beerenwinkel. PLoS Computational Biology, 2008 May; 4(5): e1000074.
    • »abstract
    • PLoS
    • pdf
    • arXiv
      • The genetic diversity of viral populations is important for biomedical problems such as disease progression, vaccine design, and drug resistance, yet it is not generally well-understood. In this paper, we use pyrosequencing, a novel DNA sequencing technique, to reconstruct viral populations. Pyrosequencing produces a large number of short, error-prone DNA reads. We develop mathematical and statistical tools to correct errors and assemble the reads into the different viral strains present in the population. We apply these methods to HIV-1 populations from drug resistant patients and show that pyrosequencing produces results quite close to accepted techniques at a low cost and potentially higher resolution.
  • Using invariants for phylogenetic tree construction
    In M. Putinar and S. Sullivant (eds.), Emerging Applications of Algebraic Geometry, I.M.A. Volumes in Mathematics and its Applications, 2008 to appear.
    • »abstract
    • pdf
    • arXiv
      • Phylogenetic invariants are certain polynomials in the joint probability distribution of a Markov model on a phylogenetic tree. Such polynomials are of theoretical interest in the field of algebraic statistics and they are also of practical interest—they can be used to construct phylogenetic trees. This paper is a self-contained introduction to the algebraic, statistical, and computational challenges involved in the practical use of phylogenetic invariants. We survey the relevant literature and provide some partial answers and many open problems.
  • Sequence editing by Apolipoprotein B RNA-editing catalytic component-B and epidemiological surveillance of transmitted HIV-1 drug resistance.
    R.J. Gifford, S.Y. Rhee, N. Eriksson, M. Kiuchi, A.K. Das, and R.W. Shafer. AIDS, 22(6):717-725, March 30, 2008.
    • »abstract
    • AIDS
      • Design: Promiscuous guanine (G) to adenine (A) substitutions catalysed by apolipoprotein B RNA-editing catalytic component (APOBEC) enzymes are observed in a proportion of HIV-1 sequences in vivo and can introduce artifacts into some genetic analyses. The potential impact of undetected lethal editing on genotypic estimation of transmitted drug resistance was assessed. Methods: Classifiers of lethal, APOBEC-mediated editing were developed by analysis of lentiviral pol gene sequence variation and evaluated using control sets of HIV-1 sequences. The potential impact of sequence editing on genotypic estimation of drug resistance was assessed in sets of sequences obtained from 77 studies of 25 or more therapy-naive individuals, using mixture modelling approaches to determine the maximum likelihood classification of sequences as lethally edited as opposed to viable. Results: Analysis of 6437 protease and reverse transcriptase sequences from therapy-naive individuals using a novel classifier of lethal, APOBEC3G-mediated sequence editing, the polypeptide-like 3G (APOBEC3G)-mediated defectives (A3GD) index', detected lethal editing in association with spurious 'transmitted drug resistance' in nearly 3% of proviral sequences obtained from whole blood and 0.2% of samples obtained from plasma. Conclusion: Screening for lethally edited sequences in datasets containing a proportion of proviral DNA, such as those likely to be obtained for epidemiological surveillance of transmitted drug resistance in the developing world, can eliminate rare but potentially significant errors in genotypic estimation of transmitted drug resistance.
  • Apollonian circle packings: Number theory II. Spherical and hyperbolic packings
    N. Eriksson and Jeffrey C. Lagarias. Ramanujan Journal 14 (3):437-469, 2007.
    • »abstract
    • DOI
    • pdf
    • arXiv
      • Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. In Euclidean space it is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. Integral circle packings also exist in spherical and hyperbolic space, provided a suitable definition of curvature is used and as in the Euclidean case, there are an infinite number of different integral packings. This paper studies number-theoretic properties of spherical and hyperbolic packings. This amounts to studying the orbits of a particular subgroup of the group of integral automorphs of the indefinite quaternary quadratic form $Q_{\sD}(w, x, y, z)= 2(w^2+x^2 +y^2 + z^2) - (w+x+y+z)^2$. This subgroup, called the Apollonian group, acts on integer solutions $Q_{\sD}(w, x, y, z)=k$. This paper gives a reduction theory for orbits of $\sA$ acting on integer solutions to $Q_{\sD}(w, x, y, z)=k$ valid for all integer $k$. It also classifies orbits for all $k \equiv 0 \pmod{4}$ in terms of an extra parameter $n$ and an auxiliary class group (depending on $n$ and $k$), and studies congruence conditions on integers in a given orbit.
  • Conjunctive Bayesian networks
    N. Beerenwinkel, N. Eriksson, and B. Sturmfels. Bernoulli, 13 (4):893-909, 2007.
    • »abstract
    • DOI
    • pdf
    • arXiv
    • code
    • slides
      • Conjunctive Bayesian networks (CBNs) are graphical models that describe the accumulation of events which are constrained in the order of their occurrence. A CBN is given by a partial order on a (finite) set of events. CBNs generalize the oncogenetic tree models of Desper et al. (1999) by allowing the occurrence of an event to depend on more than one predecessor event. The present paper studies the statistical and algebraic properties of CBNs. We determine the maximum likelihood parameters and present a combinatorial solution to the model selection problem. Our method performs well on two datasets where the events are HIV mutations associated with drug resistance. Concluding with a study of the algebraic properties of CBNs, we show that CBNs are toric varieties after a coordinate transformation and that their ideals possess a quadratic Gröbner basis.
  • Evolution on distributive lattices
    N. Beerenwinkel, N. Eriksson, and B. Sturmfels. Journal of Theoretical Biology, 242 (2):409-420, 2006.
    • »abstract
    • DOI
    • pdf
    • arXiv
    • code
    • slides
      • We consider the directed evolution of a population after an intervention that has significantly altered the underlying fitness landscape. We model the space of genotypes as a distributive lattice; the fitness landscape is a real-valued function on that lattice. The risk of escape from intervention, i.e., the probability that the population develops an escape mutant before extinction, is encoded in the risk polynomial. Tools from algebraic combinatorics are applied to compute the risk polynomial in terms of the fitness landscape. In an application to the development of drug resistance in HIV, we study the risk of viral escape from treatment with the protease inhibitors ritonavir and indinavir.
  • Markov bases for noncommutative Fourier analysis of ranked data
    P. Diaconis and N. Eriksson. Journal of Symbolic Computation, 41 (2):182-195, 2006.
    • »abstract
    • DOI
    • pdf
    • arXiv
    • code
    • slides
      • To calibrate Fourier analysis of $S_5$ ranking data by Markov chain Monte Carlo techniques, a set of moves (Markov basis) is needed. We calculate this basis, and use it to provide a new statistical analysis of two data sets. The calculation involves a large Gröbner basis computation (45825 generators), but reduction to a minimal basis and reduction by natural symmetries leads to a remarkably small basis (14 elements). Although the Gröbner basis calculation is infeasible for $S_6$, we exploit the symmetry of the problem to calculate a Markov basis for $S_6$ with 7,113,390 elements in 58 symmetry classes. We improve a bound on the degree of the generators for a Markov basis for $S_n$ and conjecture that this ideal is generated in degree 3.
  • Polyhedral conditions for the nonexistence of the MLE for hierarchical log-linear models
    N. Eriksson, S. Fienberg, A. Rinaldo, and S. Sullivant. Journal of Symbolic Computation, 41 (2):222-233, 2006.
    • »abstract
    • DOI
    • pdf
    • arXiv
    • data
      • We provide a polyhedral description of the conditions for the existence of the maximum likelihood estimate (MLE) for a hierarchical log-linear model. The MLE exists if and only if the observed margins lie in the relative interior of the marginal cone. Using this description, we give an algorithm for determining if the MLE exists. If the tree width is bounded, the algorithm runs in polynomial time. We also perform a computational study of the case of three random variables under the no three-factor effect model.
  • Phylogenetic algebraic geometry
    N. Eriksson, K. Ranestad, B. Sturmfels and S. Sullivant. In C. Ciliberto, A. Geramita, B. Harbourne, R-M. Roig and K. Ranestad (eds.), Projective Varieties with Unexpected Properties, 237-255. De Gruyter, Berlin, 2005.
    • »abstract
    • pdf
    • arXiv
      • Phylogenetic algebraic geometry is concerned with certain complex projective algebraic varieties derived from finite trees. Real positive points on these varieties represent probabilistic models of evolution. For small trees, we recover classical geometric objects, such as toric and determinantal varieties and their secant varieties, but larger trees lead to new and largely unexplored territory. This paper gives a self-contained introduction to this subject and offers numerous open problems for algebraic geometers.
  • Toric ideals of homogeneous phylogenetic models
    In Proceedings of the 2004 international symposium on symbolic and algebraic computation, 149-154. ACM Press, New York, 2004.
    • »abstract
    • DOI
    • pdf
    • arXiv
    • slides
    • copyright
      • We consider the model of phylogenetic trees in which every node of the tree is an observed, binary random variable and the transition probabilities are given by the same matrix on each edge of the tree. The ideal of invariants of this model is a toric ideal. We are able to compute the Gröbner basis and minimal generating set for this ideal for trees with up to 11 nodes. These are the first non-trivial Gröbner bases calculations in 2048 indeterminates. We conjecture that there is a quadratic Gröbner basis for binary trees, but that generators of degree $n$ are required for some trees with $n$ nodes. The polytopes associated with these toric ideals display interesting finiteness properties. We describe the polytope for an infinite family of binary trees and conjecture (based on extensive computations) that there is a universal bound on the number of vertices of the polytope of a binary tree.
  • q-series, elliptic curves, and odd values of the partition function
    International Journal of Mathematics and Mathematical Sciences, 22 (1):55-66, 1999.
    • »abstract
    • pdf
      • Let $p(n)$ be the number of partitions of an integer $n$. Euler proved the following recurrence for $p(n)$: \[ p(n)=\sum _{k=1}^{\infty} (-1)^{k+1} (p(n-\omega (k))+p(n-\omega (-k))) \] where $\omega (k)=\frac{3k^2+k}{2}.$ In view of Euler's result one sees that it is fairly easy to compute $p(n)$ very quickly. However, many questions remain open even regarding the parity of $p(n)$. In this paper we use various facts about elliptic curves and $q$-series to construct, for every $i\geq 1$, finite sets $M_i$ for which $p(n)$ is odd for an odd number of $n\in M_i.$
Book Chapters:
  • Tree Construction Using Singular Value Decomposition
    In L. Pachter and B. Sturmfels (eds.) Algebraic Statistics for Computational Biology, 347-358. Cambridge University Press, Cambridge, UK, 2005.
  • Ultra-Conserved Elements in Vertebrate and Fly Genomes
    M. Drton, N. Eriksson, and G. Leung. In L. Pachter and B. Sturmfels (eds.) Algebraic Statistics for Computational Biology, 387-402. Cambridge University Press, Cambridge, UK, 2005.
Theses:
  • Algebraic combinatorics for computational biology
    Ph.D. dissertation, Department of Mathematics, UC Berkeley.
  • Clifford Algebras and Spin Groups
    MIT Undergraduate Journal of Mathematics, 3, 2001.