The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks

By Dan Gusfield

Combinatorial structure and algorithms for deducing genetic recombination history, represented by ancestral recombination graphs and other networks, and their role in the emerging field of phylogenetic networks.





Combinatorial structure and algorithms for deducing genetic recombination history, represented by ancestral recombination graphs and other networks, and their role in the emerging field of phylogenetic networks.

In this book, Dan Gusfield examines combinatorial algorithms to construct genealogical and exact phylogenetic networks, particularly ancestral recombination graphs (ARGs). The algorithms produce networks (or information about networks) that serve as hypotheses about the true genealogical history of observed biological sequences and can be applied to practical biological problems.

Phylogenetic trees have been the traditional means to represent evolutionary history, but there is a growing realization that networks rather than trees are often needed, most notably for recent human history. This has led to the development of ARGs in population genetics and, more broadly, to phylogenetic networks. ReCombinatorics offers an in-depth, rigorous examination of current research on the combinatorial, graph-theoretic structure of ARGs and explicit phylogenetic networks, and algorithms to reconstruct or deduce information about those networks.

ReCombinatorics, a groundbreaking contribution to the emerging field of phylogenetic networks, connects and unifies topics in population genetics and phylogenetics that have traditionally been discussed separately and considered to be unrelated. It covers the necessary combinatorial and algorithmic background material; the various biological phenomena; the mathematical, population genetic, and phylogenetic models that capture the essential elements of these phenomena; the combinatorial and algorithmic problems that derive from these models; the theoretical results that have been obtained; related software that has been developed; and some empirical testing of the software on simulated and real biological data.


$64.00 X ISBN: 9780262027526 600 pp. | 7 in x 9 in 171 b&w illus., 11 tables


  • The book is highly organized, easy to follow, and easy to read. It is self-contained both with respect to biology and combinatorics, and it would be suitable for a researcher in either discipline, or in computer science, who wants to learn the necessary background and theorems.

    Computing Reviews


  • Understanding how genomes have evolved requires combining 'vertical' evolution (mutation and selection) with 'horizontal' events (notably recombination). The resulting intricate pattern of ancestry is called an 'ancestral recombination graph' (ARG). Dan Gusfield has been a leading figure in their study for many years. His latest book ReCombinatorics provides a fascinating and engaging account of the combinatorial and algorithmic properties of ARGs and related phylogenetic networks. Its wealth of recent results—for both newcomers and experts alike—offers a much-needed treatment to better link phylogenetics and population genetics.

    Mike Steel

    Professor of Mathematics and Statistics, University of Canterbury; Fellow of the Royal Society of New Zealand (FRSNZ); and coauthor of Phylogenetics

  • ReCombinatorics does a brilliant job laying out rigorous solutions to the haplotype phasing problem under the constraint that there is only limited recombination. This proves to be a surprisingly central problem in human population genetics, and the sections dealing with testing genetic association using methods based on the haplotype tree and on ancestral recombination graphs have a mathematical precision combined with excellent figures and pseudocode to guide the reader.

    Andrew G. Clark

    Jacob Gould Schurman Professor of Population Genetics, Cornell University

  • This is an absolutely beautifully written book, and should be essential reading for anyone wishing to understand phylogenetic networks, whether from a population genetics or a phylogenetics viewpoint. What is most impressive is the wonderful discussion of the history of ideas and techniques in these fields, so that even a non-mathematician can learn a great deal. For mathematically inclined researchers, this may be one of the most important and useful books in computational biology they'll ever read.

    Tandy Warnow

    Founder Professor of Bioengineering and Computer Science, University of Illinois at Urbana-Champaign