Histories of sequences in the coalescent model with recombination can be si
mulated using an algorithm that takes as input a sample of extant sequences
. The algorithm traces the history of the sequences going back in time, enc
ountering recombinations and coalescence (duplications) until the ancestral
material is located on one sequence for homologous positions in the presen
t sequences. Here an alternative algorithm is formulated not as going back
in time and operating on sequences, but by moving spatially along the seque
nces, updating the history of the sequences as recombination points are enc
ountered. This algorithm focuses on spatial aspects of the coalescent with
recombination rather than on temporal aspects as is the case of familiar al
gorithms. Mathematical results related to spatial aspects of the coalescent
with recombination are derived. (C) 1999 Academic Press.