extfieldsofstudy: Biology Medicine

text:
Looking for trees in the forest: summary tree from posterior samples

Background Bayesian phylogenetic analysis generates a set of trees which are often condensed into a single tree representing the whole set. Many methods exist for selecting a representative topology for a set of unrooted trees, few exist for assigning branch lengths to a fixed topology, and even fewer for simultaneously setting the topology and branch lengths. However, there is very little research into locating a good representative for a set of rooted time trees like the ones obtained from a BEAST analysis. Results We empirically compare new and known methods for generating a summary tree. Some new methods are motivated by mathematical constructions such as tree metrics, while the rest employ tree concepts which work well in practice. These use more of the posterior than existing methods, which discard information not directly mapped to the chosen topology. Using results from a large number of simulations we assess the quality of a summary tree, measuring (a) how well it explains the sequence data under the model and (b) how close it is to the “truth”, i.e to the tree used to generate the sequences. Conclusions Our simulations indicate that no single method is “best”. Methods producing good divergence time estimates have poor branch lengths and lower model fit, and vice versa. Using the results presented here, a user can choose the appropriate method based on the purpose of the summary tree.

Background
Bayesian Markov Chain Monte Carlo (MCMC) analysis provides powerful and popular techniques for performing phylogenetic analysis. The result of such an analysis is a set of trees drawn from the posterior distribution. The set of correlated draws is often condensed into a single tree for visualistion, comprehension, annotations and presentation. When most trees agree in topology and branch lengths, the most frequent tree topology, properly annotated, can give a fair representation of the posterior distribution.
However, a single tree can be misleading, especially when the agreement between posterior trees is small. Posterior tree topologies can be reduced to a set of common sub-topologies [1], but this is also a fragmented view of the posterior. Tree drawing programs such as FigTree [2] can annotate internal nodes with the clade posterior support (the fraction of posterior trees containing the clade), and the credible interval of internal node ages.
Still, the choice of any specific topology highlights one alternative at the expense of others. The tree drawing program DensiTree draws all posterior trees transparently [3]. Where most trees agree in topology and node height, lines are close to each other and distinct edges appear, while areas of uncertainty in topology or heights remain a blur. The composite image allows a direct assessment of posterior support and node height uncertainty by visual inspection. But even the display of the full posterior can be hard to interpret when the uncertainty gets large, and a summary tree overlaid on top can be useful in such situations.
There are many ways of obtaining a "representative" tree topology from a collection of trees. One group of methods look for consensus among the trees using splits, clusters or rooted triplets/quartets present in posterior trees [4]. The TreeAnnotator utility in BEAST [5] uses the clade frequencies as estimated by the posterior to score each tree, selecting the rooted topology of the highest scoring tree amongst the set. This results in a fully resolved topology http://www.biomedcentral.com/1471-2148/13/221 with a non zero support, in contrast to consensus methods which often produce unresolved trees. A recently published method uses conditional clade splits probabilities to compute a probability for each posterior tree [6].
However, selecting a representative topology is only the first step in generating a summary tree from the output of programs such as BEAST. BEAST trees are rooted with branches proportional to time, as is the summary tree. In the second step, TreeAnnotator assigns a divergence time for each clade using the ages of matching clades from the posterior. If the number of trees containing the clade is small, the divergence time estimate can have high variance which may result in negative branch lengths. Clades in trees from the MCMC samples which do not appear in the summary tree are essentially ignored, and sometimes a large proportion of the posterior goes unrepresented. Ignoring non-matching parts appears to be the accepted practice and is used in the SumTrees utility in DendroPy [7].
In this paper we describe several new ways for building rooted summary trees. These new constructions use more of the information contained in the posterior even when the disagreement between posterior trees is high. Some of the methods are based on rooted tree distances, and are similar in spirit to the method developed by Huggins et al. for unrooted trees [8]. We perform an extensive simulation study and compare the trees from all methods using multiple criteria. Summary trees are assessed with respect to the posterior and by their distance to the tree used in generating the sequence data. The methods are implemented in biopy [9], and integrated with DensiTree, making it easy to examine the summary tree in the context of the full posterior.

Definitions and notations
We define a rooted tree as a collection of clades with ages. Specifically, a tree is a strict hierarchy of clades, where each clade is a subset of the taxa, and a non-negative age is associated with each clade.
Formally, a tree T is a triplet (L, C, h), where L = {x 1 , x 2 , . . . , x l } is the set of taxa and C = {C 1 , C 2 , . . . , C n } is a set of clades. Each clade C i ⊆ L is a subset of taxa, and h : C → R ≥0 is a function assigning an age to the clade. The set C describes only the clades hierarchy and is referred to as the tree topology. Sometimes we shall use c ∈ T as a shorthand for T = (L, C, h)andc ∈ C ("clade c is present in tree T").
To qualify as a tree, the following conditions must hold: i The tree contains all leaves: ii The tree contains a root: L ∈ C. iii Strict hierarchy of clades: for any two clades For any clade c, the elements in the set A(c) = {y ∈ C : c ⊂ y} are called ancestors of c, and the minimal element P(c) in A is the parent of c. Every clade except the root has a parent and by association a branch to its parent with length b(c) = h(P(c)) − h(c). For convenience, the branch length of a subset not in C is defined as zero. Any subset of taxa x has a Most Recent Common Ancestor in the tree, the minimal clade containing all members of x. Formally, ca(x) is the minimal element of {y ∈ C : x ⊆ y}. For brevity we omit the tree when the context is clear, and use ca(c, T) to explicitly associate the clade with the tree T.
Extending the domain of b(·) to all taxa subsets simplifies definitions involving sets of trees with different topologies. We extend h(·) for the same reason and define the age of any subset x ⊆ L to be the age of the common ancestor of x,h(x) = h(ca(x)).
Usingh, we define the heights error, a discrepancy score between clade ages of T = (L, C, h) and a reference tree T ref , The heights error is the total sum of clade age errors, whether they appear in the reference tree or not. The age of a clade which is not in the reference tree is taken to be the age of the MRCA of the clade taxa, which spans a larger clade in the reference tree. Note that the definition is not symmetric. Alternatively we define the divergence times error which focuses on the time lineages split from each other. The divergence time for any clade x ⊆ L is the mean divergence time of all pairs of x. Formally, we start with the pairs of taxa which split at the clade; those are the pairs in x whose common ancestor is the clade, Now the average split time is the mean of all pair splits, Finally, The total error is, The clade and divergence errors are equal for trees with the same topology, but they differ when topologies disagree, and the difference usually increases with the distance in topology. http://www.biomedcentral.com/1471-2148/13/221 The clades missed error counts the number of clades in This number is equal to (half ) the Robinson-Foulds tree distance [10] when T has no zero length branches. A clade with a zero branch does not count as a match because it is potentially confused with its parent. The clades called error scores a 1 for correctly called clades and a -1 penalty for incorrectly called clades, A tree set T = {T 1 , T 2 , . . . , T k } is a set of trees on shared taxa. Typically those sets are samples from a Bayesian analysis, and we define the posterior frequency F(x) of x ⊆ L as the fraction of times x is present as a clade in the trees: The posterior frequency of a subset not in any of the trees is zero.

Distance between trees
The Rooted Branch Score (RBS) measures the distance between two rooted time trees, and is the total sum of the difference in branch lengths of matching clades. This definition is motivated by the distance between unrooted trees [11], but the space of rooted trees is more complex than its unrooted counterpart since branch lengths are not free to vary independently of each other [12]. Since by convention the branch length of a missing clade is zero, any clade present only in one tree contributes its total length to the score. Formally, for T 1 = (L, C 1 , h 1 ) and T 2 = (L, C 2 , h 2 ) we have, The Squared Branch Score (SRBS) is similar, but taking the square of the difference instead of the absolute value, The Heights Score (HS) takes the difference between clade ages instead of branches. Like the RBS, branches appearing in only one tree are added to the sum, The heights score is a (non-optimal) edit distance, where the score is the total sum of a sequence of moves which transform one tree into the other. Each move involves sliding an internal node, and two nodes may "merge" into one when they meet.
The Rooted Agreement Score (RAS) measures the disagreement between branches by treating them as intervals. Two branches may be of the same length and still contribute to the distance if they span different intervals as measured from the time of the tips. The score, when divided by the sum of the length of the two trees, is the probability that a random point chosen uniformly on one of the trees has a corresponding point on the other tree. Formally, where − → b (x) is the interval spanned by the clade branch, and is the symmetric difference operator, that is RBS and RAS are metrics in tree space, while SRBS and HS are not. RBS is a metric since branches can be mapped to the vector space R 2 n −1 [8], and a similar argument works for RAS. However, we only require that distances are semimetrics and make no use of the triangle inequality.

Summary trees BEAST Tree annotator
The Tree Annotator utility in BEAST generates a summary tree using a two stage procedure. First, each posterior tree is assigned a score based on topology. The Clade Credibility of a tree is the product of posterior frequencies (equation (7)) of all clades in the tree, The Maximal Clade Credibility (MCC) tree is the tree with the highest score, and we shall refer to its topology as the MCC topology. In the second step, each clade is assigned an age based on the clade age in posterior trees. Formally, the age is set as either the mean or the median of the set of ages Since each age is set independently, the end result is not guaranteed to be a tree (condition iii). A few "negative branches" are not an unusual occurrence in trees with a medium to large number of taxa and moderate posterior uncertainty.

Minimum distance trees
The distance between the tree set T and the tree T is defined as the mean distance of T to all members of T, where d T is one of the tree scores defined previously. A Minimum Distance Tree is a tree which minimizes d(T, T). While the definition is simple and natural, the details are not. First, the minimal tree is not necessarily unique; there might be several or even an infinite number of minimal trees in some cases. Second, with anything more than a few taxa the space of trees is vast and topologically complex, so there is no guarantee of finding the minimal tree. We therefore limit the search to the topologies present in the posterior, and designate this approach by a lowercase 'm' followed by the distance method (mRBS, mRAS, etc). However, even this can be time consuming when the posterior contains many topologies, and in addition we examine a family of methods which consider just a single topology, using one of the heuristics outlined in the next section. The details about the algorithm for searching the best branch assignment for a specific topology are in Appendix 2.

Selecting a topology
All of the two stage methods we considered selects a topology first and assign branch lengths conditional on that topology. We examined three alternatives to the MCC for selecting a topology. The first alternative uses the recently published Conditional Clade Probability Distribution (CCD). The CCD computes a probability for each tree based upon the posterior probability of the splits in the tree, conditional on the clade posterior frequency [6]. The second is a the Total Clade Branch (TCB), which assigns a score to each clade in the tree equal to the total length of matching branches in the posterior. The total length reflects the support for a clade by combining both the frequency (the number of trees with the clade) and confidence, under the assumption that longer branches are more likely to be "real" than shorter branches. The third is the Highest Posterior Frequency (HPF), which picks the topology of the tree most frequent in the posterior. To break ties, the HPF picks the tree whose height is closest to the mean root height of the posterior.

CA Tree
Negative branches in the TreeAnnotator tree result from using a different subset of posterior trees for estimating each clade age. In the Common Ancestor Tree (CAT), every clade x ∈ C is assigned an age using the mean of the clade age in all posterior trees. Formally, The generated ages always produce a tree, since x ⊂ y =⇒h(x, T i ) ≤h(y, T i ). Unlike TreeAnnotator, which may end up using a small number of values for some clades, CAT uses |T| posterior values for estimating the age of each clade.

Taxa partitions tree
We now present the Taxa Partition (TP) tree, a single stage method which does not commit to a particular topology before assigning ages. The TP is inspired by the tree operator described by Mau et al [13]. In this representation each internal node is assigned a left/right orientation, inducing a linear order on the taxa and positioning each internal node between two tips (Figures one and two in [13]). We reverse the process by first ordering the taxa, then using the posterior to assign the ages between tips and finally reconstructing the tree topology from the ages.
For a given ordering of taxa, each posterior tree provides ages according to its topology. A clade contributes an age if it spans an unbroken range in the ordering. For example, for the order [a b c d], the tree (((a,b),c),d) contributes the age of (a,b) to [a | bcd], the age of ((a,b),c) to [ab | cd] and the root height to After collecting ages for all splits from the posterior, a point estimate of the height at each split is used to build the tree. The precise definitions are given in Appendix 2.
TP incorporates clade ages from competing topologies before committing to the final topology. For example, take the set with a mixture of two topologies, ((a,b),c) and (a,(b,c)). With the obvious ordering [a b c], TP uses all ages in every tree, and the choice between the two topologies is determined by the age of the [ab | c] and [a | bc] splits. If [ab | c] is higher we end up with ((a,b),c), otherwise with (a,(b,c)).
Finding an optimal ordering is hard. Assigning an orientation which minimizes the distance between taxa orders http://www.biomedcentral.com/1471-2148/13/221 of just two trees is NP complete [14]. We use a fast heuristic which proved effective in practice: build a distance matrix for pairs of taxa and use simple clustering to build the ordering. The distance between taxa a and b in each tree is the size of the clade of their common ancestor, d(a, b) = |ca({a, b})|. The overall distance is the mean of pair distances over all posterior trees. The clustering starts with each taxon in its own group, then progressively joins the two closest groups.

Test cases
To evaluate the various methods we generated 2000 test cases, divided into 20 groups of 100 repeats. For each case, a tree with n tips was drawn from the Kingman coalescent distribution [15] with population size N e . All repeats shared the same n and N e , and each group was assigned one pair from the 5x4 grid formed by n = 8, 16,32,64,128 and N e = 1, 2, 4, 8.
A sequence of length 800bp was generated for the tips of the tree, starting with an ancestral sequence at the root and mutating the sequence along the branches using the Jukes-Cantor substitution model [16] with a mutation rate of 0.005. The sequences were analyzed using BEAST-2 [17] under the same model (Jukes-Cantor and a coalescent prior with constant population size). The tree and population size were estimated but the mutation rate was fixed at its true value. The chain was 2.2M steps, sampled every 2k steps. 200k of the initial samples were discarded (burnin), leaving 1000 posterior samples. Those were used as input for building a summary tree by each of the methods under consideration.
The test trees contain 8 to 128 tips and range (on average) from a height of 0.01 substitutions to 0.08, or 2 to 16 million years for a nuclear mammalian gene. Sampling the posterior of such trees normally requires a longer MCMC chain, but here a relatively short one is sufficient. The data was generated under a simple model and the exact same model is used for inference, resulting in excellent mixing. Not only was the effective sample size high for all parameters, we made sure the clades were adequately sampled by running a second independent chain, starting with a different seed. We then computed the maximum of the absolute difference between posterior frequency of all clades; this number was well below 5% in most settings, and around 6% for the most diffuse case (128 tips and height of 0.01 substitutions).
The posterior for trees with 32 and more taxa was completely diffuse, with a distinct topology for each sample. Even the easiest cases (n = 8 and N e = 8) contained between 1 and 45 distinct topologies, with a mean of 6. Also note that even when the posterior has a single topology, a method may do better that others by setting more accurate branch lengths. Summary trees were compared using two main criteria: accuracy in estimating ages and model fit. The first criteria was broken into 3 related error measures: accuracy in estimating the root height, accuracy in estimating clade ages (equation 1) and accuracy in estimating divergence times (equation 4). The second criteria was also divided into three: the log-likelihood of the sequence data given the tree (tree likelihood), the log-likelihood of the tree under the coalescent (coalescent likelihood), and the overall model fit, which is the sum of the tree and coalescent likelihood.

How methods are ranked
The methods were compared by aggregating the results from all test cases. Let us take the root height as an example. For each test case, an error value is computed for each method by taking the absolute difference between the summery and true tree heights. Next, the methods are ranked by error using dense ranking (the 1-2-2-3 rule). Finally, the mean rank of each method is computed by averaging its rank over all 2000 tests.
This scoring procedure was repeated (bootstrapped) 4000 times. In each repeat 2000 test cases are sampled (with replacement) from the pool of 2000 test cases, and a mean score computed for each method. Method A was deemed better than B only if A's mean ranking was greater than B's in 90% (3600) of the bootstraps. The method gets a final score of 0 (best) if no other method is better, and a score of R + 1 if there is a better method of score R.
The same process is repeated, using not the rankings of errors but the normalized error values. The normalization takes the errors of each case and transforms them to have a mean of 0 and a variance of 1. This ranks the methods by the magnitude of the error they make compared to other methods.
This may seem overly complex but making a fair comparison requires extra care. The methods and error measures are correlated in both obvious and subtle ways. Multiple criteria allows for a more nuanced comparison. Ideally, the particular mix of methods should not matter: adding a duplicate (or a very close variant) of one method should not penalize the ranking of lesser methods. Using dense ranking should minimize those effects. Strong correlations exist between the test settings (N e and n) and the magnitude of errors, so aggregating results from the 20 groups requires some care. Rankings based on comparison alone are insensitive to those correlations, and the normalization of errors makes aggregation possible without going through the complex exercise of modeling the relations between settings. Another reason for using two rankings is that method A may be slightly better than B in (say) 60% of the cases, yet its errors in the other 40% are large. The difference between the two ranks would alert us to such situations. http://www.biomedcentral.com/1471-2148/13/221 Finally, any number of test cases, 2000 included, is small when considering the size of tree space. Bootstrapping provides some confidence that the results are stable and not due to random noise. Table 1 lists the rankings of 22 methods for building summary trees. The table lists the comparison and error magnitude ranks for each of the 7 error measures: root height, clades missed and called (equations 5 and 6), ages and divergence times errors (equation 1 and 4), model fit, tree likelihood and coalescent likelihood. See Additional files 1 and 2 for the complete table and detailed per method rank graphs. Table 2 provides condensed rankings for the 22 methods together with performance statistics for each method obtained by averaging over the 2000 summary trees produced by each method.

Discussion
Clearly no method in Table 1 is "best", but several interesting trends and patterns can be identified. The agreement of ranking by comparison and magnitude is excellent, suggesting a similar distribution of errors for all methods. The table shows 22 of the 55 methods examined; most of the reduction comes from removing methods using CCD and HPF to select a topology, as MCC/TCB were significantly better for almost all combinations of methods and error criteria. This is slightly surprising, especially since we expected CCD, which assigns a proper probability to every tree topology, to fare better than heuristics such as TCB or MCC. The on-line supplement compares the four selection methods in more detail.
As expected there is a strong correlation between model fit and tree/coalescent likelihood (r = 0.89 and r = 0.98), but in addition the tree and coalescent likelihood are strongly correlated as well (r = 0.85). Basically, methods  The ranks for RH, CAE and DVE were added to make the TIMES rank indicating fit of clade heights, and MF, TLL and CLL ranks added to make MODEL rank indicating fit of topology. The POLY column shows the mean number of branches with length zero, which effectively create a polytomy in the tree. The number of zero length branches in each tree were divided by the total number of branches to turn them in percentages so that they can be averaged over all 2000 test cases. The MF% column shows the mean percentile of the summary tree log-likelihood (tree+coalescent) in the posterior samples. For example, a value of 94% means that the summary tree log-likelihood was higher than 94% of the posterior trees. The CAE% column show the mean clade age errors per clade, as a percent of tree height. The CME% column shows the mean number of missed clades, as a percentage of the number of non-trivial clades in the tree. The means are obtained by averaging the statistic over the 2000 summary trees produced by each method.
generating trees with a good model fit tend to do well on both counts. The only exception is TP(avg) with a good tree likelihood but bad coalescent likelihood. Also, low clade age errors and low divergence errors go together (r=0.79), again with TP(avg) as the exception. Slightly unexpected at first sight is the negative correlation (r = −0.88) between clades missed and clades called. Either a method plays it safe by calling only definite clades, and tends to miss a lot (CONS), or calls everything and makes more mistakes (TP). The table shows a second unexpected result: strong negative correlation between clade age errors and model fit (r = −0.94). Since model fit is highly correlated with branch lengths (r = 0.87), no method provides good clade ages and good branch lengths/model fit. Methods optimizing branches, such as RBS, generate trees with good fit but worse ages, and methods optimizing ages exhibit the opposite. This negative correlation exists between all measures of age and fit. It is quite interesting that the two variants of the TP end up at different ends: medians give better model fit while means gives lower divergence errors.
Another performance split can be observed between pairs employing the same method for setting branch lengths but using MCC and TCB for selecting the topology. The MCC variant has better model fit, while the TCB fares better with clade calls and misses.
While Table 1 makes it easy to compare pairs of methods, it is quite hard to interpret as a whole. Table 2 complements it by aggregating some performance ranking http://www.biomedcentral.com/1471-2148/13/221 and adding a few per-method statistics. The first statistic is the mean number of zero length branches in the summery tree, which effectively create polytomies. The methods in the table are divided into three groups: those who never create polytomies, those with occasional polytomies (up to 5%), and those with a high number (20% or more). The number of polytomies is strongly correlated with missed and called clades: methods which "resolve" conflict in the posterior by not committing and creating zero length branches miss more true clades but make less mistakes, and so have a high clade calls. Somewhat surprisingly there is no connection between zero length branches and model fit. We suspected that short branches were the main cause for low model fit, since they create non-coalescent like trees, however we see that RBS methods manage to have high model fit and around 24% polytomies. The other three statistics are the mean model fit percentile, clade age errors per clade as a percent of tree height, and the percent of missed clades from the total number of non-trivial clades. Those numbers can help in deciding how a difference in ranking translates to performance: for example, TP(avg) is seven ranks higher than TP(med) in clade time errors, but this amounts only to a difference of 0.13%, about 1 / 7 of the total range. On the other hand there are a seven ranks between TP(avg) and CAT in model fit, but here the difference is very largefrom 45% to 93%. Figure 1 illustrates visually how conflict in the posterior affects the summery trees generated by four methods. The posterior trees are from a preliminary analysis of the rps16 intron of Quercus, part of a niche evolution study (Xu et al., in prep). We use this example because the weak phylogenetic signal makes the differences stand out. HS sets to zero all branches with low support, effectively creating polytomies where competing topologies exist. CAT takes the chosen topology as the truth and treats the conflicting information as "noise" to eliminate. TP is somewhere in between, and RBS creates very short branches, because a long branch for a clade with low support is penalized when the tree is matched with the many posterior trees missing the clade. Clearly RBS goes somewhat astray here, but one should keep in mind that some branches produced by other methods are unreliable too. Large discrepancy between summary trees indicates a large amount of uncertainty in the posterior, and in those cases no single tree is a good representative of the full posterior.

Conclusions
Properly analysing the test cases proved to be as challenging as the research itself. The number of possible methods for constructing summary trees, coupled with the number of ways of assessing the results can be overwhelming. In addition, the domain of trees is vast and the evaluation and construction methods are not independent. For Figure 1 Four Summary Trees. Four summary trees generated from the same data set drawn over a DensiTree. A DensiTree draws all trees in a set of trees using transparancy so that in places where the trees in the tree set agrees there is dark colouring, while in places where there is a lot of variation there is light colouring. The bars in the tree from RBS shows the 95% credible intervals for all clades. http://www.biomedcentral.com/1471-2148/13/221 example, the distance between the summary and true tree seems the most natural error measure. However, we have four ways of measuring distance and four related methods, each searching for the minimal distance tree using that distance. Not unexpectedly, each distance score finds the tree produced by its counterpart to be closer to the true tree than the trees generated using other scores. Interconnections such as these show the importance of using multiple error criteria when comparing methods. The space of tree sets is complex, and each measure sheds light on different aspects of that space. Both "Clades Missing" and "Clades Called" measure topological distance via success in detecting clades, both seem reasonable and valid, yet one is the reverse of the other. Having only one of them would give a biased view. Simultaneously examining many methods -while complicating the comparison processcan reveal general performance trends.
By examining results from a large simulation study we found there is no clear "winner". Having low clade age errors and good branch lengths in a tree seems fundamentally exclusive. Methods setting clade ages from posterior ages tend to have lower age errors while methods matching the branch lengths produce trees with a better fit to the model. Therefore, it makes sense to consider the purpose of the summary tree when choosing a method. If divergence times matters most, use either HS or CAT. If only topology matters, use the consensus (CONS) or TP. In both cases the decision between the two alternatives depend on whether you are conservative and prefer unresolved clades (polytomies) in areas of conflict, or whether you wish a "the best guess" at a fully resolved tree. Use RBS to get a tree with good model fit and therefore closer to a Maximum Likelihood tree. TP(med) provides a good compromise: good model fit and low missed clades, with middle of the pack ages/divergence errors (but still better than RBS). All of these are better than the MCC as implemented in TreeAnnotator, which is middle of the pack in all measures except for doing worse on clades called and well on root height.
While the simulations show a few surprising results, we were most surprised by the performance of the "theory based" methods. We set out to replace heuristics with methods based upon firmer theoretical consideration, and strongly expected that RAS, a tree metric which takes into account both ages and branch lengths, will outperform the alternatives. Likewise, we expected the CCD to fare better than other methods for selecting a topology. However, heuristics seem to do better when measured against the main objective -recovering the true tree.
We think the different types of summaries are all valuable when the posterior trees are in conflict. Together with the full posterior as drawn by DensiTree, they provide different insights into the information contained in the posterior. We suggest that researchers generating a summary tree for annotation or publication use one of the newer methods since all of them outperform the existing consensus methods and BEAST's own TreeAnnotator.
While we focused on obtaining a single point estimate from posterior MCMC samples, we would like to emphasize that researchers should treat single point estimates as end points, and use the full posterior whenever possible, especially for secondary analyses. In addition, one should look at several methods for extracting a point estimate when dealing with the complex space of phylogenetic trees. The ages are computed by taking the median (or mean) of V k . The tree is reconstructed by picking the maximal age as the root, and recursively building the sub-trees to the left and right of the split.

B Implementation: Minimum distance tree
For a tree set T (draws from the posterior) and a target topology C our objective is to find a tree with topology C which minimizes the total distance to T under a tree distance metric D T (Equation 13). We use a generic multivariate optimizer to do part of the heavy lifting, but transforming the problem into a suitable form is far from trivial. While the details vary slightly for each distance metric, we found the following four steps essential: 1. Represent the tree as a point in R m . 2. Pre-process posterior trees to speed up the evaluation of the total distance to all posterior trees. 3. Analytically compute the derivative. 4. Find a good initial starting point. http://www.biomedcentral.com/1471-2148/13/221

Tree parametrization
The tree T = (L, C, h) is represented as a vector of real numbers z = (h r , α 2 , . . . , α m ) ∈ R m , where m = |C| − |L| is the number of internal clades in the tree. h r is the height of T, and α 2 , α 3 , . . . , α m are m − 1 values, one per internal clade, equal to the ratio of the clade age to the age of its parent. To retrieve a clade age from z, multiply the root height by the α for all the clade ancestors. That is, h r k α k , where k ranges over the clade ancestors. By traversing the tree in pre-order (clade before its descendants) all ages can be extracted from z using just m − 1 multiplications, and an additional 2(m − 1) subtractions would extract all branch lengths. Each component in z has a simple bound independent of other components; 0 ≤ h r < ∞ and 0 ≤ α i ≤ 1. This makes the tree a suitable optimization target for a method such as L-BGFS-B, a quasi newton algorithm for minimizing a multivariate function with simple bounds [18].

Pre-processing of posterior trees
The search for the minimum distance tree involves many evaluations of the target function, the mean distance d(T, T). This evaluation is sped up by transforming the expression, which is a sum on trees, into a sum over clades. The details vary somewhat, depending on the distance metric D T . Here we elaborate for the rooted branch score case (Equation 8), and the interested reader should consult the code for details of the other metrics.
For the tree T = (L, C, h) the total distance is expanded as follows, The terms in parentheses do not depend on T and can be precomputed, so the last two terms take O(|C|) operations to evaluate. The first term appears to require O(|C||T|) but we can cut this down to O(|C| log(|T|)).
The reason for this complicated looking expression is that the last two terms in parentheses can be precomputed, and the first is simply the number of branches in the posterior greater than b(x) minus the number of branches smaller than it. After we pre-sort the branches from the posterior for each clade, this number can be found by a binary search, taking at most O(log(|T|)) since there can be at most (|T|) matched branches, one for each tree in the posterior.

Analytical derivative
The search is significantly faster when a derivative can be computed analytically, since estimating a derivative requires at least m evaluations (the number of dimensions). While the details are tedious the calculations themselves are simple, since the target function is composed in a series of multiplications and additions/subtractions, so the derivative is easy to compute using the chain rule at each stage. Again the interested reader should consult the code for the exact details in each case.

Search initialization
We found that a good starting point can be vital, as under some settings the number of multiple local minima can be large. While the procedure to obtain the initial tree seems natural and obvious in hindsight, several other obvious looking approaches did not perform well at all.
The initial tree is obtained by first examining each branch independently. Each branch has its own optimal length, based on the matching branches in the posterior and the distance metric. This optimal value is computed for each branch, but since branch lengths are not independent, the next step builds a tree from those optimal http://www.biomedcentral.com/1471-2148/13/221 values. The build assigns an age to each clade, proceeding in post-order, that is assigning an age to all descendants of a clade before assigning the clade age. The age of the clade is obtained by averaging the expected age from the direct descendants, which is the sum of their own assigned age and their optimal branch length.


text:
The presence of sboA and spaS genes and antimicrobial peptides subtilosin A and subtilin among Bacillus strains of the Amazon basin

This report demonstrates the usefulness of PCR for the genes spaS and sboA as a means of identifying Bacillus strains with a potential to produce subtilin and subtilosin A. One collection strain and five Bacillus spp. isolated from aquatic environments in the Amazon basin were screened by PCR using primers for sboA and spaS designed specifically for this study. The sequences of the PCR products showed elevated homology with previously described spaS and sboA genes. Antimicrobial peptides were isolated from culture supernatants and analyzed by mass spectrometry. For all samples, the mass spectra revealed clusters with peaks at m/z 3300–3500 Da, corresponding to subtilosin A, subtilin and isoforms of these peptides. These results suggest that the antimicrobial activity of these strains may be associated with the production of subtilosin A and/or subtilin. The PCR used here was efficient in identifying novel Bacillus strains with the essential genes for producing subtilosin A and subtilin.

Many peptide antibiotics possess bactericidal, fungicidal and immunomodulatory activities and frequently occur as secondary metabolites produced by microorganisms. Among Bacillus species, some antimicrobial peptides are gene encoded and synthesized ribosomally while others are produced non-ribosomally by the multienzyme thiotemplate mechanism (Cotter et al., 2005).
Subtilosin A is the only anionic, circular antimicrobial peptide produced by wild strains of Bacillus subtilis (van Belkun et al., 2011). The production of mature subtilosin A requires the expression of eight (sboA-albABCDEFG) of the nine genes identified in subtilosin A-producing strains of B. subtilis. These clustered genes are transcribed from a promoter residing upstream of the sboA gene and their products are involved in the posttranslational modification and processing of presubtilosin, secretion and immunity. The albABCDEFG genes are believed to constitute an operon that encodes the proteins that function in presubtilosin processing and subtilosin ex-port. The sboA gene encodes presubtilosin, a 43-aminoacid peptide (Zheng et al., 2000;van Belkun et al., 2011).
Subtilin is a lanthionine-containing peptide antibiotic (lantibiotic) very similar to nisin, which is the most important member of the group of linear lantibiotics and is used as a food preservative. The biosynthesis of this bacteriocin is based on the expression of ten genes that are organized in a gene cluster spaBTCSIFEGRK. The spaS gene encodes the prepeptide of subtilin in which amino acids are enzymatically modified by the products of genes spaB and spaC. The modified precursor is transported through the cytoplasmic membrane by the ABC transporter encoded by spaT, which appears to be associated with a membrane complex containing the enzymes SpaB and SpaC (Kiesau et al., 1997;Stein et al., 2003).
The Amazon basin is a source of enormous biological diversity for microorganisms with potential value for biotechnological applications (Chies et al., 2002). Some investigations have undertaken screening for useful microorganisms Motta et al., 2004). The aim of this work was to screen for the subtilosin A and subtilin genes among Bacillus strains isolated from the intestine of Amazon basin fishes, using a simple, efficient PCR with specific primers for sboA and spaS.
Electrophoretic analyses of the PCR products revealed 734 bp and 566 bp fragments for the sboA and spaS primers, respectively (Figure 1). No PCR products were observed for B. cereus ATCC 14579 that was used as a negative control (data not shown). The PCR products were sequenced in the ACTGene Laboratory (Centro de Biotecnologia, UFRGS, Porto Alegre, RS, Brazil) using an automatic sequencer (ABI-PRISM 3100 Genetic Analyzer; Applied Biosystems). The sequence data were collected using the software Data Collection ver. 1.0.1 (Applied Biosystems) and a BLAST algorithm was used to retrieve homologous sequences from GenBank (National Center for Biotechnonology Information) with the software CLUSTAL W v.1.8 (Thompson et al., 1994).
All sequences of the 734 bp fragments showed elevated homology (minimum identity: 98%) with the gene encoding presubtilosin (sboA). Similarly, the sequences of the 566 bp fragments had high homology (minimum identity: 97%) with the gene encoding presubtilin (spaS). Differences in the sequences corresponded to silent mutations. The genes sboA and spaS are critical for production of the antimicrobial peptides subtilosin A and subtilin, respectively (Zheng et al., 2000;Stein et al., 2003).
Antimicrobial peptides were isolated as described by Kawulka et al. (2004). Samples concentrated in a vacuum centrifuge (SpeedVac SC100, Savant, USA) were dissolved in ethanol and analyzed by mass spectrometry in a MALDI-TOF mass spectrometer (MALDI-Micro MX PSD, Micromass, Manchester, UK) operated in reflection mode with a matrix of a-cyano-4-hydroxycinnamic acid. 102 Velho et al. Antimicrobial activity was determined by the disk diffusion method, essentially as described elsewhere (Motta et al., 2007). Listeria monocytogenes ATCC 7644 was used as the indicator organism. The antimicrobial peptides were isolated from the cell-free culture supernatant of Bacillus spp. All strains showed antimicrobial activity against L. monocytogenes. The mass spectra revealed major peaks at m/z 3300-3500 Da (Figure 2), corresponding to subtilosin A, subtilin and isoforms of these peptides (Heinzmann et al., 2006;Abriouel et al., 2011). Typical m/z values for subtilosin A (3399), subtilin (3319), succ-subtilin (3419) and its K + adduct (3457) were observed in the spectra. A major peak at m/z 3442 corresponding to ericin S (Bierbaum and Sahl, 2009) was also detected. Strain P7 presented a minor peak at m/z 3347, possibly associated with the recently discovered lantibiotic entianin (Fuchs et al., 2011). Strain P34 showed a more complex spectrum ( Figure 2C), with some peaks that could not be attributed to known antimicrobial peptides from Bacillus spp. These results agree with the fact that Bacillus may produce a diversity of antimicrobial peptides that vary according to the strain (Abriouel et al., 2011).
The results of this work indicate that PCR with specific primers for sboA and spaS is a valuable means of screening for Bacillus spp. and strains that produce subtilosin A and subtilin. With the exception of B. subtilis, the presence of subtilosin A had previously been reported only in a strain of B. amyloliquefaciens (Sutyak et al., 2008). Bacillus sp. P7 and P11 belong to the B. subtilis, B. amyloliquefaciens and B. velesensis cluster (Giongo et al., 2007), whereas strain P34 appears to be a novel Bacillus species (Motta et al., 2007). PCR-based methods are valuable tools for the rapid screening of class II bacteriocinproducing isolates in environmental samples (Yi et al., 2010). PCR has also been used to detect the bacteriocins nisin, pediocin and enterocin A in lactic acid bacteria isolated from traditional Thai fermented foods (Suwanjinda et al., 2007).
The continuous emergence of antibiotic resistance has led to increased interest in bacteriocins. These peptides are considered as the ultimate candidates for food preservation and some clinical applications because their range of activity is often limited and specific (Cotter et al., 2005). Like nisin, subtilosin A and subtilin have a proven track record of efficacy against L. monocytogenes (Stein et al., 2004;Burkard et al., 2007). Our results provide another option that should be investigated by the food industry.


extfieldsofstudy: Chemistry Medicine

s2fieldsofstudy: Biology Engineering

text:
Fates of Microcystis aeruginosa Cells and Associated Microcystins in Sediment and the Effect of Coagulation Process on Them

During toxic Microcystis aeruginosa blooms, large amounts of cells can enter sediment through natural settlement, and coagulation treatment used to control water blooms can enhance the accumulation of cells. However, the current understanding of the fates of these cells and associated microcystins (MCs), as well as the effect of coagulation treatment on these factors, is limited. The results of the present study show that Microcystis aeruginosa cells in sediment were steadily decomposed under experimental conditions, and that they completely disappeared within 28 days. The major MCs released from settled cells were immediately degraded in sediment, and microbial degradation may be the main mechanism involved in this process. Coagulation treatment with PAC (polyaluminium chloride) + sepiolite can efficiently remove Microcystis aeruginosa cells from the water column and prevent their re-invasion. Furthermore, coagulation treatment with PAC + sepiolite had no significant effect on the release and decomposition of MCs and, thus, will not enhance the MCs pollution. However, coagulation treatment can accelerate the nutrient cycle by enhancing the settlement of cells. More attention should be paid to the effect on nutrient cycle when coagulation treatment is used for restoration of aquatic ecosystems.

Introduction
Cyanobacterial blooms, especially Microcystis blooms, have received worldwide attention due to their increase in occurrence and severity [1,2]. Massive growth of cyanobacteria could result in decreased water quality by releasing offensive taste and odor compounds [3]. More importantly, some cyanobacteria found in blooms can produce natural toxins [4], including microcystins (MCs), which are the most frequently encountered family of hepatotoxins. The growing concern regarding the acute and chronic effects of MCs has resulted in the World Health Organization setting a guideline value of 1 μg/L for microcystin-LR (MCLR) in drinking water [5]. Cyanobacterial cells can enter sediment through natural sedimentation [6][7][8][9], and this process does not occur exclusively at the end of the bloom, but, rather, throughout the entire bloom period [10]. Part of these cells may decay and decompose immediately after sedimentation [6,11], whereas more cells can withstand the environmental changes and survive for longer periods under stable conditions of low temperature and darkness [10,12]. However, the settled cells may also disappear from the sediment by decay or being grazed by protists [6,10,13,14]. Some cells even reinvade the water column in spring and serve as inoculum for the planktonic population, during which substantial loss of cells may occur by decay or programmed cell death [6,15]. Therefore, the abundance of cells in sediment often shows a temporal pattern, with a decline from spring to early summer owing to reinvasion, followed by an increase in late autumn due to settlement of pelagic cells [6,16].
Accumulation of large amounts of cyanobacterial cells in sediment may pose environmental problems. For example, the inoculation of resuspended cells may result in new blooms [6,17,18]. If large amounts of cells in the sediment decay and break down intensively, the sudden release of intracellular organic compounds and nutrients may deteriorate the water quality. Additionally, as MCs are usually contained in healthy cells [19], large amounts of intracellular MCs may enter the sediment together with cyanobacterial cells [8,10,20] and then be released into the surrounding water after the decay of cells [21]. Previous studies demonstrated that MCs released from cells are mainly reduced through dilution, adsorption, and biodegradation [20]. The biodegradation is considered as the main pathway for MCs elimination in the natural environment [21]. However, the relationship between release rate and degradation rate is still unknown. If the release of MCs is faster than the degradation, extracellular MCs will accumulate in sediment, and, hence, harm the benthic ecosystems [22] and even the water quality. Thus, it is important to understand the process that cyanobacterial cells and associated MCs are subjected to [10].
The presence of toxic cyanobacterial population in water bodies causes a serious threat for the health of humans [23]. To remove these cyanobacteria and associated MCs, many approaches including biological, chemical, mechanical, genetic, and environmental controls have been proposed [24][25][26]. Chemical coagulation process has been proved to be effective in eliminating cyanobacterial cells and intracellular MCs from drinking water sources [25][26][27][28][29][30]. Pan et al. [31] demonstrated that coagulation treatment can also be used for the removal of cyanobacterial blooms and the subsequent restoration of submerged vegetation in a whole bay (0.1 km 2 ) experiment, suggesting that this technology might be effective in emergency treatment of cyanobacterial blooms or even the restoration of eutrophic water bodies. More recently, a combination of PAC (polyaluminium chloride) and modified clay was successfully used to restore a eutrophic lake through sinking cyanobacterial bloom and stabilizing phosphorus [32]. The treated lake has been shifted from a eutrophic/hypertrophic state to an oligo/mesotrophic state and kept this state for five years [32]. Although coagulation treatment gets rid of cyanobacterial cells from water column, it can not actually eliminate cyanobacterial cells from the water bodies. The cells are only transferred from the water column into the sediment. Hence, coagulation treatment may promote the accumulation of cyanobacterial cells in sediment, which could lead to new problems. Moreover, some coagulants may cause adverse effects on aquatic ecosystem because of their toxicity to aquatic organisms [33]. For example, if aluminum is used as coagulant in acidic conditions (pH < 6), ionic aluminum would be leached from insoluble forms and become toxic to many organisms, including microbes, plants, fish, and mammals [34]. Therefore, the potential effects of coagulation treatment on aquatic ecosystem function also deserve attention.
Previous investigations have described the dynamics of cyanobacteria and MCs in lake sediments under field conditions [6,7,10,21]. However, the details of this process have not been elucidated through experiments and the release and decomposition process of intracellular MCs after their entering the sediment is still unclear. Furthermore, although coagulation treatment can efficiently remove bloom algae and might be used for the restoration of aquatic ecosystems [31,32], its effects on the fates of settled cells and associated MCs have not been reported to date; thus, its safety is still unknown. This study was conducted to investigate the fates of sedimented Microcystis and associated intracellular MCs, as well as the effects of coagulation treatment on these compounds through laboratory simulation experiments.

Natural Settlement and Coagulation Efficiency
Microcystis aeruginosa cells settled slowly without coagulant, with only 9.8% and 43.8% of cells settling to the sediment after 0.5 h and 8 h, respectively. The addition of coagulant significantly accelerated the settlement of Microcystis aeruginosa cells. The percentage of settled cells reached 69.4%, 99.3%, and 99.9% within 0.5 h after adding Sepiolite, PAC and PAC + Sepiolite, respectively, and more than 99% of cells were removed within 8 h in all coagulation treatments.

Dynamics of Microcystis aeruginosa in Sediments
The dynamics of viable cells in both overlying water and sediment were investigated by light microscopy after staining with trypan blue. Although Microcystis aeruginosa cells from the natural settlement treatment settled more slowly than those from coagulation treatments, no viable cells were detected in overlying water for any treatments at day six ( Figure 1).
The changes in viable cells in sediments showed a similar trend in both natural settlement treatment and coagulation treatment with PAC + sepiolite ( Figure 2). Specifically, the abundance of cells increased at the beginning of incubation, with a peak value being observed at day six. Thereafter, cells diminished steadily and no viable cells were detected at day 28. Although the patterns in the PAC treatment and sepiolite treatment were significantly different from that in the natural settlement treatment (p < 0.05), cells in these treatments also changed gradually and finally disappeared within 28 days. Moreover, there were fewer viable cells in sediment during the entire experiment for PAC treatment than for other treatments ( Figure 2).  The re-invasion potential of cells in sediments was further investigated for the natural settlement treatment and coagulation treatment with PAC + sepiolite. To accomplish this, sediment samples were suspended in water and then allowed to settle for five minutes, after which the cells suspended in the water phase (hereafter referred to as resuspendable cells) were counted by light microscopy. The dynamics of resuspendable cells in the sediment samples are shown in Figure 3. In the natural settlement treatment, the resuspendable cell numbers underwent the same changes as viable cells and the concentrations of resuspendable cells were only slightly lower than those of viable cells at most time points (Figures 2 and 3). However, for the coagulation treatments (PAC + sepiolite), the concentrations of resuspendable cells were significantly lower than those of the viable cells in sediments throughout the experimental period. The resuspendable cells increased gradually at first, with the highest concentration being observed at day 12. Thereafter, the resuspendable cells decreased steadily and were completely gone at day 28. Although the same amounts of cells were added, the resuspendable cells in the coagulation treatment samples (PAC + sepiolite) were lower than those in the natural settlement samples.

Microcystin Release and Degradation
During the incubation period, no MCLR were detected in the overlying water in any treatments other than the PAC treatment, in which a low level of MCLR (0.23 mg/L) was detected at day three ( Figure 4). The dynamics of MCLR in sediment are shown in Figure 5. The curves of the MCLR concentration in various treatments showed a common trend ( Figure 5). After about 6-12 days of lag phases, MCLR concentrations decreased gradually to below the detection limit at day 24 (PAC and PAC + sepiolite) and day 28 (natural settlement and sepiolite), respectively. During this course, no intermediate degradation product that had a UV spectrum similar to that of MCs was detected in the HPLC chromatogram. In addition, similar to the viable cells, the concentrations of MCLR in sediment were different for various treatments, and the concentrations in PAC treatment samples appeared to be lower than that in other samples. Nonparametric Spearman statistical analysis with data from all sediment samples showed that the concentration of MCLR in sediments was closely related to the Microcystis aeruginosa biomass in sediment (r = 0.93, p < 0.01, n = 36).  To test whether MCs released from cells were decomposed by microbial community indigenous to the sediment, biodegradation experiments were conducted by adding soluble MCLR to sediment/aqueous system. The concentration of MCLR was effectively reduced to below the detection limits within six days, whereas no obvious reduction was observed in sterile control, indicating that losses of MCs in the experiments were not due to abiotic degradation ( Figure 6). Furthermore, no intermediate degradation product that had a UV spectrum similar to that of MCs was observed in the HPLC chromatogram.

TN in Water Phase
The concentrations of TN in the water phase were monitored throughout the experiment using a TOC/TN analyzer after filtration through a 0.22 μm filter, and the results are shown in Figure 7. The TN concentrations in all treatments increased gradually from the beginning of the experiment to around day 24. No significant difference was observed among the TN profiles of various treatments (p > 0.05) except for the PAC treatment, in which the TN concentrations were higher than in other treatments during the first 20 days.

Discussion
Coagulation treatment has a strong potential for application in the restoration of aquatic ecosystems by removing bloom algae from water column [31,32], however, whether this process affects the fates of settled cells and thus causes new environmental problems is still unknown. Our results show that coagulation treatment removed Microcystis aeruginosa cells efficiently, and the combined use of PAC and sepiolite has higher removal efficiency compared with each coagulant alone. Furthermore, only a small part of viable cells was detected to be resuspendable in the coagulation treatment with PAC + sepiolite compared with the natural settlement treatment, indicating that the combined use of PAC and sepiolite can effectively prevent the cells from reinvading the water column. It is worth noting that distilled water was used in our experiment to suspend sediment during counting resuspendable cells. This may facilitate the dissolution of aggregate due to the low ionic strength in distilled water and thus make the cells immobilized in floc easy to be released. Therefore, the actual number of resuspendable cells in PAC + sepiolite treatment may be lower than that we observed. The less resuspendable cells is important for in situ control of bloom algae because the intense wind-induced mixing or bioturbation that often occurs in eutrophic water bodies can resuspend the sediment, resulting in the recruitment of benthic algae [35][36][37]. The effective removal of bloom algae and the inhibition of cells re-invasion by coagulation process may favor the rebuilding of submerged vegetation and subsequent restoration of eutrophic water bodies.
Our results also suggest that coagulation treatment with PAC + sepiolite or sepiolite has no negative effect on Microcystis aeruginosa cells at the dose used in this study, as the cells number in sediment decreased gradually during incubation (Figure 2). In PAC treatment, however, a low level of MCs was detected in water phase during the early period of incubation (Figure 4), whereas no MCs were discovered in water phase after day three. Additionally, no massive decay of cells occurred during the whole experiments ( Figure 2). These findings indicate that the lysis of cells and release of intracellular MCs might be due to the inadequate mixing of PAC at the beginning of coagulation experiment. These results differ from that of Han et al. [38], who found that alum treatment caused serious damage to Microcystis ichthyoblabe cells and resulted in the release of intracellular MCs no matter whether sediment was present or not. Although the exact reason for this discrepancy is still unknown, it is not likely due to coagulant dose, as a higher coagulant dose was adopted in present study (50.6 mg/mL as Al) than in above-described study (48 mg/mL as Al). The numbers of viable cells increased obviously in the early period of incubation for natural settlement treatment and coagulation treatments except PAC treatment. This might be attributed to the growth of Microcystis aeruginosa cells in sediment. During incubation, the sample bottles were brought out termly to detect the color change of sediment and overlying water. The exposure to light may promote the propagation of cells in the sediment surface and, thus, lead to the increase in cell numbers during the early period of incubation. In the mid-late period, however, this effect may begin to weaken as more cells decayed, hence the cell numbers commenced to decrease. A similar pattern appeared in the resuspendable cells in natural settlement treatment and PAC + sepiolite treatment. For the natural settlement treatment, the resuspendable cells changed synchronously with the viable cells in sediment and the resuspendable/viable cells ratio kept constant on the whole, suggesting that the variations of resuspendable cell numbers were attributed to the changes of viable cell densities. For the PAC + sepiolite treatment, however, the variations in resuspendable cells were not synchronized with the changes in the viable cells. Moreover, the resuspendable/viable cells ratio increased linearly from 0.05 at the beginning to 0.46 at day 16 and then decreased to 0.21 at day 24. These results suggest that the initial increase in resuspendable cells may be due to the increasing looseness of floc with time, rather than due to the growth of cells. In the later period of incubation, the resuspendable cells may be reduced owing to the significant decrease in viable cells. However, why the resuspendable/viable cells ratio decreased after day 16 was still unclear.
After coagulation treatment, massive MCs entering the sediment with intact cells may pose potential risk of MCs pollution. Our results show that coagulation treatment did not enhance the accumulation of MCs in sediment or lead to intense release of soluble MCs into water column. During incubation, the concentrations of MCs in sediment decreased steadily in the same manner as viable cells for all treatments. In addition, no MCs were detected in overlying water with the decay of cells, except in the PAC treatment, even though the total concentration of MCs in samples was as high as 250 μg/g sediment. These results imply that coagulation treatment has no significant effect on the release or decomposition of MCs in sediment. The synchronous change and high correlation between MCs concentration and cells number suggest that most MCs detected in sediment were contained in viable cells. Similar phenomenon was also demonstrated in a field investigation by Ihe [6]. As the MCs concentration (250 μg/g) in sediment was far higher than the adsorptive capacity of the sediment [20], the decline of MCs was not likely due to the irreversible adsorption to sediment. Therefore, the MCs were likely decomposed immediately after released from cells and would not enhance MCs pollution. In the present study, however, no pre-concentration or clean-up processes were performed before analyzing the MCs in the water phase due to the limited sample volume. As a result, it is still unconfirmed whether there was low level of MCs (less than 0.05 mg/L) entering the water column during treatment, even though no MC was detected in the overlying water. Since low-level prolonged exposure to MCs can also pose a risk to the environment and human health [23], the release and persistence of low levels of MCs deserves further investigation.
Our results indicate that biodegradation may be the major detoxification process of MCs released from cells in sediment. The biodegradation of soluble MCLR in sediment ( Figure 6) argues that the MCs released from settled cells are likely degraded by MC-biodegrading bacteria indigenous to sediment. As biodegradation is a major process for natural elimination of MCs and the ability to degrade MCs is widely spread in water bodies, with abundance of MC-degrading bacteria inhabiting the sediment [21,39], bacterial biodegradation may play an important role in the fate of MCs released from settled cells under field conditions. During the degradation of MCs, no byproducts with the characteristic UV spectrum of MCs were observed upon HPLC analysis, implying that the Adda residue in the MCs had been disrupted. As the Adda residue is critical for MC toxicity, disruption of the Adda residue indicates that the toxicity of MCs might decrease remarkably. These findings suggest that MCs may be detoxified through biodegradation promptly after released from settled cells in sediment.
During the bloom period, bloom algae can also enter the sediment through natural sedimentation and sedimentation rates up to several g/m 2 /d have been reported in reservoirs [10]. The high sedimentation rates have caused massive accumulation of cells in sediment, with cell concentrations as high as 3 × 10 10 cells/L [6]. Our results show that the naturally settled cells decomposed steadily and completely disappeared at day 28, days after a lag phase of six days, and during which no massive die-off of cells was noted (Figure 2). This decomposition rate is faster than that reported by Schöne [15], who demonstrated that only 27% of Microcystis cells in natural sediments disappeared at day 21. This discrepancy may be partly attributed to the different forms of Microcystis, as the cultured cells (unicellular form) have been used in present experiment, whereas colonial strains were studied in the reference [15]. Another possible reason was the difference in incubation temperature used in their study (9-15 °C) and this study (25 °C), because low temperature may suppress the biodegradation of Microcystis cells [12]. Similar effect of temperature was also found in a field investigation by Ihle [6]. The steady decomposition of settled cells at high temperature implies that these cells may not persist for very long periods of time in sediment. This explains why no massive accumulation of cells is detected during water bloom periods although large amounts of cells settle into sediment [6,10].
With the decay of settled cells, nitrogen element was synchronously released into water phase, suggesting that organic nitrogen in cells such as protein and nucleic acid was released. These kinds of organic nitrogen may be further decomposed by microorganisms and finally mineralized to NH + -N in water bodies. To avoid disturbing the floc, the disolved oxygen in our experiments was not measured during incubation. It is likely that both oxic and anoxic microenvironments are present in the same bottle due to the decay of algae cells. Hence, we supposed that some of NH + -N might be oxidized to NO 3 − -N through nitrification during incubation. Although coagulation treatment has no significant effect on the release of TN (Figure 7), it brings massive cells into the sediment. The steady lysis of these cells and the release of nitrogen may accelerate the nutrient cycle in water bodies. Therefore, more attentions should be paid to the effect on nutrients cycle when applying coagulation treatment.
Han et al. [38] found that coagulation treatment with alume has negative effect on cyanobacteria-lysing organisms and microcystin-degrading bacteria. However, the same effect did not occur in present study, because no obvious inhibition on the lysis of algae cells and the degradation of MCs were observed. One possible reason may be the high pH (initial pH > 7 in all treatments) in our experiments. In neutral to slightly acidic conditions (pH > 6), aluminum is locked in minerals and is consequently nontoxic, whereas the Al 3+ ion may be leached with increase in pH and appear toxic to aquatic organisms [34]. Besides aluminum, MCs may also negatively affect aquatic ecosystems due to their toxicity to aquatic plants and animals [40]. Previous studies reported that toxic Microcystis aeruginosa can be grazed by some protists and mixotrophic golden algae [14,41,42], and the intracellular MCs may affect the grazer growth [41]. These results suggest that the intracellular MCs may affect the structure of aquatic communities. Giaramida et al. [43] found that exposure to MCs can drive changes in structure and physiology of bacterial communities in sediment. Whether the same effects occurred in our experiment is still unclear as the structure of aquatic communities was not detected. In the present study, no extracellular MCs accumulated massively in our experimental conditions owing to their fast degradation, therefore, the acute impact of MCs on aquatic organisms may be negligible. However, as low-level prolonged exposure to MCs may also pose a risk to organisms [23], the chronic effects of extracellular MCs on aquatic ecosystem also deserve attention.

Microcystis aeruginosa
Microcystis aeruginosa (PCC 7806) was kindly provided by the Freshwater Algae Culture Collection of the Chinese Academy of Sciences, and originally obtained from the Pasteur Culture Collection of Cyanobacteria in France. Cultures were grown in BG-11 medium (pH 7.1) and maintained at 25 °C with fluorescent lamps as a light source (1500 lx). The cultures were harvested through centrifugation (4000 rpm for 15 min) during the late exponential phase of growth. The pelleted cells were then washed three times, after which they were suspended with sterile distilled water.

Sediment Samples
Samples of surface sediment were collected from Lake Dianchi (Kunming, Yunnan, China), where heavy cyanobacterial blooms have frequently occurred during the past 20 years. Samples were collected using a stainless steel grab sampler in December 2006. The treatment and characteristics of the sediment samples have been described previously [44].

Experimental Design
The coagulation experiments were conducted in a jar test unit with six paddles. Three types of coagulants, PAC, sepiolite and PAC + sepiolite, were used in the coagulation experiments. Since the primary purpose of this experiment was to elucidate the fates of sedimented Microcystis aeruginosa and associated MCs after coagulation treatment, a high initial concentration of cells (9.2 × 10 7 cells/mL) was used to simulate the processes that may occur in practical coagulation treatment. In addition, more coagulants (PAC 250 mg/L, sepiolite 7 g/L, PAC 250 mg/L + sepiolite 2.8 g/L) than which are used in practical coagulation (clay 0.1-2.5 g/L, less than 10 mg Al/L) were employed to efficiently remove this high concentration of cells [32,45]. To analyze the coagulation efficiency, coagulant was added to 0.4 L of algae suspension at the beginning of a 1-min rapid mix cycle (200 rpm) to mix coagulant with suspension sufficiently. The cell suspensions were then mixed slowly at 50 rpm for 10 min to form macro-floc, after which the resultant floc was allowed to settle. Subsequently, 0.5 mL of water was siphoned from 1 cm below the water surface after 0.5 and 8 hours, and the cells in the samples were then counted by light microscopy.
To investigate the fate of cells in the sediment, coagulant was also added to 0.4 L of algae suspension at the beginning of a 1-min rapid mix cycle (200 rpm). Then the cell suspensions were mixed slowly at 50 rpm for about 10 min. Before the end of slow mix cycle, the cell suspensions were distributed into nine bottles (40 mL per bottle) containing 0.4 g of sediment by siphon, and during which the cell suspensions were mixed with sediment by gentle shaking. The initial pH was detected by pH meter and was between 7 and 7.6 in all treatments. The bottles were then capped with cotton plugs and incubated in darkness without shaking at 25 °C ± 0.5 °C in an incubator. In the incubation period, the sample bottles were brought out of incubator termly to detect the color changes of sediment and overlying water. One bottle was selected for sampling at days 0 (after two hours of incubation), 3, 6, 9, 12, 16, 20, 24, and 28, and the sampling procedure was shown in Figure 8. During sampling, 0.5 mL of overlying water was siphoned from 1 cm below the water surface and the residual viable algae cells were measured by light microscopy. The remaining overlying water was then siphoned and filtered (0.22 μm), after which it was analyzed for total nitrogen (TN) using a MultiN/C2100 analyzer, as well as for MCLR by high performance liquid chromatography (HPLC). The residual sediments in the bottles were then centrifuged at 4000 rpm for 10 min and the pelleted sediment was then resuspended in 10 mL of distilled water. During mixing, 0.4 mL of the mixture was sampled to enumerate the residual viable cells in the sediment by light microscopy. The remaining portions of the mixture samples were allowed to settle for 5 min, after which 0.4 mL of water was sampled to count the viable cells by light microscopy. This value was then used to calculate the resuspendable cells in the sediments. The remaining mixture was used to measure the MCLR in sediment after further centrifugation. The fate of naturally settled cells in sediment was investigated as described above, except that no coagulant was added. All experiments were conducted in triplicate.

Biodegradability of Soluble MCs in Sediment
To verify whether soluble MCs can be decomposed by indigenous microbial community in sediments, biodegradation experiments were conducted according to the method previously reported [44]. The sediment (0.4 g) and 20 mL of sterilized distilled water were added to 25 mL brown glass bottles and mixed, followed by the addition of MCLR to produce a final concentration of 5 mg/L. The bottles were then capped with cotton plugs and incubated without shaking at 25 ± 0.5 °C. To detect MCLR, 0.5 mL of well-mixed sample was collected at different time intervals. A control experiment was performed, in which sediment and water was autoclaved at 121 °C three times before adding MCLR.

Viable Cells Assay
To distinguish living cells from dead ones, vital staining was carried out using Trypan blue solution (0.4%) [46]. Samples were mixed with coloring solution in the same proportion (1:1, v/v). After 5 min of incubation, the viable cells were counted in a hemocytometer under a light microscope. As viable cells have intact cell membranes, they do not take in dye. On the contrary, nonviable cells do not have intact membrane, hence they can take up dye and appear a distinctive blue color.

MC Extraction and Analysis
Sediment samples were extracted for 15 min with 7 mL of 75% aqueous methanol under ultrasonic irradiation. The extraction was repeated three times, after which the combined supernatants were dried at 35 °C using a rotary evaporator (Laborta 4000-efficient, Heidolph, Schwabach, Germany) and then dissolved in 5 mL of 75% aqueous methanol for MCLR analysis. The MCLR concentrations in the extracted solutions and water samples were detected by HPLC as previously described [44].

Statistical Analysis
One-way repeated-measures ANOVA was performed using the statistical software package SPSS for Windows (SPSS 16.0, SPSS Inc., Chicago, IL, USA) to determine if there were significant differences between treatments. If a significant difference was detected, further comparison (Tukey's method) was conducted to identify which specific treatments differed. p values < 0.05 were considered to be statistically significant.

Conclusions
The fates of Microcystis aeruginosa cells and associated MCs in sediment as well as the effect of coagulation treatment were studied by a simulation experiment. The results demonstrated that the settled cells were steadily decomposed within 28 days for all treatments, and high concentrations of TN were released into the water column during this period. Most MCs were degraded immediately after being released from the cells and microbial degradation may have been the major mechanism for this process. Coagulation treatment with PAC + sepiolite can not only efficiently remove Microcystis aeruginosa cells from the water column, but also prevent their re-invasion. In addition, it had no significant effect on the decomposition of MCs. During coagulation treatment, however, large amounts of cells were brought into the sediment, thus, the lysis of these cells and the release of these intracellular materials can accelerate the nutrient cycle. The results presented here have important implications for the management of water supplies contaminated with MC-producing cyanobacteria.