BACKGROUND
the automatic detection of clusters of vertices in a graph is practiced in diverse fields from image recognition to social networks, and is widely used in computational biology for the study of gene families.
conceptually, a gene family is a set of genes, in one genome or several, that includes all descendants of a single gene in some ancestral organism , and excludes genes descended from other ancestral genes .
operationally, lacking the historical data to identify a gene family in these terms, it is standard practice to construct gene families on the basis of dna or protein sequence similarities.
the assumption is that genes in the same family will retain much more sequence similarity than unrelated genes, though this is more of a general tendency than a strict rule.
the genes belonging to a particular gene family may be identified with the vertices of a graph, which has edges between pairs of genes exceeding a threshold similarity score.
in the present work, we will focus on gene families within a single genome.
we set aside data on syntenic correspondences between orthologs as well as functional evidence relating genes, despite their usefulness in many contexts, in order to achieve the first of our two goals - the identification of the conceptual and methodological problems in the purely graph-theoretical approach, and the framing of a proposal to deal with them.
in plants, the creation, expansion and attrition of gene families through mechanisms of gene duplication, notably tandem duplication and, more spectacularly, whole genome doubling, allows rapid adaptation of populations to a broad range of niches.
this motivates the second of our two goals in this paper - a comprehensive survey of gene family sizes in  <dig> published angiosperm genomes.
in the first part of this paper, we review some of the desiderata of clustering methods in graphs, and define a new kind of cluster: soft cliques with backbones .
though similar in some respects to methods based on minimum spanning tree, scwib clustering controls the "chaining effect" characteristic of many such methods, by requiring that clusters satisfy a tolerant edge density criterion that takes into account cluster size.
we present an exact algorithm based on the scwib concept that can handle moderate amounts of data, and that can be converted into a heuristic for realistic genomes.
we then compare scwib results with the output of mcl  <cit> , a method which is one of the most widely used for inferring gene families.
we also see how the scwib families compare with the curated gene families of arabidopsis thaliana  <cit> .
finally we apply our algorithm to  <dig> published angiosperm genome sequences.
we compare the distribution of gene family sizes, and find similar patterns are displayed in the large majority of cases.
we find, however, that the earliest branching angiosperm, amborella trichopoda has a distinctly different pattern, with relatively few moderate- or large-size families.
RESULTS
creating gene families on the basis of similarities is essentially a kind of clustering.
well-known clustering methods like k-means  <cit> , hierarchical methods, e.g., single- link  <cit> , average-link  <cit>  and complete- link, spatial methods, e.g., pca and self-organizing maps  <cit> , and graph-based methods, e.g., minimum spanning trees  <cit>  and cliques, have all been used.
these all have advantages and disadvantages, depending on the context.
in our study of gene families, we wanted to avoid methods that produce large, inhomogeneous, families by "chaining", such as single-link, on the one hand, and methods that are overly biased towards smaller or equal-sized families, like clique or complete-link, on the other.
chaining is a major problem in constructing gene families, largely due to the multiple domain structure of many proteins.
some domains recur in many different families, with the result that both conceptually and operationally, there are no longer strict boundaries between families.
this problem has been treated in most depth by joseph and durand  <cit> .
methods that construct clusters by adding objects to that cluster with an element closest to them, without accounting for the rest of the cluster, like single-link or minimum spanning tree are particularly prone to chaining and, in some applications, like recognition of objects in satellite imagery, this may be desirable  <cit> .
however, in the context of constructing gene families, this amounts to the inclusion of non-homologous genes within the same family, something to be avoided in evolutionary analyses
gene families as soft cliques with backbones
to ensure that a gene family is determined by strong similarities connecting each of its members,
• we set a high similarity threshold u and require that a cluster be connected, in the graph theoretical sense, solely in terms of similarities exceeding u. by itself this is similar to other graph theory criteria, and like them it is susceptible to chaining, for meaningful values of u or, alternatively, to very small clusters, if u is too high.
to control for chaining
• we also set a less stringent threshold w , and require that the elements in the cluster form a clique, or almost form a clique, in terms of similarities exceeding w. we cannot require that the cluster forms a full clique, since this is too stringent for high values of w, and is not restrictive enough for low values.
a way of relaxing the clique criterion is
• to require the similarities in a cluster to form an s-plex  <cit> , where s = sn+ <dig>  the number of elements in the cluster being n , and  <dig> <s <  <dig> is a constant.
in an s-plex, every element is of degree at least n − s.
each cluster is thus validated on two levels, as a set of strongly connected elements, at level u, that is not built by chaining, due to the s-plex condition at level w.
exact algorithm
the algorithm generates all possible scwibs in a graph.
the output can then be post-processed to find a compatible subset of these to satisfy any one of several criteria.
algorithm scwib
parameters: thresholds  <dig> <w <u <  <dig> and tolerance coefficient  <dig> <s < 1
input: graph g with edge-weights w
output: the list  l of the possible scwibs in g.
steps:
define eu= {e ∈ e|u ≤ w}, ew= {e ∈ e|w ≤ w <u}
order vertices by increasing degree
while there are more vertices
select the first vertex v from the ordered list of vertices
call listgenefamily
store l <dig> results in  l.
remove v from g
algorithm listgenefamily
input: vertex v, graph g, e = eu ∪ ew
output: the list l <dig> of the all the scwibs in g that contain v
steps:
let d be the degree of vertex v
maximum size m of scwib that can contain v is m=ds+1
create a queue q, insert the subgraph with only one vertex v into q
while there are more subgraphs in q
pop out the first subgraph sg and store it into l1
if |sg| <m,
for each vertex u ∈ v  joined with an edge in eu to the last vertex of sg,
check if the subgraph g' of g is a scwib cluster,  if yes, insert g' into q.
the scwib algorithm presented here shows how the clusters can be calculated naturally, despite two independent levels of control on cluster quality.
this is an exact algorithm as it constructs all possible clusters and then picks the largest, the next disjoint largest and so on.
it requires exponential time, since the number of possible clusters can be exponential.
as displayed it is simple, but unnecessarily inefficient; the algorithm can be sped up enormously by reordering the vertices after a specified number of calls to the inner algorithm.
it can also be made more efficient by temporarily postponing the construction of clusters that threaten to require excessive time, and by a number of other devices.
for use on large genomes, it can be converted into a heuristic by replacing the exhaustive exploration of all search paths by a large enough sample of these paths.
comparison with mcl
mcl  <cit>  is one of the most widely used methods for inferring gene families.
its basic principle is the iteration of a procedure that strengthens certain heavily weighted edges and weakens those with lesser weight.
with appropriate parameter settings, mcl and scwib can produce very similar distributions of cluster sizes.
the lack of any cluster quality criterion influencing the mcl process, however, results in many of its clusters, including some of the largest ones, having very few internal edges, as in figure  <dig>  while the scwib construction explicitly prohibits this.
comparison with tair
the most comprehensive, though very incomplete, inventory of curated gene families for a plant pertains to the arabidopsis thaliana genome  <cit> .
this is a collection of gene families, found on the arabidopsis information resource  gene family page, contributed by individual scholars and groups, based largely on function within the cell as well as sequence similarities.
it is not an attempt to partition the entire set of arabidopsis genes into clusters, and there is no requirement that the families are disjoint.
furthermore, the functional groups are not intended to correspond perfectly with gene families as defined by common ancestry.
nonetheless, we compare these families with those produced by scwib.
we find that many of the gene similarities in large functionally-determined families do not meet the scwib criteria, which therefore splits them into a number of subfamilies.
the same holds for the comparison of the functional families with mcl clusters.
this implies the limitations of purely similarity-based methods for gene family detection.
nevertheless, many functional families are in almost one-to-one correspondence with gene families determined by scwib.
in figure  <dig>  only part of the nac transcription factor family is in the cluster; other parts are in other scwib clusters.
this family has been diverging in the land plants long before the emergence of the angiosperms, so that different ancient nac transcription factor subfamilies are not connected at the u = 70% level that we used.
of interest is that in an mcl analysis of this same data, with inflation factor fixed at  <dig>  to achieve the same total number of gene families as scwib, this cluster is fragmented among five mcl families, none of them containing more than nine of the  <dig> genes.
the angiosperm genomes
the emergence of new genes and new functions for existing genes is a major aspect of evolutionary divergence of species.
in animals, especially the mammals, a key mechanism for such innovation is alternative splicing, which affects at least 50% of genes  <cit> .
in plants, however, this phenomenon is thought to be much less important, impacting just 5-10%  <cit> , while the creation, expansion and attrition of gene families through mechanisms of gene duplication, notably tandem duplication and, more spectacularly, whole genome doubling, may spur rapid adaptation of populations to a broad range of niches.
we extracted all the data available on angiosperm genomes in the coge database  <cit> .
we required genomes to be published, publicly available, and have associated structural gene annotations.
the genomes included amborella, soybean, brachypodium distachyon, setaria, peach, cassava, capsella rubella, sorghum, eucalyptus, common bean, grapevine, cacao, banana, turnip, papaya, arabidopsis thaliana, tomato, potato, arabidopsis lyrata, leavenworthia alabamica, sisymbrium irio, aethionema arabicum, strawberry, thellungiella parvula, watermelon, sacred lotus, utricularia, spirodela polyrhiza, date palm, pigeonpea, sweet orange, poplar, rice, ricinus communis, clementine, lotus, flax, maize, cucumber, kiwifruit, mimulus, medicago, pepper and eutrema parvulum  <cit> .
we could not exercise any control on the quality of the sequencing, the assembly, or the annotation, and we will discuss the possible consequences of this on our results in the conclusions.
we used the synmap tool in coge to run a comparison of each genome with itself in order to construct a complete set of gene duplicates.
we disregarded syntenic context , by setting the minimum block length to  <dig>  from the unfiltered results, we eliminated duplicates with similarities less than w =  <dig> .
we decomposed the set of resulting set of duplicates into scwibs with parameters u =  <dig> , w =  <dig> , s =  <dig> .
we used a local optimization criterion, finding the largest possible scwib first, then re-applying the method on successively small graphs that result from removing the vertices in the previously generated clusters.
it should be noted that synmap, as we used it produces a large peak of duplicate genes with similarities from 60- <dig>  this had little if any consequence for our results, since almost all of these duplicates would be eliminated by the u criterion, although they could provide support for the s-plex criterion.
based on u =  <dig> , our gene families would largely have origins within the angiosperms, or be subfamilies of ancient plant gene families diversifying within the angiosperms.
as a control, we carry out an experiment on the same set of gene pairs for each genome, but using the mcl method.
exactly the same genes are involved.
to ensure that the number of gene families were comparable, we used an inflation factor of  <dig>  for the mcl.
figure  <dig> shows that distribution of mcl family sizes is more spread out than in the scwib case in figure  <dig>  however, the anomalous lack of large gene families of amborella still stands out.
this pattern emerges clearly, although the distinction is not as clear as with scwib.
another genome, cucumber, also has small numbers of moderate-sized families.
discussion and
CONCLUSIONS
the parameters of scwib directly control the connectedness and density characteristics of the clusters; we can predict the results of changes in each one.
this contrasts with program parameters like the inflation factor in mcl, whose effects are largely indirect and unpredictable at the level of individual clusters.
although scwib involves three numerical factors, they enter into the algorithm in a simultaneous way to assure both connectedness and density.
scwib clusters can also be generated by heuristics derived from generic search strategies such as branch-and-bound, and we have implemented this as a check on results from the algorithm scwib-derived heuristics.
the remarkably distinct pattern apparent in the amborella distribution of gene family sizes will have to be validated in future studies.
most immediate is the role of the specific parameter values for u, w and s. does the pattern hold up when one or more of these are shifted?
preliminary results, not shown here, are positive: increasing s from  <dig>  to  <dig>  increases the number of larger gene families  for all the genomes, but the distinction between amborella  and the other  <dig>  is amplified.
a systematic answer to this question will require considerable computing time to experiment with different values of u and w , but without any change in methodology.
another question is whether the pattern we observe is somehow dependent on the scwib definition, we have shown that the mcl method, which differs from scwib in almost every way possible, reproduces the distinct pattern of amborella with respect to the other genomes, with almost no large gene families and a small number of moderate-sized one.
another question arises because of the great heterogeneity of methods used over more than a decade of genome sequencing, particularly with regard to gene annotation.
most pertinent is the attention paid to identify gene families that are in fact families of transposons.
and indeed, the annotation of the recently sequenced amborella genome zealously pursued the identification and exclusion of such families from the set of bonafide gene families.
nevertheless, while this may have ensured a deficit of large families in the data from this genome, it could not account for the observed deficit in families with  <dig> to  <dig> genes.
is the amborella pattern phylogenetically significant?
most of the  <dig> other genomes are core eudicots, but there is a good number of poaceae and other monocots, as well as the basal eudicot nelumbo, and these all share the same pattern as the core eudicots.
sequenced genomes of other land plants, like selaginella and pinus taeda are not included in our analysis, and preliminary analyses show other, inconsistent, differences in family size distribution from the angiosperms, but no dearth of large gene families.
there is thus no evidence that amborella conserves some ancestral, pre-angiosperm pattern of gene family sizes, but this will question will require further genomic data to settle.
a similar question, whether amborella represents a pre-core eudicot pattern among angiosperms, will also require further data from other early branching plants, but already we know that nelumbo as well as the monocots, all have the typical pattern.
another factor may lie in the fact that amborella is the only genome to have escaped whole genome duplication since the origins of the angiosperms; this may also be associated with a lesser tendency to amplify and diversify gene families.
finally, the paucity of large families in amborella may be an acquired feature, and not a conserved one.
the current restricted ecological range of this plant may reflect a long history of isolation, of small populations, and little advantage to genetic innovation.
competing interests
the authors declare that they have no competing interests.
authors' contributions
all authors participated in the research, wrote the paper, read and approved the manuscript.

 the automatic detection of clusters of vertices in a graph is practiced in diverse fields from image recognition to social networks, and is widely used in computational biology for the study of gene families. conceptually, a gene family is a set of genes, in one genome or several, that includes all descendants of a single gene in some ancestral organism, and excludes genes descended from other ancestral genes. operationally, lacking the historical data to identify a gene family in these terms, it is standard practice to construct gene families on the basis of dna or protein sequence similarities. the assumption is that genes in the same family will retain much more sequence similarity than unrelated genes, though this is more of a general tendency than a strict rule. the genes belonging to a particular gene family may be identified with the vertices of a graph, which has edges between pairs of genes exceeding a threshold similarity score. in the present work, we will focus on gene families within a single genome. we set aside data on syntenic correspondences between orthologs as well as functional evidence relating genes, despite their usefulness in many contexts, in order to achieve the first of our two goals - the identification of the conceptual and methodological problems in the purely graph-theoretical approach, and the framing of a proposal to deal with them. in plants, the creation, expansion and attrition of gene families through mechanisms of gene duplication, notably tandem duplication and, more spectacularly, whole genome doubling, allows rapid adaptation of populations to a broad range of niches. this motivates the second of our two goals in this paper - a comprehensive survey of gene family sizes in published angiosperm genomes. in the first part of this paper, we review some of the desiderata of clustering methods in graphs, and define a new kind of cluster: soft cliques with backbones. though similar in some respects to methods based on minimum spanning tree, scwib clustering controls the "chaining effect" characteristic of many such methods, by requiring that clusters satisfy a tolerant edge density criterion that takes into account cluster size. we present an exact algorithm based on the scwib concept that can handle moderate amounts of data, and that can be converted into a heuristic for realistic genomes. we then compare scwib results with the output of mcl, a method which is one of the most widely used for inferring gene families. we also see how the scwib families compare with the curated gene families of arabidopsis thaliana. finally we apply our algorithm to published angiosperm genome sequences. we compare the distribution of gene family sizes, and find similar patterns are displayed in the large majority of cases. we find, however, that the earliest branching angiosperm, amborella trichopoda has a distinctly different pattern, with relatively few moderate- or large-size families.  creating gene families on the basis of similarities is essentially a kind of clustering. well-known clustering methods like k-means, hierarchical methods, e.g., single- link, average-link and complete- link, spatial methods, e.g., pca and self-organizing maps, and graph-based methods, e.g., minimum spanning trees and cliques, have all been used. these all have advantages and disadvantages, depending on the context. in our study of gene families, we wanted to avoid methods that produce large, inhomogeneous, families by "chaining", such as single-link, on the one hand, and methods that are overly biased towards smaller or equal-sized families, like clique or complete-link, on the other. chaining is a major problem in constructing gene families, largely due to the multiple domain structure of many proteins. some domains recur in many different families, with the result that both conceptually and operationally, there are no longer strict boundaries between families. this problem has been treated in most depth by joseph and durand. methods that construct clusters by adding objects to that cluster with an element closest to them, without accounting for the rest of the cluster, like single-link or minimum spanning tree are particularly prone to chaining and, in some applications, like recognition of objects in satellite imagery, this may be desirable. however, in the context of constructing gene families, this amounts to the inclusion of non-homologous genes within the same family, something to be avoided in evolutionary analyses gene families as soft cliques with backbones to ensure that a gene family is determined by strong similarities connecting each of its members, • we set a high similarity threshold u and require that a cluster be connected, in the graph theoretical sense, solely in terms of similarities exceeding u. by itself this is similar to other graph theory criteria, and like them it is susceptible to chaining, for meaningful values of u or, alternatively, to very small clusters, if u is too high. to control for chaining • we also set a less stringent threshold w, and require that the elements in the cluster form a clique, or almost form a clique, in terms of similarities exceeding w. we cannot require that the cluster forms a full clique, since this is too stringent for high values of w, and is not restrictive enough for low values. a way of relaxing the clique criterion is • to require the similarities in a cluster to form an s-plex, where s = sn+ the number of elements in the cluster being n, and <s < is a constant. in an s-plex, every element is of degree at least n − s. each cluster is thus validated on two levels, as a set of strongly connected elements, at level u, that is not built by chaining, due to the s-plex condition at level w. exact algorithm the algorithm generates all possible scwibs in a graph. the output can then be post-processed to find a compatible subset of these to satisfy any one of several criteria.     algorithm scwib     parameters: thresholds <w <u < and tolerance coefficient <s < 1     input: graph g with edge-weights w     output: the list  l of the possible scwibs in g.     steps:         define eu= {e ∈ e|u ≤ w}, ew= {e ∈ e|w ≤ w <u}         order vertices by increasing degree         while there are more vertices             select the first vertex v from the ordered list of vertices             call listgenefamily             store l results in  l.             remove v from g     algorithm listgenefamily     input: vertex v, graph g, e = eu ∪ ew     output: the list l of the all the scwibs in g that contain v     steps:         let d be the degree of vertex v         maximum size m of scwib that can contain v is m=ds+1         create a queue q, insert the subgraph with only one vertex v into q         while there are more subgraphs in q             pop out the first subgraph sg and store it into l1             if |sg| <m,                 for each vertex u ∈ v joined with an edge in eu to the last vertex of sg,                 check if the subgraph g' of g is a scwib cluster, if yes, insert g' into q. the scwib algorithm presented here shows how the clusters can be calculated naturally, despite two independent levels of control on cluster quality. this is an exact algorithm as it constructs all possible clusters and then picks the largest, the next disjoint largest and so on. it requires exponential time, since the number of possible clusters can be exponential. as displayed it is simple, but unnecessarily inefficient; the algorithm can be sped up enormously by reordering the vertices after a specified number of calls to the inner algorithm. it can also be made more efficient by temporarily postponing the construction of clusters that threaten to require excessive time, and by a number of other devices. for use on large genomes, it can be converted into a heuristic by replacing the exhaustive exploration of all search paths by a large enough sample of these paths. comparison with mcl mcl is one of the most widely used methods for inferring gene families. its basic principle is the iteration of a procedure that strengthens certain heavily weighted edges and weakens those with lesser weight. with appropriate parameter settings, mcl and scwib can produce very similar distributions of cluster sizes. the lack of any cluster quality criterion influencing the mcl process, however, results in many of its clusters, including some of the largest ones, having very few internal edges, as in figure while the scwib construction explicitly prohibits this. comparison with tair the most comprehensive, though very incomplete, inventory of curated gene families for a plant pertains to the arabidopsis thaliana genome. this is a collection of gene families, found on the arabidopsis information resource gene family page, contributed by individual scholars and groups, based largely on function within the cell as well as sequence similarities. it is not an attempt to partition the entire set of arabidopsis genes into clusters, and there is no requirement that the families are disjoint. furthermore, the functional groups are not intended to correspond perfectly with gene families as defined by common ancestry. nonetheless, we compare these families with those produced by scwib. we find that many of the gene similarities in large functionally-determined families do not meet the scwib criteria, which therefore splits them into a number of subfamilies. the same holds for the comparison of the functional families with mcl clusters. this implies the limitations of purely similarity-based methods for gene family detection. nevertheless, many functional families are in almost one-to-one correspondence with gene families determined by scwib. in figure only part of the nac transcription factor family is in the cluster; other parts are in other scwib clusters. this family has been diverging in the land plants long before the emergence of the angiosperms, so that different ancient nac transcription factor subfamilies are not connected at the u = 70% level that we used. of interest is that in an mcl analysis of this same data, with inflation factor fixed at to achieve the same total number of gene families as scwib, this cluster is fragmented among five mcl families, none of them containing more than nine of the genes. the angiosperm genomes the emergence of new genes and new functions for existing genes is a major aspect of evolutionary divergence of species. in animals, especially the mammals, a key mechanism for such innovation is alternative splicing, which affects at least 50% of genes. in plants, however, this phenomenon is thought to be much less important, impacting just 5-10%, while the creation, expansion and attrition of gene families through mechanisms of gene duplication, notably tandem duplication and, more spectacularly, whole genome doubling, may spur rapid adaptation of populations to a broad range of niches. we extracted all the data available on angiosperm genomes in the coge database. we required genomes to be published, publicly available, and have associated structural gene annotations. the genomes included amborella, soybean, brachypodium distachyon, setaria, peach, cassava, capsella rubella, sorghum, eucalyptus, common bean, grapevine, cacao, banana, turnip, papaya, arabidopsis thaliana, tomato, potato, arabidopsis lyrata, leavenworthia alabamica, sisymbrium irio, aethionema arabicum, strawberry, thellungiella parvula, watermelon, sacred lotus, utricularia, spirodela polyrhiza, date palm, pigeonpea, sweet orange, poplar, rice, ricinus communis, clementine, lotus, flax, maize, cucumber, kiwifruit, mimulus, medicago, pepper and eutrema parvulum. we could not exercise any control on the quality of the sequencing, the assembly, or the annotation, and we will discuss the possible consequences of this on our results in the conclusions. we used the synmap tool in coge to run a comparison of each genome with itself in order to construct a complete set of gene duplicates. we disregarded syntenic context, by setting the minimum block length to from the unfiltered results, we eliminated duplicates with similarities less than w =. we decomposed the set of resulting set of duplicates into scwibs with parameters u =, w =, s =. we used a local optimization criterion, finding the largest possible scwib first, then re-applying the method on successively small graphs that result from removing the vertices in the previously generated clusters. it should be noted that synmap, as we used it produces a large peak of duplicate genes with similarities from 60- this had little if any consequence for our results, since almost all of these duplicates would be eliminated by the u criterion, although they could provide support for the s-plex criterion. based on u =, our gene families would largely have origins within the angiosperms, or be subfamilies of ancient plant gene families diversifying within the angiosperms. as a control, we carry out an experiment on the same set of gene pairs for each genome, but using the mcl method. exactly the same genes are involved. to ensure that the number of gene families were comparable, we used an inflation factor of for the mcl. figure shows that distribution of mcl family sizes is more spread out than in the scwib case in figure however, the anomalous lack of large gene families of amborella still stands out. this pattern emerges clearly, although the distinction is not as clear as with scwib. another genome, cucumber, also has small numbers of moderate-sized families. discussion and  the parameters of scwib directly control the connectedness and density characteristics of the clusters; we can predict the results of changes in each one. this contrasts with program parameters like the inflation factor in mcl, whose effects are largely indirect and unpredictable at the level of individual clusters. although scwib involves three numerical factors, they enter into the algorithm in a simultaneous way to assure both connectedness and density. scwib clusters can also be generated by heuristics derived from generic search strategies such as branch-and-bound, and we have implemented this as a check on results from the algorithm scwib-derived heuristics. the remarkably distinct pattern apparent in the amborella distribution of gene family sizes will have to be validated in future studies. most immediate is the role of the specific parameter values for u, w and s. does the pattern hold up when one or more of these are shifted? preliminary results, not shown here, are positive: increasing s from to increases the number of larger gene families for all the genomes, but the distinction between amborella and the other is amplified. a systematic answer to this question will require considerable computing time to experiment with different values of u and w, but without any change in methodology. another question is whether the pattern we observe is somehow dependent on the scwib definition, we have shown that the mcl method, which differs from scwib in almost every way possible, reproduces the distinct pattern of amborella with respect to the other genomes, with almost no large gene families and a small number of moderate-sized one. another question arises because of the great heterogeneity of methods used over more than a decade of genome sequencing, particularly with regard to gene annotation. most pertinent is the attention paid to identify gene families that are in fact families of transposons. and indeed, the annotation of the recently sequenced amborella genome zealously pursued the identification and exclusion of such families from the set of bonafide gene families. nevertheless, while this may have ensured a deficit of large families in the data from this genome, it could not account for the observed deficit in families with to genes. is the amborella pattern phylogenetically significant? most of the other genomes are core eudicots, but there is a good number of poaceae and other monocots, as well as the basal eudicot nelumbo, and these all share the same pattern as the core eudicots. sequenced genomes of other land plants, like selaginella and pinus taeda are not included in our analysis, and preliminary analyses show other, inconsistent, differences in family size distribution from the angiosperms, but no dearth of large gene families. there is thus no evidence that amborella conserves some ancestral, pre-angiosperm pattern of gene family sizes, but this will question will require further genomic data to settle. a similar question, whether amborella represents a pre-core eudicot pattern among angiosperms, will also require further data from other early branching plants, but already we know that nelumbo as well as the monocots, all have the typical pattern. another factor may lie in the fact that amborella is the only genome to have escaped whole genome duplication since the origins of the angiosperms; this may also be associated with a lesser tendency to amplify and diversify gene families. finally, the paucity of large families in amborella may be an acquired feature, and not a conserved one. the current restricted ecological range of this plant may reflect a long history of isolation, of small populations, and little advantage to genetic innovation. competing interests the authors declare that they have no competing interests. authors' contributions all authors participated in the research, wrote the paper, read and approved the manuscript. 
chaining is a major problem in constructing gene families. we compare examples of output from scwib and the markov cluster algorithm, and also compare some curated arabidopsis thaliana gene families with the results of automatic clustering. we apply our method to published angiosperm genomes with annotation, and discover that amborella trichopoda is distinct from all the others in having substantially and systematically smaller proportions of moderate- and large-size gene families. gene familiesclusterings-plexangiospermsamborella trichopeda19- october twelfth annual research in computational molecular biology satellite workshop on comparative genomics cold spring harbor, ny, usa this differs from other definitions in how it controls the "chaining effect", by ensuring clusters satisfy a tolerant edge density criterion that takes into account cluster size. we define a new kind of cluster on graphs with strong and weak edges: soft cliques with backbones.
 chaining is a major problem in constructing gene families.  we define a new kind of cluster on graphs with strong and weak edges: soft cliques with backbones. this differs from other definitions in how it controls the "chaining effect", by ensuring clusters satisfy a tolerant edge density criterion that takes into account cluster size. we implement algorithms for decomposing a graph of similarities into scwibs. we compare examples of output from scwib and the markov cluster algorithm, and also compare some curated arabidopsis thaliana gene families with the results of automatic clustering. we apply our method to published angiosperm genomes with annotation, and discover that amborella trichopoda is distinct from all the others in having substantially and systematically smaller proportions of moderate- and large-size gene families.  we offer several possible evolutionary explanations for this result. gene familiesclusterings-plexangiospermsamborella trichopeda19- october twelfth annual research in computational molecular biology satellite workshop on comparative genomics cold spring harbor, ny, usa 