title: ACG: rapid inference of population history from recombining nucleotide sequences.
abstract: BACKGROUND
  Reconstruction of population history from genetic data often requires Monte Carlo integration over the genealogy of the samples. Among tools that perform such computations, few are able to consider genetic histories including recombination events, precluding their use on most alignments of nuclear DNA. Explicit consideration of recombinations requires modeling the history of the sequences with an Ancestral Recombination Graph (ARG) in place of a simple tree, which presents significant computational challenges.
  
  
  RESULTS
  ACG is an extensible desktop application that uses a Bayesian Markov chain Monte Carlo procedure to estimate the posterior likelihood of an evolutionary model conditional on an alignment of genetic data. The ancestry of the sequences is represented by an ARG, which is estimated from the data with other model parameters. Importantly, ACG computes the full, Felsenstein likelihood of the ARG, not a pairwise or composite likelihood. Several strategies are used to speed computations, and ACG is roughly 100x faster than a similar, recombination-aware program.
  
  
  CONCLUSIONS
  Modeling the ancestry of the sequences with an ARG allows ACG to estimate the evolutionary history of recombining nucleotide sequences. ACG can accurately estimate the posterior distribution of population parameters such as the (scaled) population size and recombination rate, as well as many aspects of the recombinant history, including the positions of recombination breakpoints, the distribution of time to most recent common ancestor along the sequence, and the non-recombining trees at individual sites. Multiple substitution models and population size models are provided. ACG also provides a richly informative graphical interface that allows users to view the evolution of model parameters and likelihoods in real time.
authors: ARUP Labs, 500 Chipeta Way, Salt Lake City, UT 84108, USA. brendan.d.ofallon@aruplab.com
authors: Brendan D
authors: BD
authors: O'Fallon
mesh_terms: D001499:Bayes Theorem; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D009010:Monte Carlo Method; D010375:Pedigree; D011156:Population Density; D011995:Recombination, Genetic; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
references: J Comput Biol. 1996 Winter;3(4):479-502
references: 9018600
references: Proc Natl Acad Sci U S A. 2007 Feb 20;104(8):2785-90
references: 17301231
references: Bioinformatics. 2001 Aug;17(8):754-5
references: 11524383
references: PLoS Biol. 2006 Mar;4(3):e72
references: 16494531
references: Bioinformatics. 2003 Aug 12;19(12):1572-4
references: 12912839
references: Bioinformatics. 2006 Mar 15;22(6):768-70
references: 16410317
references: Trends Ecol Evol. 2009 Feb;24(2):86-93
references: 19101058
references: J Mol Evol. 1981;17(6):368-76
references: 7288891
references: Nature. 2002 Oct 24;419(6909):832-7
references: 12397357
references: Genetics. 2002 Mar;160(3):1231-41
references: 11901136
references: BMC Evol Biol. 2007 Nov 08;7:214
references: 17996036
references: Mol Biol Evol. 1997 Jul;14(7):717-24
references: 9214744
references: Comput Appl Biosci. 1997 Jun;13(3):235-8
references: 9183526