BACKGROUND
an unexpected observation from the early genome sequencing era has been the extent to which different sets of putatively orthologous genes often yield strongly supported but incompatible tree topologies.
whether this disagreement is due primarily to violations of phylogenetic assumptions or to lateral genetic transfer  is still the subject of fierce debate  <cit> .
where one or more lgt events are suspected as a cause of topological differences between trees, it is often desirable to identify the lineages implicated, and if possible the direction of transfer  as well.
the correct identification of these events depends on the size and shape of the trees being compared, and the position of the lgt events within these trees.
when taken in aggregate, the lgt events implied by many trees can reveal information about major pathways of gene sharing between closely and distantly related organisms  <cit> .
deduction of lgt events from phylogenetic trees is often based on the implicit or explicit idea of a reference tree that accurately describes the evolutionary relationships between the organisms under consideration  <cit> .
in the absence of statistical bias, complications of paralogy, and lgt, all strongly supported gene or protein trees would agree with this reference topology.
even if the reference tree is simply an amalgam of many trees based on molecular sequence , the implied 'organismal' history will be represented as a strictly bifurcating hierarchy with a defined point of origin in time .
test trees inferred from a single gene or protein, or even a concatenated set of such sequences, will have no obvious rooting unless uniform rates of evolution  are assumed, in which case the tree can be midpoint rooted  <cit> , or if the inferred gene tree is sufficiently similar to the reference tree such that the root of the latter can be confidently assigned to the former.
since a strict molecular clock assumption is frequently violated by empirical data  <cit> , and the rooting of test trees may not be obvious in the face of lgt and biased evolution, comparisons between a rooted reference tree and one or more unrooted 'test' trees have the strongest evolutionary justification and are more general than comparisons between two rooted trees.
another important component of tree comparisons is the ability to deal with multifurcating nodes in trees that are incompletely resolved.
while most traditional phylogenetic methods produce completely resolved, strictly bifurcating trees as output, the statistical support  at some of these bifurcating nodes may be extremely weak.
thus, a disagreement between two trees that is based on a weakly supported topological feature may be of no interest, and it is often preferable to collapse the corresponding feature into a multifurcating node.
finally, in broad phylogenomic studies most sets of putatively orthologous genes or proteins will not cover the entire reference tree, so it may be necessary to 'project' the reference tree by removing the non-represented taxa before performing the comparison.
however, if inferred lgt events are to be compared, it must be possible to evaluate them all in light of the complete reference tree.
while many tree comparison metrics exist  <cit> , the subtree prune and regraft  distance  <cit>  is most relevant to the inference of lgt events.
a subtree prune and regraft operation on a binary tree t is performed by cutting any edge and thereby pruning subtree t, and then regrafting the subtree by the same cut edge to a new vertex obtained by dividing a pre-existing edge in t-t .
forced contraction is also applied to maintain the binary property  <cit> .
in the context of an lgt event, the edge that is regrafted onto corresponds to the donor taxon, while the edge that is cut corresponds to the position of the recipient taxon.
an edit path is any set of such spr operations that can be applied to a reference tree to yield a topology that is congruent with the inferred protein tree.
by extension, an optimal edit path is one of the  edit paths that is minimal or most-parsimonious for a given reference and test tree, such that there exists no edit path solution requiring fewer edit operations.
the length of the optimal edit path is the minimal spr distance or edit distance between the two trees.
the computational complexity of calculating the spr distance between unrooted binary trees is unknown.
a proof of np-hardness was given in hein et al.
<cit> , but was subsequently noted to be incorrect by allen and steel  <cit> , who further showed that the related tree bisection and reconnection  distance problem is np-hard but fixed parameter tractable  for unrooted binary trees.
bordewich et al.
<cit>  showed that computing the spr distance between rooted binary trees is also np-hard.
the problem that we are attempting to solve here is slightly different from the above in that we have a rooted binary reference tree and an unrooted, possibly multificating, test tree.
the bipartition measure we use to compare trees treats the reference tree as if it were unrooted and multifurcating when comparing it to the test tree.
thus the problem we are attempting to solve is the spr distance between unrooted multifurcating trees.
the complexity of this problem is open, but given the above results it is very likely to be np-hard.
a variety of algorithms for calculating or approximating spr and other distance measures between trees have been proposed in the literature.
hein et al.
<cit>  gave an algorithm that claimed to approximate spr distance between rooted phylogenetic trees to within a factor of  <dig>  however, allen and steel  <cit>  showed that it is actually the tree bisection and reconnection  distance that is being calculated, and in rodrigues et al.
<cit>  the approximation factor was shown to be  <dig>  lattrans  <cit>  calculates the minimum number of spr operations in the path between two rooted binary phylogenetic trees subject to certain direction of time constraints.
they identify two ways in which the  reference tree and the test tree can disagree , and give corresponding spr operations to fix them .
the algorithm is then to find an i-fat or h-fat vertex, fix it, and then recurse, checking that cycles  are not introduced.
the case where there may be multiple copies of a gene in a given species is also considered.
the algorithm has been used to identify up to  <dig> transfers in  <dig> leaves  <cit> , but in 1% of trials, the algorithm did not find a valid scenario with the real number of transfers.
the horizstory algorithm  <cit>  approximates the spr distance between rooted and possibly multifurcating phylogenetic trees.
the algorithm works by first eliminating rooted subtrees in the gene and reference trees that are in complete agreement, i.e.
are identical.
spr moves are then recursively proposed on the remaining trees until they are brought into agreement.
a unique feature of the algorithm is that is can propose phantom sister taxa, which are not represented in the reference tree because of incomplete taxon sampling, but donate genes to taxa that are represented in the analysis.
while this is a realistic innovation that was not implemented in previous algorithms, a given set of lateral transfers involving no phantom sisters can often be "explained" by a smaller set of transfers involving phantom sisters, in which case the algorithm will not find this larger set.
we have developed a new program eeep  for the inference of edit paths which imposes evolutionarily reasonable constraints on the search space of edits to reduce the overall computational burden while retaining the ability to produce accurate solution sets.
an important feature of eeep is the ability to partition the reference tree into regions of discordance, which are reconciled internally with no lgt events permitted between regions.
we also introduce the idea of tree distance ratchets, where proposed spr operations on a reference tree are only accepted if the resulting tree is more similar to the test tree , or at least as similar .
the partitioning of the reference tree and the use of tree distance ratchets do not always yield a complete solution set, but can reduce the running time of the algorithm by several orders of magnitude.
the eeep algorithm has been developed to address some of the problems outlined above, by considering unrooted, possibly multifurcating test trees while imposing time constraints on edit operations that are implied by a rooted reference tree.
a precursor to eeep was used to extract edit paths from a set of  <dig> prokaryotic genomes  <cit> , with frequently observed edits assigned to 'highways' of lgt between organisms.
this precursor version lacked many features that are implemented in the present release, including the permissive ratchets described below, and the ability to remove time constraints on edit operations, which is now a core component of the ratchets.
in the analysis presented here, we use random trees to compare the performance of eeep to that of two other recent lgt detection algorithms, and use eeep to recover edit paths for the large set of protein trees described in beiko et al.
<cit> .
we compare the edit distances inferred from this data set with similar distances derived from random trees to assess the extent to which vertical or horizontal signal dominates in the protein trees.
finally, examination of the distribution of phylogenetic distances spanned by inferred lgt events is used to determine whether most or all inferred events occur between closely related taxa  or if long-distance transfers are also implied.
RESULTS
benchmarking of eeep
the performance of eeep was evaluated with both simulated and empirical data.
random rooted and unrooted trees were generated and the performance  of eeep was compared to that of lattrans and horizstory for strictly bifurcating trees.
the following example, illustrated in figure  <dig>  shows the differences between the approaches of eeep, horizstory and lattrans, as applied to a reference tree  and corresponding rooted  or unrooted  test trees.
the differences between the trees may be resolved by a single lateral transfer in a number of ways, which are indicated with arrows in the figure.
lattrans proposes transfer scenarios a and b: the parent edge of leaf  <dig> donates to the parent edge of leaf  <dig>  or vice versa.
horizstory proposes three transfer scenarios, the first two  as for lattrans, and the third  being a phantom sister transfer.
the phantom sister edge joins the reference tree between the root and the pendant subtree covering taxa  <dig>   <dig>  and  <dig>  and this edge donates to the parent edge of leaf  <dig>  the effect is to cut the parent edge of leaf  <dig> and reattach it above leaves  <dig> and  <dig>  without the phantom sister interpretation this would represent a donation to descendant time violation.
for eeep with time constraints, four solutions are found: a and b as in lattrans and horizstory, and two further scenarios  where the edge joining the root of the reference tree to the pendant covering taxa  <dig> and  <dig> donates to the parent edge of  <dig>  and vice versa.
lattrans and horizstory do not propose these solutions, since scenarios d and e lead to a reference tree with a misplaced root.
a non-time constrained eeep search finds a further solution which corresponds to scenario c, the phantom sister solution found by horizstory.
another difference between the algorithms is the requirement that the test tree be rooted.
an example of the effect of root placement on path recovery is shown in figure  <dig>  the reference  and test  trees differ only in the positioning of the root, so eeep, which does not consider the rooting of the test tree, would not need to produce an edit path at all.
conversely, lattrans and horizstory would need to infer four sequential transfers to reconcile the first tree with the second, since taxa t <dig> through t <dig> would all need to be transferred to the other side of the root , one at a time.
random rooted binary phylogenetic trees were generated for n taxa as follows.
a bipartition on the integers from  <dig> to n was created by randomly cutting the list into two non-empty parts.
this bipartition then represents the edges adjacent to the root node of the tree being constructed.
each of the two induced partitions was then randomly split into two lists to create a further bipartitioning of these sets.
new bipartitions were then created recursively by cutting elements of previously created bipartitions into two sets until the bipartitions only consisted of singleton elements.
thus the tree was created by starting at the root and creating bipartitions  until the leaf nodes were reached.
sets of transfers were then applied to the rooted binary phylogenetic trees by choosing random donor and recipient edges to generate test trees.
no attempt was made to avoid time violations in generating these random edits.
in the case of eeep the test trees were then unrooted.
the leaf and transfer combinations that were tested are shown in table 1: for each of these combinations,  <dig> reference and test trees were generated, giving in total  <dig> reference and test tree pairs tested.
the programs were benchmarked on a cluster of  <dig>  ghz amd opteron computers running linux.
each process was limited to completing within  <dig> hours and using at most  <dig>  gb of ram.
comparisons of the performance of eeep, horizstory and lattrans on recovering edit paths for varying numbers of leaves and transfers in randomly generated trees are shown in table  <dig>  for horizstory the cases for which a solution was not found were all due to reaching the time limit of  <dig> hours.
the maximum ram used by horizstory was  <dig> mb.
for eeep, the limiting factor was ram, with no search taking more than  <dig> hours.
lattrans never exceeded the ram or time limits, and the small number of cases where no solution was found were likely due to limits in the heuristics of the algorithm.
overall, lattrans found a solution in  <dig> % of cases, horizstory in  <dig> % and eeep in  <dig> %.
lattrans performed remarkably well on every tree size, failing only in a small minority of cases on the set of 100-taxon trees.
horizstory recovered an edit path from every tree of size  <dig>   <dig>  and  <dig>  but many of the edit paths in larger trees could not be recovered in less than five hours.
the success of several different types of eeep run, as well as horizstory and lattrans, in recovering edit paths from trees of various sizes is shown in figure  <dig>  eeep runs performed without ratchets failed to recover edit paths from many trees of size  <dig> or greater, with the worst performance obtained from runs that did not partition trees into regions of discordance  and those that did not make use of time constraints.
while the performance of eeep dropped with increasing tree size, the use of ratchets substantially improved the recovery of edit paths, with the permissive test tree ratchet yielding a modest improvement over the standard eeep run, and the strict ratchet recovering paths from > 80% of all trees containing  <dig> or fewer taxa, and 66% of all trees with  <dig> taxa.
we assessed the ability of each of the four types of ratchet to recover the correct edit distance as determined by the unratcheted runs.
for tree comparisons in which the unratcheted run returned a solution, each type of ratchet was able to recover the correct edit distance from >90% of all data sets, with both permissive ratchets yielding better accuracy  than the strict reference tree  and test tree  ratchets.
thus, the ratchets provide a considerable increase in speed, with a small sacrifice of accuracy.
phylogenomic analysis of  <dig> prokaryotic taxa
eeep was also used to infer pathways of lgt by comparing a set of  <dig>  <dig> protein test trees derived from the microbial data set described in beiko et al.
<cit> , to a reference supertree constructed using the mrp algorithm  <cit>  and rooted to follow the  paradigm of bacteria and archaea as separate, monophyletic domains  <cit> .
these trees were inferred from aligned, putatively orthologous sequences using version  <dig>  beta of the mrbayes program  <cit> , which samples from a likelihood distribution of trees and generates a posterior probability estimate for each possible bipartitioning of taxa.
we considered only those bipartitions with a posterior probability  of  <dig>  or greater, which immediately eliminated  <dig> data sets from consideration, since the inferred trees for these sets had no bipartitions with support above this threshold.
while some of the differences between the protein trees and reference supertree are likely due to violations of phylogenetic assumptions or failure of ortholog mapping and sequence alignment, an extensive set of statistical tests and parsimony analysis of insert/delete states were used in beiko et al.
<cit>  to show that discordant trees were not simply a consequence of inadequate methods or biased sequenced evolution.
the  <dig>  <dig> trees with at least one bipartition supported at pp =  <dig>  were submitted individually to eeep, with five different types of ratchet constraints applied in separate runs: a) no constraint; b) a permissive test tree distance ratchet; c) a strict test tree distance ratchet; d) a permissive reference tree distance ratchet; and e) a strict reference tree distance ratchet.
these runs were constrained to run within  <dig> gb of ram, and the success rate of each method in recovering a solution was assessed.
the edit distance and path properties of inferred protein trees were compared with similar properties of randomly generated trees.
in the majority of cases, eeep runs of even the largest data sets completed in less than  <dig> minutes, either successfully returning a set of edit paths, or reaching the imposed memory limit and terminating.
the number of inferred lgt events within a given set of trees expresses the extent to which horizontal acquisition of genes has influenced genome evolution in the represented taxa.
simulations of random lgt events via multiple spr permutations can be used to distinguish empirical trees from random trees, since the former should only approximate the latter when lgt is rampant and sufficiently random  <cit> .
thus, if random lgt events dominate a given dataset, then the spr distance between any inferred tree and the reference tree should be similar to the average distance between pairs of random trees.
if vertical inheritance  dominates in a set of inferred trees, then the number of edit paths observed should be smaller.
to assess the significance of the average similarity between reference and test trees, we should know the distribution of edit distances between pairs of random trees.
the average distance between a pair of trees is not known, though song  <cit>  presents a formula for the number of trees that are separated from a given tree by a single spr operation.
we must therefore resort to building an empirical distribution from random pairs of trees.
another problem is the bias toward non-recovery of edit paths from larger trees will yield underestimates of mean edit distance for these sets.
consequently, we performed comparisons between many pairs of random trees to generate a background distribution of edit distances between trees, and concentrated on trees with  <dig> or fewer taxa, in a range where eeep was able to recover edit path solutions for every protein tree tested above.
figure  <dig> shows the mean edit path length recovered for each size class of protein trees, compared to the maximum possible edit path length  and the mean edit path length recovered from comparisons between  <dig> pairs of random trees.
for comparisons between random trees, each unit increase in taxon size yields an increase of  <dig>  in average edit distance .
when protein trees of size  <dig> to  <dig> are considered, each unit increase yields an increase of only  <dig>  in average edit distance .
extending the model to include protein trees of sizes  <dig> to  <dig> yields a similar slope , with a reduced linear fit coefficient of  <dig>  due to instability in mean estimates for larger protein tree sizes.
since the slope of this relationship between inferred protein trees is approximately 1/ <dig> of the equivalent relationship between random trees, it is clear that there is a strong cohesive, likely vertical, signal in the protein trees.
tree edits induced by an spr operation can implicate lineages that are separated by any number of internal branches.
this concept of 'short' versus 'long' edits is captured in measures such as the nearest-neighbor interchange  distance  <cit> , but must be assessed indirectly in the case of spr operations.
the count or total length of internal branches separating the donor and recipient lineages can be used to assess the 'length' of an edit operation  <cit> .
for a fixed number of edits, the number of regions of discordance and other tree distance measures can be used as well: long-distance edits will tend to overlap, yielding fewer and larger regions of discordance, and bipartition-based measures such as the robinson-foulds distance will be larger due to the greater number of bipartitions disrupted by edit operations.
figure  <dig> shows the normalized reference tree distance  for several combinations of tree size and number of edits, for inferred protein trees and the randomly permuted trees described earlier in "benchmarking of eeep" above.
while the average normalized reference tree distance is invariably larger in the set of randomly permuted trees, there is a wide distribution of normalized distances in both types of tree, evidenced by the large standard deviations associated with each group.
if α =  <dig>  is used as the cutoff for statistical significance, and divided by ten to yield a bonneferroni-corrected threshold of  <dig> , then in only three out of ten classes  is the difference between experimental and random trees statistically significant.
thus, edits inferred from protein trees tend to be 'shorter' on average than randomly induced edits, but there is considerable overlap between the distributions of the two sets.
there is a similar tendency of random edits to associate into fewer regions of discordance.
when trees with >  <dig> edit  were considered, in all cases a majority of trees contained only a single discordant region.
however, a larger minority of protein trees contained multiple regions of discordance  than did the randomly permuted trees .
this observation is consistent with the ability of eeep to recover edit path solutions for very large protein trees with >  <dig> edits, due to partitioning of the tree into multiple regions of discordance, while randomly permuted trees of a similar size often could not be resolved.
while inferred protein trees showed a high degree of similarity  to a reference supertree, the number of internal edges spanned by inferred edit operations was only marginally shorter than those generated under a random model.
while statistical and biological hypotheses tend to predict 'local' topological rearrangements , in our data set we frequently inferred lgt events between prokaryotic phyla and between the bacterial and archaeal domains.
the dissimilarity between orthologous sequences from different phyla precludes homologous recombination, which requires a high degree of sequence similarity, so these transfers require illegitimate recombination to integrate the donor dna into the recipient genome  <cit> .
the existence of these transfers is supported by phylogenetic profile analysis, which shows a patchy distribution for many sets of genes that cannot be explained through loss alone.
relationship between discordant bipartitions and edit distance
when an spr operation is performed on a reference tree, the internal edges in the original tree that connect the donor and recipient taxa will be incompatible with edges in the derived tree, since the bipartitions of taxa implied by these edges are not found in the new tree.
this chain of internal edges defines a 'trail of destruction' that can be used to set minimum bounds on the number of edit operations needed to reconcile the two trees .
for each protein tree that could be reconciled with the reference tree by eeep, we compared the minimum edit distance recovered by eeep with the total number of endpoints associated with the trails of destruction in each protein tree.
for the  <dig> protein trees with an edit distance of  <dig> relative to the supertree, the result is trivial: a single edit operation on a reference tree induces a trail of destruction containing exactly two endpoints, with the donor and recipient lineages at opposite ends of the chain.
each of these trees must therefore contain a single linear trail.
each subsequent edit operation can increase the number of endpoints by  <dig>   <dig>  or  <dig> with respect to the original reference tree, so among protein trees with an edit distance d ≥  <dig>  the number of endpoints is bounded by  <dig> and 2d.
if 2d or 2d -  <dig> endpoints are observed in comparing a reference with a test tree, then d is guaranteed to be the minimal edit distance.
of the  <dig> protein trees with d ≥  <dig>   <dig>  could be confirmed as minimal edit paths with this approach.
two simple examples of trails of destruction from overlapping edit operations are shown in figure 8: an example where the number of endpoints is equal to 2d , and a case where the endpoint count is equal only to d .
CONCLUSIONS
all three algorithms tested here on random trees were limited to some extent by computational resources: the amount of ram was typically limiting for eeep, and running time for horizstory.
lattrans is extremely fast and efficient relative to the other algorithms, but its requirement of strictly bifurcating, rooted trees makes it an inappropriate choice for phylogenomic analyses.
the most straightforward approach to increasing the range of problems that can be resolved with eeep is through the use of faster computers with more memory, and parallelization.
however, the 'trails of destruction' give interesting clues about the nature and number of spr operations that are required, and should be considered as a possible source of new ways to refine the search for most-parsimonious edit paths.
we have used eeep to reconcile a reference supertree comprising  <dig> organisms with  <dig>  <dig> microbial protein trees as part of a large phylogenetic study  <cit> .
not surprisingly, for these data the inferred protein trees were far more similar to each other and to the reference supertree than were randomly generated pairs of reference and test trees.
this similarity reflects cohesive signal in the inferred protein trees that is congruent with the organismal history, e.g.
'vertical' inheritance from parent to offspring.
since vertical signal dominates in this data set, there is no evidence that lgt has destroyed the organismal signature that should be evident in sequence phylogenies.
as statistical tests and corrections for violations of basic phylogenetic assumptions improve  <cit> , and as hypotheses about the 'transferability' of different types of gene are refined  <cit> , the underlying organismal history initially suggested by 16s rrna analysis and refined using other data sets should solidify.
final words – interpreting edit paths
a final challenge in the inference of edit paths is the interpretation of multiple, equally parsimonious edit paths.
the most frequent examples of multiple edit paths involve simple permutations of the same set of edits, which imply that there is no time constraint on the order in which those edits can occur.
also common are symmetrical exchanges, where a gene transfer event involving two taxa yields the same effect on tree topology regardless of which taxon is the donor and which the recipient.
in these cases, information about the partners obligately involved in the exchange may be clear, and interpretable in light of hypotheses about preferential gene sharing between organisms, but the direction of transfer cannot be deduced solely from the tree topology.
finally, a given comparison of trees can produce multiple edit paths that suggest partially overlapping or non-overlapping sets of transfer partners.
these cases typically identify a small set of possible exchange partners, but fail to uniquely identify each pair of taxa participating in a transfer.
analysis of large sets of obligate and possible transfers can reveal trends that correspond to 'highways' of gene sharing  <cit> , but conclusions about the sharing history of individual genes may be unclear.
can other information be used to uniquely identify the donor and recipient implicated in an lgt event?
while eeep, horizstory and lattrans consider only the branching order of phylogenetic trees, other features of the trees and the underlying sequences can potentially convey useful information as well.
if genome-to-genome 'distances' are implied either in the reference tree or through some other method, then sequence-to-sequence distances that are much shorter than expected may identify the partners in a recent genetic transfer event.
this type of assessment relies on the assumption that sequences have evolved in a clock-like fashion, which may be frequently violated if transferred sequences evolve more rapidly in the recipient genome due to amelioration pressures or functional duplication  <cit> .
the topological analysis performed by eeep may also be complemented by the use of surrogate methods which consider the deviation of residue composition within a gene from that of the 'background' genome sequence  <cit> .
most of these methods can be applied to a single genome, so the detection of recently acquired sequences is not dependent on having a relative of the donor sampled as well.
however, since these methods typically rely on genomic sequence bias to generate a null distribution, they are particularly sensitive to amelioration  <cit>  and the overlap among the predictions of different methods is quite poor  <cit> .
given the evidence that different surrogate methods may detect different types of lgt events, or events of different ages  <cit> , the best strategy is to carefully consider the results of several different approaches.

 an unexpected observation from the early genome sequencing era has been the extent to which different sets of putatively orthologous genes often yield strongly supported but incompatible tree topologies. whether this disagreement is due primarily to violations of phylogenetic assumptions or to lateral genetic transfer is still the subject of fierce debate. where one or more lgt events are suspected as a cause of topological differences between trees, it is often desirable to identify the lineages implicated, and if possible the direction of transfer as well. the correct identification of these events depends on the size and shape of the trees being compared, and the position of the lgt events within these trees. when taken in aggregate, the lgt events implied by many trees can reveal information about major pathways of gene sharing between closely and distantly related organisms. deduction of lgt events from phylogenetic trees is often based on the implicit or explicit idea of a reference tree that accurately describes the evolutionary relationships between the organisms under consideration. in the absence of statistical bias, complications of paralogy, and lgt, all strongly supported gene or protein trees would agree with this reference topology. even if the reference tree is simply an amalgam of many trees based on molecular sequence, the implied'organismal' history will be represented as a strictly bifurcating hierarchy with a defined point of origin in time. test trees inferred from a single gene or protein, or even a concatenated set of such sequences, will have no obvious rooting unless uniform rates of evolution are assumed, in which case the tree can be midpoint rooted, or if the inferred gene tree is sufficiently similar to the reference tree such that the root of the latter can be confidently assigned to the former. since a strict molecular clock assumption is frequently violated by empirical data, and the rooting of test trees may not be obvious in the face of lgt and biased evolution, comparisons between a rooted reference tree and one or more unrooted'test' trees have the strongest evolutionary justification and are more general than comparisons between two rooted trees. another important component of tree comparisons is the ability to deal with multifurcating nodes in trees that are incompletely resolved. while most traditional phylogenetic methods produce completely resolved, strictly bifurcating trees as output, the statistical support at some of these bifurcating nodes may be extremely weak. thus, a disagreement between two trees that is based on a weakly supported topological feature may be of no interest, and it is often preferable to collapse the corresponding feature into a multifurcating node. finally, in broad phylogenomic studies most sets of putatively orthologous genes or proteins will not cover the entire reference tree, so it may be necessary to'project' the reference tree by removing the non-represented taxa before performing the comparison. however, if inferred lgt events are to be compared, it must be possible to evaluate them all in light of the complete reference tree. while many tree comparison metrics exist, the subtree prune and regraft distance is most relevant to the inference of lgt events. a subtree prune and regraft operation on a binary tree t is performed by cutting any edge and thereby pruning subtree t, and then regrafting the subtree by the same cut edge to a new vertex obtained by dividing a pre-existing edge in t-t. forced contraction is also applied to maintain the binary property. in the context of an lgt event, the edge that is regrafted onto corresponds to the donor taxon, while the edge that is cut corresponds to the position of the recipient taxon. an edit path is any set of such spr operations that can be applied to a reference tree to yield a topology that is congruent with the inferred protein tree. by extension, an optimal edit path is one of the edit paths that is minimal or most-parsimonious for a given reference and test tree, such that there exists no edit path solution requiring fewer edit operations. the length of the optimal edit path is the minimal spr distance or edit distance between the two trees. the computational complexity of calculating the spr distance between unrooted binary trees is unknown. a proof of np-hardness was given in hein et al., but was subsequently noted to be incorrect by allen and steel, who further showed that the related tree bisection and reconnection distance problem is np-hard but fixed parameter tractable for unrooted binary trees. bordewich et al. showed that computing the spr distance between rooted binary trees is also np-hard. the problem that we are attempting to solve here is slightly different from the above in that we have a rooted binary reference tree and an unrooted, possibly multificating, test tree. the bipartition measure we use to compare trees treats the reference tree as if it were unrooted and multifurcating when comparing it to the test tree. thus the problem we are attempting to solve is the spr distance between unrooted multifurcating trees. the complexity of this problem is open, but given the above results it is very likely to be np-hard. a variety of algorithms for calculating or approximating spr and other distance measures between trees have been proposed in the literature. hein et al. gave an algorithm that claimed to approximate spr distance between rooted phylogenetic trees to within a factor of however, allen and steel showed that it is actually the tree bisection and reconnection distance that is being calculated, and in rodrigues et al. the approximation factor was shown to be lattrans calculates the minimum number of spr operations in the path between two rooted binary phylogenetic trees subject to certain direction of time constraints. they identify two ways in which the reference tree and the test tree can disagree, and give corresponding spr operations to fix them. the algorithm is then to find an i-fat or h-fat vertex, fix it, and then recurse, checking that cycles are not introduced. the case where there may be multiple copies of a gene in a given species is also considered. the algorithm has been used to identify up to transfers in leaves, but in 1% of trials, the algorithm did not find a valid scenario with the real number of transfers. the horizstory algorithm approximates the spr distance between rooted and possibly multifurcating phylogenetic trees. the algorithm works by first eliminating rooted subtrees in the gene and reference trees that are in complete agreement, i.e. are identical. spr moves are then recursively proposed on the remaining trees until they are brought into agreement. a unique feature of the algorithm is that is can propose phantom sister taxa, which are not represented in the reference tree because of incomplete taxon sampling, but donate genes to taxa that are represented in the analysis. while this is a realistic innovation that was not implemented in previous algorithms, a given set of lateral transfers involving no phantom sisters can often be "explained" by a smaller set of transfers involving phantom sisters, in which case the algorithm will not find this larger set. we have developed a new program eeep for the inference of edit paths which imposes evolutionarily reasonable constraints on the search space of edits to reduce the overall computational burden while retaining the ability to produce accurate solution sets. an important feature of eeep is the ability to partition the reference tree into regions of discordance, which are reconciled internally with no lgt events permitted between regions. we also introduce the idea of tree distance ratchets, where proposed spr operations on a reference tree are only accepted if the resulting tree is more similar to the test tree, or at least as similar. the partitioning of the reference tree and the use of tree distance ratchets do not always yield a complete solution set, but can reduce the running time of the algorithm by several orders of magnitude. the eeep algorithm has been developed to address some of the problems outlined above, by considering unrooted, possibly multifurcating test trees while imposing time constraints on edit operations that are implied by a rooted reference tree. a precursor to eeep was used to extract edit paths from a set of prokaryotic genomes, with frequently observed edits assigned to'highways' of lgt between organisms. this precursor version lacked many features that are implemented in the present release, including the permissive ratchets described below, and the ability to remove time constraints on edit operations, which is now a core component of the ratchets. in the analysis presented here, we use random trees to compare the performance of eeep to that of two other recent lgt detection algorithms, and use eeep to recover edit paths for the large set of protein trees described in beiko et al.. we compare the edit distances inferred from this data set with similar distances derived from random trees to assess the extent to which vertical or horizontal signal dominates in the protein trees. finally, examination of the distribution of phylogenetic distances spanned by inferred lgt events is used to determine whether most or all inferred events occur between closely related taxa or if long-distance transfers are also implied.  benchmarking of eeep the performance of eeep was evaluated with both simulated and empirical data. random rooted and unrooted trees were generated and the performance of eeep was compared to that of lattrans and horizstory for strictly bifurcating trees. the following example, illustrated in figure shows the differences between the approaches of eeep, horizstory and lattrans, as applied to a reference tree and corresponding rooted or unrooted test trees. the differences between the trees may be resolved by a single lateral transfer in a number of ways, which are indicated with arrows in the figure. lattrans proposes transfer scenarios a and b: the parent edge of leaf donates to the parent edge of leaf or vice versa. horizstory proposes three transfer scenarios, the first two as for lattrans, and the third being a phantom sister transfer. the phantom sister edge joins the reference tree between the root and the pendant subtree covering taxa and and this edge donates to the parent edge of leaf the effect is to cut the parent edge of leaf and reattach it above leaves and without the phantom sister interpretation this would represent a donation to descendant time violation. for eeep with time constraints, four solutions are found: a and b as in lattrans and horizstory, and two further scenarios where the edge joining the root of the reference tree to the pendant covering taxa and donates to the parent edge of and vice versa. lattrans and horizstory do not propose these solutions, since scenarios d and e lead to a reference tree with a misplaced root. a non-time constrained eeep search finds a further solution which corresponds to scenario c, the phantom sister solution found by horizstory. another difference between the algorithms is the requirement that the test tree be rooted. an example of the effect of root placement on path recovery is shown in figure the reference and test trees differ only in the positioning of the root, so eeep, which does not consider the rooting of the test tree, would not need to produce an edit path at all. conversely, lattrans and horizstory would need to infer four sequential transfers to reconcile the first tree with the second, since taxa t through t would all need to be transferred to the other side of the root, one at a time. random rooted binary phylogenetic trees were generated for n taxa as follows. a bipartition on the integers from to n was created by randomly cutting the list into two non-empty parts. this bipartition then represents the edges adjacent to the root node of the tree being constructed. each of the two induced partitions was then randomly split into two lists to create a further bipartitioning of these sets. new bipartitions were then created recursively by cutting elements of previously created bipartitions into two sets until the bipartitions only consisted of singleton elements. thus the tree was created by starting at the root and creating bipartitions until the leaf nodes were reached. sets of transfers were then applied to the rooted binary phylogenetic trees by choosing random donor and recipient edges to generate test trees. no attempt was made to avoid time violations in generating these random edits. in the case of eeep the test trees were then unrooted. the leaf and transfer combinations that were tested are shown in table 1: for each of these combinations, reference and test trees were generated, giving in total reference and test tree pairs tested. the programs were benchmarked on a cluster of ghz amd opteron computers running linux. each process was limited to completing within hours and using at most gb of ram. comparisons of the performance of eeep, horizstory and lattrans on recovering edit paths for varying numbers of leaves and transfers in randomly generated trees are shown in table for horizstory the cases for which a solution was not found were all due to reaching the time limit of hours. the maximum ram used by horizstory was mb. for eeep, the limiting factor was ram, with no search taking more than hours. lattrans never exceeded the ram or time limits, and the small number of cases where no solution was found were likely due to limits in the heuristics of the algorithm. overall, lattrans found a solution in % of cases, horizstory in % and eeep in %. lattrans performed remarkably well on every tree size, failing only in a small minority of cases on the set of 100-taxon trees. horizstory recovered an edit path from every tree of size and but many of the edit paths in larger trees could not be recovered in less than five hours. the success of several different types of eeep run, as well as horizstory and lattrans, in recovering edit paths from trees of various sizes is shown in figure eeep runs performed without ratchets failed to recover edit paths from many trees of size or greater, with the worst performance obtained from runs that did not partition trees into regions of discordance and those that did not make use of time constraints. while the performance of eeep dropped with increasing tree size, the use of ratchets substantially improved the recovery of edit paths, with the permissive test tree ratchet yielding a modest improvement over the standard eeep run, and the strict ratchet recovering paths from > 80% of all trees containing or fewer taxa, and 66% of all trees with taxa. we assessed the ability of each of the four types of ratchet to recover the correct edit distance as determined by the unratcheted runs. for tree comparisons in which the unratcheted run returned a solution, each type of ratchet was able to recover the correct edit distance from >90% of all data sets, with both permissive ratchets yielding better accuracy than the strict reference tree and test tree ratchets. thus, the ratchets provide a considerable increase in speed, with a small sacrifice of accuracy. phylogenomic analysis of prokaryotic taxa eeep was also used to infer pathways of lgt by comparing a set of protein test trees derived from the microbial data set described in beiko et al., to a reference supertree constructed using the mrp algorithm and rooted to follow the paradigm of bacteria and archaea as separate, monophyletic domains. these trees were inferred from aligned, putatively orthologous sequences using version beta of the mrbayes program, which samples from a likelihood distribution of trees and generates a posterior probability estimate for each possible bipartitioning of taxa. we considered only those bipartitions with a posterior probability of or greater, which immediately eliminated data sets from consideration, since the inferred trees for these sets had no bipartitions with support above this threshold. while some of the differences between the protein trees and reference supertree are likely due to violations of phylogenetic assumptions or failure of ortholog mapping and sequence alignment, an extensive set of statistical tests and parsimony analysis of insert/delete states were used in beiko et al. to show that discordant trees were not simply a consequence of inadequate methods or biased sequenced evolution. the trees with at least one bipartition supported at pp = were submitted individually to eeep, with five different types of ratchet constraints applied in separate runs: a) no constraint; b) a permissive test tree distance ratchet; c) a strict test tree distance ratchet; d) a permissive reference tree distance ratchet; and e) a strict reference tree distance ratchet. these runs were constrained to run within gb of ram, and the success rate of each method in recovering a solution was assessed. the edit distance and path properties of inferred protein trees were compared with similar properties of randomly generated trees. in the majority of cases, eeep runs of even the largest data sets completed in less than minutes, either successfully returning a set of edit paths, or reaching the imposed memory limit and terminating. the number of inferred lgt events within a given set of trees expresses the extent to which horizontal acquisition of genes has influenced genome evolution in the represented taxa. simulations of random lgt events via multiple spr permutations can be used to distinguish empirical trees from random trees, since the former should only approximate the latter when lgt is rampant and sufficiently random. thus, if random lgt events dominate a given dataset, then the spr distance between any inferred tree and the reference tree should be similar to the average distance between pairs of random trees. if vertical inheritance dominates in a set of inferred trees, then the number of edit paths observed should be smaller. to assess the significance of the average similarity between reference and test trees, we should know the distribution of edit distances between pairs of random trees. the average distance between a pair of trees is not known, though song presents a formula for the number of trees that are separated from a given tree by a single spr operation. we must therefore resort to building an empirical distribution from random pairs of trees. another problem is the bias toward non-recovery of edit paths from larger trees will yield underestimates of mean edit distance for these sets. consequently, we performed comparisons between many pairs of random trees to generate a background distribution of edit distances between trees, and concentrated on trees with or fewer taxa, in a range where eeep was able to recover edit path solutions for every protein tree tested above. figure shows the mean edit path length recovered for each size class of protein trees, compared to the maximum possible edit path length and the mean edit path length recovered from comparisons between pairs of random trees. for comparisons between random trees, each unit increase in taxon size yields an increase of in average edit distance. when protein trees of size to are considered, each unit increase yields an increase of only in average edit distance. extending the model to include protein trees of sizes to yields a similar slope, with a reduced linear fit coefficient of due to instability in mean estimates for larger protein tree sizes. since the slope of this relationship between inferred protein trees is approximately 1/ of the equivalent relationship between random trees, it is clear that there is a strong cohesive, likely vertical, signal in the protein trees. tree edits induced by an spr operation can implicate lineages that are separated by any number of internal branches. this concept of'short' versus'long' edits is captured in measures such as the nearest-neighbor interchange distance, but must be assessed indirectly in the case of spr operations. the count or total length of internal branches separating the donor and recipient lineages can be used to assess the'length' of an edit operation. for a fixed number of edits, the number of regions of discordance and other tree distance measures can be used as well: long-distance edits will tend to overlap, yielding fewer and larger regions of discordance, and bipartition-based measures such as the robinson-foulds distance will be larger due to the greater number of bipartitions disrupted by edit operations. figure shows the normalized reference tree distance for several combinations of tree size and number of edits, for inferred protein trees and the randomly permuted trees described earlier in "benchmarking of eeep" above. while the average normalized reference tree distance is invariably larger in the set of randomly permuted trees, there is a wide distribution of normalized distances in both types of tree, evidenced by the large standard deviations associated with each group. if α = is used as the cutoff for statistical significance, and divided by ten to yield a bonneferroni-corrected threshold of, then in only three out of ten classes is the difference between experimental and random trees statistically significant. thus, edits inferred from protein trees tend to be'shorter' on average than randomly induced edits, but there is considerable overlap between the distributions of the two sets. there is a similar tendency of random edits to associate into fewer regions of discordance. when trees with > edit were considered, in all cases a majority of trees contained only a single discordant region. however, a larger minority of protein trees contained multiple regions of discordance than did the randomly permuted trees. this observation is consistent with the ability of eeep to recover edit path solutions for very large protein trees with > edits, due to partitioning of the tree into multiple regions of discordance, while randomly permuted trees of a similar size often could not be resolved. while inferred protein trees showed a high degree of similarity to a reference supertree, the number of internal edges spanned by inferred edit operations was only marginally shorter than those generated under a random model. while statistical and biological hypotheses tend to predict'local' topological rearrangements, in our data set we frequently inferred lgt events between prokaryotic phyla and between the bacterial and archaeal domains. the dissimilarity between orthologous sequences from different phyla precludes homologous recombination, which requires a high degree of sequence similarity, so these transfers require illegitimate recombination to integrate the donor dna into the recipient genome. the existence of these transfers is supported by phylogenetic profile analysis, which shows a patchy distribution for many sets of genes that cannot be explained through loss alone. relationship between discordant bipartitions and edit distance when an spr operation is performed on a reference tree, the internal edges in the original tree that connect the donor and recipient taxa will be incompatible with edges in the derived tree, since the bipartitions of taxa implied by these edges are not found in the new tree. this chain of internal edges defines a'trail of destruction' that can be used to set minimum bounds on the number of edit operations needed to reconcile the two trees. for each protein tree that could be reconciled with the reference tree by eeep, we compared the minimum edit distance recovered by eeep with the total number of endpoints associated with the trails of destruction in each protein tree. for the protein trees with an edit distance of relative to the supertree, the result is trivial: a single edit operation on a reference tree induces a trail of destruction containing exactly two endpoints, with the donor and recipient lineages at opposite ends of the chain. each of these trees must therefore contain a single linear trail. each subsequent edit operation can increase the number of endpoints by or with respect to the original reference tree, so among protein trees with an edit distance d ≥ the number of endpoints is bounded by and 2d. if 2d or 2d - endpoints are observed in comparing a reference with a test tree, then d is guaranteed to be the minimal edit distance. of the protein trees with d ≥ could be confirmed as minimal edit paths with this approach. two simple examples of trails of destruction from overlapping edit operations are shown in figure 8: an example where the number of endpoints is equal to 2d, and a case where the endpoint count is equal only to d.  all three algorithms tested here on random trees were limited to some extent by computational resources: the amount of ram was typically limiting for eeep, and running time for horizstory. lattrans is extremely fast and efficient relative to the other algorithms, but its requirement of strictly bifurcating, rooted trees makes it an inappropriate choice for phylogenomic analyses. the most straightforward approach to increasing the range of problems that can be resolved with eeep is through the use of faster computers with more memory, and parallelization. however, the'trails of destruction' give interesting clues about the nature and number of spr operations that are required, and should be considered as a possible source of new ways to refine the search for most-parsimonious edit paths. we have used eeep to reconcile a reference supertree comprising organisms with microbial protein trees as part of a large phylogenetic study. not surprisingly, for these data the inferred protein trees were far more similar to each other and to the reference supertree than were randomly generated pairs of reference and test trees. this similarity reflects cohesive signal in the inferred protein trees that is congruent with the organismal history, e.g.'vertical' inheritance from parent to offspring. since vertical signal dominates in this data set, there is no evidence that lgt has destroyed the organismal signature that should be evident in sequence phylogenies. as statistical tests and corrections for violations of basic phylogenetic assumptions improve, and as hypotheses about the'transferability' of different types of gene are refined, the underlying organismal history initially suggested by 16s rrna analysis and refined using other data sets should solidify. final words – interpreting edit paths a final challenge in the inference of edit paths is the interpretation of multiple, equally parsimonious edit paths. the most frequent examples of multiple edit paths involve simple permutations of the same set of edits, which imply that there is no time constraint on the order in which those edits can occur. also common are symmetrical exchanges, where a gene transfer event involving two taxa yields the same effect on tree topology regardless of which taxon is the donor and which the recipient. in these cases, information about the partners obligately involved in the exchange may be clear, and interpretable in light of hypotheses about preferential gene sharing between organisms, but the direction of transfer cannot be deduced solely from the tree topology. finally, a given comparison of trees can produce multiple edit paths that suggest partially overlapping or non-overlapping sets of transfer partners. these cases typically identify a small set of possible exchange partners, but fail to uniquely identify each pair of taxa participating in a transfer. analysis of large sets of obligate and possible transfers can reveal trends that correspond to'highways' of gene sharing, but conclusions about the sharing history of individual genes may be unclear. can other information be used to uniquely identify the donor and recipient implicated in an lgt event? while eeep, horizstory and lattrans consider only the branching order of phylogenetic trees, other features of the trees and the underlying sequences can potentially convey useful information as well. if genome-to-genome'distances' are implied either in the reference tree or through some other method, then sequence-to-sequence distances that are much shorter than expected may identify the partners in a recent genetic transfer event. this type of assessment relies on the assumption that sequences have evolved in a clock-like fashion, which may be frequently violated if transferred sequences evolve more rapidly in the recipient genome due to amelioration pressures or functional duplication. the topological analysis performed by eeep may also be complemented by the use of surrogate methods which consider the deviation of residue composition within a gene from that of the'background' genome sequence. most of these methods can be applied to a single genome, so the detection of recently acquired sequences is not dependent on having a relative of the donor sampled as well. however, since these methods typically rely on genomic sequence bias to generate a null distribution, they are particularly sensitive to amelioration and the overlap among the predictions of different methods is quite poor. given the evidence that different surrogate methods may detect different types of lgt events, or events of different ages, the best strategy is to carefully consider the results of several different approaches. 
the performance of eeep compares favourably to that of other algorithms when applied to strictly bifurcating trees with specified numbers of spr operations. efficient evaluation of edit paths is a new tree comparison algorithm that uses evolutionarily reasonable constraints to identify and eliminate many unproductive search avenues, reducing the time required to solve many edit path problems. we also used eeep to recover edit paths from over unrooted, incompletely resolved protein trees containing up to taxa as part of a large phylogenomic study. however, the edit paths inferred using eeep suggest an important role for genetic transfer in the evolution of microbial genomes as well. since sequence trees typically have no implied root and may contain unresolved or multifurcating nodes, the strategy implemented in eeep is the most appropriate for phylogenomic analyses. while most of the protein trees examined here were very similar to the reference supertree, requiring zero or one edit operations for reconciliation, some trees implied up to transfer events within a single orthologous set of proteins. while inferred protein trees were far more similar to a reference supertree than random trees were to each other, the phylogenetic distance spanned by random versus inferred transfer events was similar, suggesting that real transfer events occur most frequently between closely related organisms, but can span large phylogenetic distances as well. the high degree of consistency among inferred protein trees shows that vertical inheritance is the dominant pattern of evolution, at least for the set of organisms considered here. lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. an'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft operations, but finding the optimal such set of operations is np-hard for comparisons between rooted trees, and may be so for unrooted trees as well.
 lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. an'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft operations, but finding the optimal such set of operations is np-hard for comparisons between rooted trees, and may be so for unrooted trees as well.  efficient evaluation of edit paths is a new tree comparison algorithm that uses evolutionarily reasonable constraints to identify and eliminate many unproductive search avenues, reducing the time required to solve many edit path problems. the performance of eeep compares favourably to that of other algorithms when applied to strictly bifurcating trees with specified numbers of spr operations. we also used eeep to recover edit paths from over unrooted, incompletely resolved protein trees containing up to taxa as part of a large phylogenomic study. while inferred protein trees were far more similar to a reference supertree than random trees were to each other, the phylogenetic distance spanned by random versus inferred transfer events was similar, suggesting that real transfer events occur most frequently between closely related organisms, but can span large phylogenetic distances as well. while most of the protein trees examined here were very similar to the reference supertree, requiring zero or one edit operations for reconciliation, some trees implied up to transfer events within a single orthologous set of proteins.  since sequence trees typically have no implied root and may contain unresolved or multifurcating nodes, the strategy implemented in eeep is the most appropriate for phylogenomic analyses. the high degree of consistency among inferred protein trees shows that vertical inheritance is the dominant pattern of evolution, at least for the set of organisms considered here. however, the edit paths inferred using eeep suggest an important role for genetic transfer in the evolution of microbial genomes as well. 