BACKGROUND
the advent of powerful genotyping methods, either by global sequencing or by high-throughput analysis of variation at specific loci  loci  <cit> ; snps  <cit> ), provides masses of genetic data that need to be compared and clustered.
most widely used comparison methods are phylogenetic methods i.e.
hierarchical clustering, building tree-like structures to display the diversity.
these methods consider that each individual forms a cluster and repeatedly merge the most similar clusters based on pairwise distances , or try to infer the tree that most fits the data  using an appropriate evolutionary model of the compared characters.
this provides a continuous pattern of how divergent organisms are.
other comparison methods consist in finding relevant clusters, a process referred to as partitioning.
a method made popular by the software structure  <cit> , and referred to as model-based clustering, consists in using bayesian methods to assign individuals in a pre-determined number of populations.
the assumption underlying this software is that the population conforms hardy-weinberg hypotheses i.e.
refers to organisms reproducing sexually, with random pairing inside the population.
this assumption is theoretically very problematic for clonal organisms, although practice has shown that it can provide meaningful results  <cit> , partly because some parameters can be set to mimic poor mixture inside populations.
other methods have been developed outside biology, for instance to categorize images  <cit> .
they use similarity to group data in spherical clusters well represented by their centroid , and have already been tentatively used to classify human genetic data  <cit> .
this method awaits further experimental validation on large datasets.
clustering methods can be applied to different types of loci, ranging from repetitive sequences such as insertion sequences, micro-, mini-satellites or the crispr loci to single nucleotide polymorphisms , provided an appropriate method is available to calculate the distance between individuals.
such methods usually rely on a model of the mutation process.
which loci should be targeted depends on the mean divergence time between individuals, as repetitive sequences mutate faster than snp loci.
several mutation models have been developed for dna sequence with point mutations  <cit> .
for repetitive sequences , categorical distance or the stepwise mutation model  are mostly used.
crispr loci  form a new family of repetitive sequences  <cit> .
they consist in the repetition of  <dig> to  <dig> bp sequences called direct repeats  separated by unique sequences called spacers .
the constitutive unit is therefore the combination of one dr and one spacer, and presently described crispr loci have from  <dig> to  <dig> units  <cit> .
these repetitions are surrounded by protein-encoding sequences called cas genes .
the whole locus confers resistance to bacteriophages and plasmids in streptococcus thermophilus  <cit>  and in escherichia coli when overexpressed  <cit> .
resistance to the corresponding organisms is under investigation in species where spacers are homologous to foreign dna  <cit> .
they exhibit a quite high mutation rate so that they have proven useful for epidemiological studies.
describing the presence or absence of  <dig> spacers of m. tuberculosis crispr locus has become a routine technique in any tuberculosis reference center and is referred to as spoligotyping for spacer oligonucleotide typing  <cit> .
pairwise comparisons of binary profiles can provide a distance matrix that has been used to infer phylogenetic relationships.
the most common approach to infer relationships using spoligotype patterns uses the jaccard index  as distance  <cit> , counting the proportion of spacers that are present in both profiles.
the distance matrix, either made of pure spoligotyping data or combining them with minisatellite data, is usually processed using upgma or nj algorithm to build a dendrogram or a phylogenetic tree  <cit> .
a more elaborate approach using the zipf distribution and the evolutionary dynamics of crispr loci has proven more relevant to infer phylogenetic relationships for the m. tuberculosis complex  <cit>  but is not implemented in a user-friendly software yet and does not propose assignations for all currently described spoligotype patterns.
the worldwide database of spoligotyping in m. tuberculosis complex is called spoldb , and has helped identifying recurrent signatures in crispr profiles  <cit> .
these signatures, mainly based on the absence of adjacent spacers, led to the naming of large clonal families, the monophyly of which has been confirmed through other markers such as minisatellites , region of deletions  and snps  <cit> .
main acknowledged families are eai for east-african-indian , m. africanum  <dig> and  <dig> , animal strains , cas for "central-asia" , beijing, x, haarlem, lam for "latino-american and mediterranean", t and manu   <cit> .
monophyly of each of the lam, t and haarlem families has been partly invalidated.
however, the larger lineage to which they belong and that is characterized by the 33- <dig> spacers deletion at the crispr profile  has been confirmed and designated as the "euro-american" lineage  <cit> .
it corresponds to the principal genetic groups   <dig> and  <dig> as defined by sreevatsan et al.
<cit> .
altogether deletions in spoligotype patterns have proven to contain phylogenetic information and allow most strains be assigned to the families described above.
assignations performed by experts are reported in spoldb <dig> database, patterns carrying no or contradictory signatures been labeled as "u" for "unknown or unclassified".
to circumvent the dependence on experts' analysis, the bennett's laboratory proposed automatized classification of spoligotype patterns using bayesian algorithms and a distance method taking into account the deletion process by which spoligotype patterns evolve.
they provide an on-line tool called spotclust  <cit>  to assign each spoligotype to a family, either one described in spoldb <dig>  <cit>  or one of the  <dig> large families proposed by gagneux and coworkers  <cit> .
here we wanted to take advantage of a recently developed algorithm, affinity propagation, to confirm and extend these methods.
this algorithm identifies references for every data point so that data are grouped and centered on these references while a specific cost function is minimized.
the cost of adding a new reference point, assigned by the user, determines the final number of clusters.
prior to the use of this algorithm, we tested different distances to calculate pairwise distances between spoligotype patterns.
we took advantage of previously identified references and expert assignation to rank these distances, some of which are derived from previously proposed evolutionary models  <cit> .
the distance that best identified the appropriate reference for each spoligotype pattern was implemented in the affinity propagation algorithm to identify relevant subfamilies among m. tuberculosis complex .
these families partly correlated with previously identified subfamilies.
altogether, this approach allowed us to assess the robustness of previously identified sublineages among mtc, to identify new relevant sublineages and to provide re-assignations of the spoligotype patterns described in spoldb <dig>  these re-assignations interestingly matched those of studies using vntr and/or snp data.
RESULTS
comparison of classifications based on new distances or on jaccard index to expert classification of spoldb4
clustering of crispr patterns  of m. tuberculosis complex is commonly done using the jaccard index as distance  <cit> .
this index counts the shared spacers without taking into account their spatial organization.
however, it has been shown that adjacent spacers have a higher probability to be simultaneously deleted  <cit> , and this feature has been used by experts to define m. tuberculosis complex families and subfamilies  <cit>  in the international database spoldb  <cit> .
we wanted here to identify a distance conducing to the best concordance of spoligotype assignations at the family level, as available in spoldb <dig> database  <cit> .
we retained the ten widely acknowledged families: m. africanum, animal strains , beijing , cas, eai, haarlem , lam, manu, t and x  <cit> .
each is characterized by a different spoligotype signature and thus a different reference profile  <cit>  .
in addition to jaccard index, we set up three methods to compute the distance between pairs of patterns: "domain walls" measuring the proportion of shared limits of blocks of spacers in the crispr locus, "blocks" measuring the proportion of shared blocks of spacers, and "deletions" measuring the proportion of shared blocks of deleted spacers .
we implemented these four methods to compute the distances of each spoligotype of spoldb <dig> database  <cit>  to the reference profiles of the ten families .
for each method, depending on the reference to which it was most similar, each spoligotype was assigned to one of the ten families.
spoligotype patterns for which two references were equally similar were coined as unassignable.
these assignations were compared to the spoldb <dig> classification.
the jaccard method rarely associated the spoligotype patterns to their reference .
the methods that best fitted the expert classification were the "deletions" , and the "domain walls" method .
these methods also provided the smallest amount of assignations that differed from those of the experts .
these methods thus appear to be the best for fitting the expert classification out of the four methods we tested.
beij = beijing also referred to as east asia; cas = central asia also referred to as east africa and india; lam = latino-american and mediterranean; h = haarlem; eai = east african indian.
"deletions" method succeeds in correcting false spoldb <dig> assignations
some families' assignations provided by spoldb <dig> have been debated.
for instance, patterns classified as lam7-tur  <cit>  have been found not to be related to the lam family as strains carrying that pattern do not share the ligb <dig> mutation that defines the lam family  <cit> .
such strains were instead related to t-strains  <cit>  and were renamed tur.
all methods tested here except the "deletions" method still assigned them to lam family, including spotclust.
the "deletions" method assigned them all  to the t family as did methods using vntrs  <cit>  or snps  <cit>  .
similarly, all spoligotypes assigned to the h <dig> subfamily  in spoldb <dig> were recently excluded from the haarlem family based on them not carrying the mgtc <dig> mutation  <cit> .
they were renamed "ural" and appropriately assigned to the t family by the "deletions" method only .
hence, part of the assignations suspected to be wrong with the "deletions" method as compared to expert classification may in fact correct previous classification errors.
the "deletions" method thus recognizes phylogenetic lineages better than "domain walls" method and likely at least as well as the expert eye and spotclust.
this is further supported by the clear gap between the similarity of correctly assigned spoligotype patterns to their reference  and the highest similarity to any reference of patterns assigned differently than by the expert  specifically with the "deletions" method.
"recent literature assignation" represents the standard, and refers to studies using loci other than the crispr locus: t-tur classification has been suggested both by millet et al.
<cit>  and abadia et al.
<cit>  based respectively on vntr signature and snps signatures.
t-ural classification has been suggested by kovalev et al.
<cit>  as they clustered with h37rv strains and abadia et al.
<cit> .
rim: randomly initialized model.
n ... families as defined by spotclust are described on their web-site based on what spoldb <dig> families/sub-families are mostly represented: n <dig> family is described as lam3-rich; n <dig> as h1-rich; n <dig> as lam-rich; n <dig> as lam+eai-rich; n <dig> as h3+s-rich; n <dig> as t3-africanum-rich; n <dig> as x1-h37rv-rich.
the assignations matching the standard are shown in bold characters.
assignations failures are shown in italic.
note that the "deletions" method provides the highest number of exact assignations and the least assignation failures.
interestingly, beijing, x and eai families exhibited no incongruence between the "deletions" and the expert method , suggesting that these families are clearly and appropriately defined.
as reported above , the jaccard method failed to assign most spoligotype patterns to any family; for instance, no spoligotype patterns could be assigned to beij, eai or x families  with a maximum similarity to any reference not reaching 20% for beij family .
"domain walls" and "blocks" methods provided either poor resolution between correctly and wrongly assigned spoligotype patterns , or a lower number of families with no discrepancy with the expert classification .
assignations of u spoligotype patterns
assignations thus seem phylogenetically relevant using the "deletions" method and the references of the well-acknowledged families.
we thus propose an alternative spoligotype patterns classification on the  <dig> spoligotypes reported in spoldb <dig> .
assignation rate of "u"  patterns was relatively low with this method as compared to others  but may be more reliable as exemplified by three u patterns recently assigned  <cit> : "deletions" method could only assign one of them but without error whereas two of the three assignations provided by the "domain walls" method and spotclust algorithm were erroneous .
automatized identification of references by affinity propagation clustering
the "deletions" method is highly useful to classify spoligotype patterns in the described families, but this classification highly depends on the identification of references.
these references are widely acknowledged for major families but the relevance of finer classification is recurrently debated  <cit> .
affinity propagation is an algorithm that identifies a representative  for each data point in an iterative manner until the chosen configuration of exemplars minimizes a suitable cost function that depends on the choice of the clusters .
a parameter set by the user  determines an additional cost for every exemplar found.
when p is low , large clusters are built where some data points have relatively low similarity with their representative.
as p increases, the clusters reach smaller sizes so that they become
numerous, and the mean similarity with the representative increases.
interestingly, when the number of clusters does not vary even if the penalty changes, this indicates that the data points are not evenly distributed, i.e., form meaningful clusters.
when applying this method to the spoldb <dig> dataset, relevant numbers of clusters were found to be  <dig> and  <dig> .
the mean similarity with the representative was higher using affinity propagation as compared to k-means or with bionumerics applying hierarchical clustering .
the clustering in  <dig> clusters reproduced most of the  <dig> references identified by the experts .
however, h family was divided in h <dig> and h <dig>  none of them including the h <dig>  h <dig> was grouped with t spoligotype patterns as suggested by previous studies that renamed it ural  <cit> .
we propose some renamings according to major families represented in each cluster .
when performing clustering with  <dig> clusters, many of the spoldb <dig> subfamilies were identified.
some of them were however merged such as africanum2-africanum <dig>  bovis1- <dig>  pinnipedii-microtii, lam2-lam1-lam <dig>  x <dig> and  <dig> in x, etc.
.
among eai, four meaningful subfamilies were identified whereas only  <dig> were among lam.
this suggests that the lam family was oversplitted in the expert classification.
in contrast, seven subfamilies were found among the t family.
two of them exhibited complex signatures with few spoligotype patterns actually matching the whole signature .
subfamilies t <dig>  t <dig> and t <dig> were confirmed by this method.
one family still had sit <dig>  as a reference indicating that many spoligotypes  still cannot be further classified according to their spoligotype pattern.
last, one family was created from u spoligotypes and has sit  <dig> as a reference.
most patterns carried the deletion of spacers  <dig> to  <dig> that could constitute a new significant signature.
countries in which the corresponding sits were most abundant surround the indian ocean: madagascar, thailand, india and vietnam .
we thus named it sea <dig>  .
the significance of this signature compared to the classical eai signature, which differs only by the presence of spacer  <dig>  remains to be established.
beij = beijing ; afri=m.
africanum; cas = central asia ; lam = latino-american and mediterranean; h = haarlem; eai = east african indian.
confirmed families are shown in bold.
beij = beijing ; afri=m.
africanum; cas = central asia ; lam = latino-american and mediterranean; h = haarlem; eai = east african indian.
confirmed subfamilies are shown in bold.
note that most of the patterns carry the 29- <dig> spacers deletion, and that most of them are unclassified by spoldb <dig>  "main country" refers to the country where the highest number of isolates carrying this pattern were found according to spoldb <dig>  <cit> .
* indicates the spoligotype proposed as a reference by the affinity propagation algorithm.
the countries are identified via the iso3166- <dig> alpha- <dig> code.
tha = thailand; gbr = united kingdom; gnb = guinea-bissau; bra = brazil; est = estonia; mys = malaysia; bgd = bangladesh; geo = georgia; mdg = madagascar; nld = netherlands; vnm = vietnam; usa = united states.
discussion
here we first validated a simple distance method that can be used to classify crispr genetic profiles based on a worldwide m. tuberculosis spoligotype database.
second, using a recent clustering algorithm exploiting a different approach with respect to those commonly used in the biological sciences community, we could identify an alternative m. tuberculosis classification.
the comparison between the largely validated expert classification described in the international database spoldb <dig> and our alternative classification validates our approach for m. tuberculosis crispr profiles, opening the way for its use for other bacterial species where crispr were shown to provide interesting typing information  <cit> .
clustering power of crispr patterns
m. tuberculosis complex  has been infecting humans for at least  <dig> years  <cit>  and could be  <dig>  years old or even much older  <cit> .
despite its restricted genetic diversity even between human and animal strains  <cit> , phylogenetical relationships have been detected using polymorphic dna sequences  <cit> .
crispr loci characterized using the "spoligotyping" technique have been used to define families through the use of so-called signatures i.e.
the absence and presence of characterized units of cripsr loci, the spacers  <cit> .
most of these families found independent support such as host range or congruence with independent genetic markers  <cit> , even snps and regions of deletion  <cit> .
however, some of them were "ill-defined" i.e.
had a signature that was shared by several other groups, and others were defeated by independent loci: h <dig> subfamily was renamed ural as it was related to t strains and not h strains  <cit> , lam <dig> and lam <dig> were renamed tur and cameroon respectively as they are unrelated to lam strains  <cit> .
as a consequence, the use of crispr patterns to infer phylogenetical relationship was recurrently discussed  <cit> .
we used here an automatized approach for clustering crispr patterns.
our clusters largely reproduced the well-acknowledged mtc families and provided meaningful clustering for ural, tur and cameroon.
in fact, the misclassification of ural among haarlem family was due to the merging of all signatures having spacer  <dig> deleted and spacer  <dig> present disregarding the left border of the deletion.
this classification criterion is not relevant knowing the evolutionary dynamics of crispr loci due either to the insertion of is <dig> elements or to the deletion of one of several adjacent spacers.
this kind of errors is avoided if comparison is performed using an algorithm identifying complete signatures  as included in our automatized approach .
still, the fact that some families are "ill-defined" is an intrinsic problem of spoligotyping: crispr loci in m. tuberculosis are relatively short and they evolve at a rate that cannot exclude the absence or the insufficient number of mutation in some lineages.
this intrinsically limits the power of our study, i.e.
we cannot classify all strains, and not all of them with the same precision.
however, this problem does not affect the assignation quality of the strains we classify which are in fact numerous .
we thus argue that crispr profiles evolving by the insertion of transposable elements or by deletion such as those of m. tuberculosis contain relevant information for clustering and even inference of some phylogenetic links.
the targeted locus must however not be missing for the individuals to be classified.
to avoid this pitfall, the use of crispr loci should restrict to recently diverged groups as is the m. tuberculosis species complex .
such organisms uncover diverse human pathogens such as yersinia pestis, salmonella enterica, bacilllus anthracis, mycobacterium leprae and mycobacterium ulcerans.
still, the use of crispr profiles in phylogenetic reconstructions would benefit from further developments and validations for species with still active crispr loci.
distance methods for crispr profiles
if crispr can be used to infer phylogenetic relationship, the evolutionary model or distance method used during the inference is also of great importance.
several developments had been proposed until now.
we want to discuss here what our approach adds to previous ones.
crispr profiles  form a sequence of binary data.
as such, it has been analyzed with tools developed for binary information such as the jaccard index that focuses on the sharing of every unit in the profile  taken independently.
this however ignores an essential feature of the corresponding crispr locus: that it evolves by the loss of spacers.
these losses can occur either because of the insertion of a transposable element that disrupts the sequence used in the spoligotyping technique, or by deletion.
deletions can occur for several spacers at once, even if the frequency of large deletions may be lower  <cit> .
as a consequence, the distance between two patterns, one carrying many spacers and the other carrying one large deletion, should not be considered as proportional to the number of spacers that were lost , but as corresponding to a single mutation event.
the methods proposed by the bennett laboratory  <cit>  take into account the deletion process and add a probability function that best mimics the frequency of deletion size.
in spotclust, a bayesian algorithm incorporating the inference of ancestral spoligotype patterns based on spoldb <dig> database is used to assign spoligotypes to spoldb <dig> subfamilies or to families built using a randomly initialized model   <cit> .
we showed here that, by simply using expert-defined references of main families and the "deletions" distance method that is based on deletion signatures, we could better assign unknown spoligotype patterns than spotclust as well as correct previous erroneous assignations in spoldb <dig> classification such as those to lam <dig>  <cit> .
for spotclust algorithm, this was true for both the spoldb3-based classification and the randomly initialized model.
the reason for that could be either that the size of the database used by spotclust was too small to capture evolutionary steps relevant to mtc evolution, or that bayesian statistical inferences are too dependent on priors.
performance of the affinity propagation algorithm on crispr profiles clustering
affinity propagation is a message-passing algorithm that considers clustering as a problem of minimizing an "energy" function of the clusters configuration in the data set .
this approach seems particularly promising and could help solving species delineations in asexual lineages where obligate gene exchange cannot be used as a delineation criterion  <cit> .
one of the main features of the algorithm is the possibility of regulating the total number of clusters as a function of an input parameter of the algorithm .
also the high speed  and thus the possibility to analyze very large networks is encouraging the use of this algorithm.
with this method we identified both families and subfamilies in mtc.
a single family out of  <dig> made no sense .
this is likely due to a lack of information in beijing spoligotype pattern as the large 1- <dig> deletion limits the recognition of other signatures.
when considering patterns carrying a larger number of spacers, the classification was largely congruent with the literature.
in addition, we could identify new signatures, especially one, termed sea <dig>  among previously unclassified patterns.
we therefore believe that this algorithm is very useful for classifying the widely used 43-spoligotype patterns in m. tuberculosis but could prove even more useful on patterns larger than  <dig> spacers, e.g.
the improved  <dig> spacers format.
"euro-american" lineage evolution
despite large sequencing efforts  <cit> , there has been a standing difficulty in unraveling the relationships inside "euro-american" lineage strains , especially in the so-called "t family" described in spoldb <dig>  <cit> .
here, using spoldb <dig> database, we could challenge expert-defined families and subfamilies.
we first confirmed the validity of s and t <dig> subfamilies that we suggest to consider as families.
the s family was first described in sicily  <cit>  and independently identified in québec where a sublineage was shown to harbor a peculiar pnca snp  <cit> .
the t <dig> family, defined by the absence of spacer  <dig> was originally described as m. africanum  <dig>  however was shown later to be a bona fide m. tuberculosis subfamily  <cit> .
we also confirmed the reliability of haarlem family subclustering, if renaming h <dig> as ural, and suggest considering h1- <dig> and h <dig> as two families.
we confirmed the validity of t <dig> and t <dig> families as well as t4-ceu .
some lam subfamilies renamings based on vntr and snp loci  <cit>  are given further support , while other were merged .
the tendency to merge many expert-defined families was not pervasive.
indeed in the eai family, four subfamilies out of the  <dig> expert-defined ones were confirmed.
combining the families and subfamilies identification, we could provide a simplified evolutionary scheme for this lineage .
we hope in the future, by applying affinity propagation on  <dig> spoligotype patterns, to identify other euro-american subclusters.
CONCLUSIONS
this study describes 1) a novel distance method to be applied on genetic loci evolving by deletion, as for instance do inactive crispr loci, 2) a framework to take advantage of identified references for classifying individuals using such loci, 3) a way to identify new references using the affinity propagation algorithm  <cit> , and 4) assignations and assignation tools for m. tuberculosis complex.
the distance method and the framework to identify known references were largely validated by worldwide m. tuberculosis database at the crispr locus .
this work encourages the use of crispr patterns to cluster strains in other organisms carrying such loci and for which wide genotyping has been undertaken as it is now the case for human pathogens such as yersinia pestis, salmonella enterica, bacilllus anthracis, mycobacterium leprae and m. ulcerans.
affinity propagation could also be useful to cluster other genotyping data such as snps or minisatellites.
databases larger than those available by now are however required to test the validity of this method on such markers.

 the advent of powerful genotyping methods, either by global sequencing or by high-throughput analysis of variation at specific loci loci; snps ), provides masses of genetic data that need to be compared and clustered. most widely used comparison methods are phylogenetic methods i.e. hierarchical clustering, building tree-like structures to display the diversity. these methods consider that each individual forms a cluster and repeatedly merge the most similar clusters based on pairwise distances, or try to infer the tree that most fits the data using an appropriate evolutionary model of the compared characters. this provides a continuous pattern of how divergent organisms are. other comparison methods consist in finding relevant clusters, a process referred to as partitioning. a method made popular by the software structure, and referred to as model-based clustering, consists in using bayesian methods to assign individuals in a pre-determined number of populations. the assumption underlying this software is that the population conforms hardy-weinberg hypotheses i.e. refers to organisms reproducing sexually, with random pairing inside the population. this assumption is theoretically very problematic for clonal organisms, although practice has shown that it can provide meaningful results, partly because some parameters can be set to mimic poor mixture inside populations. other methods have been developed outside biology, for instance to categorize images. they use similarity to group data in spherical clusters well represented by their centroid, and have already been tentatively used to classify human genetic data. this method awaits further experimental validation on large datasets. clustering methods can be applied to different types of loci, ranging from repetitive sequences such as insertion sequences, micro-, mini-satellites or the crispr loci to single nucleotide polymorphisms, provided an appropriate method is available to calculate the distance between individuals. such methods usually rely on a model of the mutation process. which loci should be targeted depends on the mean divergence time between individuals, as repetitive sequences mutate faster than snp loci. several mutation models have been developed for dna sequence with point mutations. for repetitive sequences, categorical distance or the stepwise mutation model are mostly used. crispr loci form a new family of repetitive sequences. they consist in the repetition of to bp sequences called direct repeats separated by unique sequences called spacers. the constitutive unit is therefore the combination of one dr and one spacer, and presently described crispr loci have from to units. these repetitions are surrounded by protein-encoding sequences called cas genes. the whole locus confers resistance to bacteriophages and plasmids in streptococcus thermophilus and in escherichia coli when overexpressed. resistance to the corresponding organisms is under investigation in species where spacers are homologous to foreign dna. they exhibit a quite high mutation rate so that they have proven useful for epidemiological studies. describing the presence or absence of spacers of m. tuberculosis crispr locus has become a routine technique in any tuberculosis reference center and is referred to as spoligotyping for spacer oligonucleotide typing. pairwise comparisons of binary profiles can provide a distance matrix that has been used to infer phylogenetic relationships. the most common approach to infer relationships using spoligotype patterns uses the jaccard index as distance, counting the proportion of spacers that are present in both profiles. the distance matrix, either made of pure spoligotyping data or combining them with minisatellite data, is usually processed using upgma or nj algorithm to build a dendrogram or a phylogenetic tree. a more elaborate approach using the zipf distribution and the evolutionary dynamics of crispr loci has proven more relevant to infer phylogenetic relationships for the m. tuberculosis complex but is not implemented in a user-friendly software yet and does not propose assignations for all currently described spoligotype patterns. the worldwide database of spoligotyping in m. tuberculosis complex is called spoldb, and has helped identifying recurrent signatures in crispr profiles. these signatures, mainly based on the absence of adjacent spacers, led to the naming of large clonal families, the monophyly of which has been confirmed through other markers such as minisatellites, region of deletions and snps. main acknowledged families are eai for east-african-indian, m. africanum and, animal strains, cas for "central-asia", beijing, x, haarlem, lam for "latino-american and mediterranean", t and manu. monophyly of each of the lam, t and haarlem families has been partly invalidated. however, the larger lineage to which they belong and that is characterized by the 33- spacers deletion at the crispr profile has been confirmed and designated as the "euro-american" lineage. it corresponds to the principal genetic groups and as defined by sreevatsan et al.. altogether deletions in spoligotype patterns have proven to contain phylogenetic information and allow most strains be assigned to the families described above. assignations performed by experts are reported in spoldb database, patterns carrying no or contradictory signatures been labeled as "u" for "unknown or unclassified". to circumvent the dependence on experts' analysis, the bennett's laboratory proposed automatized classification of spoligotype patterns using bayesian algorithms and a distance method taking into account the deletion process by which spoligotype patterns evolve. they provide an on-line tool called spotclust to assign each spoligotype to a family, either one described in spoldb or one of the large families proposed by gagneux and coworkers. here we wanted to take advantage of a recently developed algorithm, affinity propagation, to confirm and extend these methods. this algorithm identifies references for every data point so that data are grouped and centered on these references while a specific cost function is minimized. the cost of adding a new reference point, assigned by the user, determines the final number of clusters. prior to the use of this algorithm, we tested different distances to calculate pairwise distances between spoligotype patterns. we took advantage of previously identified references and expert assignation to rank these distances, some of which are derived from previously proposed evolutionary models. the distance that best identified the appropriate reference for each spoligotype pattern was implemented in the affinity propagation algorithm to identify relevant subfamilies among m. tuberculosis complex. these families partly correlated with previously identified subfamilies. altogether, this approach allowed us to assess the robustness of previously identified sublineages among mtc, to identify new relevant sublineages and to provide re-assignations of the spoligotype patterns described in spoldb these re-assignations interestingly matched those of studies using vntr and/or snp data.  comparison of classifications based on new distances or on jaccard index to expert classification of spoldb4 clustering of crispr patterns of m. tuberculosis complex is commonly done using the jaccard index as distance. this index counts the shared spacers without taking into account their spatial organization. however, it has been shown that adjacent spacers have a higher probability to be simultaneously deleted, and this feature has been used by experts to define m. tuberculosis complex families and subfamilies in the international database spoldb. we wanted here to identify a distance conducing to the best concordance of spoligotype assignations at the family level, as available in spoldb database. we retained the ten widely acknowledged families: m. africanum, animal strains, beijing, cas, eai, haarlem, lam, manu, t and x. each is characterized by a different spoligotype signature and thus a different reference profile. in addition to jaccard index, we set up three methods to compute the distance between pairs of patterns: "domain walls" measuring the proportion of shared limits of blocks of spacers in the crispr locus, "blocks" measuring the proportion of shared blocks of spacers, and "deletions" measuring the proportion of shared blocks of deleted spacers. we implemented these four methods to compute the distances of each spoligotype of spoldb database to the reference profiles of the ten families. for each method, depending on the reference to which it was most similar, each spoligotype was assigned to one of the ten families. spoligotype patterns for which two references were equally similar were coined as unassignable. these assignations were compared to the spoldb classification. the jaccard method rarely associated the spoligotype patterns to their reference. the methods that best fitted the expert classification were the "deletions", and the "domain walls" method. these methods also provided the smallest amount of assignations that differed from those of the experts. these methods thus appear to be the best for fitting the expert classification out of the four methods we tested. beij = beijing also referred to as east asia; cas = central asia also referred to as east africa and india; lam = latino-american and mediterranean; h = haarlem; eai = east african indian. "deletions" method succeeds in correcting false spoldb assignations some families' assignations provided by spoldb have been debated. for instance, patterns classified as lam7-tur have been found not to be related to the lam family as strains carrying that pattern do not share the ligb mutation that defines the lam family. such strains were instead related to t-strains and were renamed tur. all methods tested here except the "deletions" method still assigned them to lam family, including spotclust. the "deletions" method assigned them all to the t family as did methods using vntrs or snps. similarly, all spoligotypes assigned to the h subfamily in spoldb were recently excluded from the haarlem family based on them not carrying the mgtc mutation. they were renamed "ural" and appropriately assigned to the t family by the "deletions" method only. hence, part of the assignations suspected to be wrong with the "deletions" method as compared to expert classification may in fact correct previous classification errors. the "deletions" method thus recognizes phylogenetic lineages better than "domain walls" method and likely at least as well as the expert eye and spotclust. this is further supported by the clear gap between the similarity of correctly assigned spoligotype patterns to their reference and the highest similarity to any reference of patterns assigned differently than by the expert specifically with the "deletions" method. "recent literature assignation" represents the standard, and refers to studies using loci other than the crispr locus: t-tur classification has been suggested both by millet et al. and abadia et al. based respectively on vntr signature and snps signatures. t-ural classification has been suggested by kovalev et al. as they clustered with h37rv strains and abadia et al.. rim: randomly initialized model. n... families as defined by spotclust are described on their web-site based on what spoldb families/sub-families are mostly represented: n family is described as lam3-rich; n as h1-rich; n as lam-rich; n as lam+eai-rich; n as h3+s-rich; n as t3-africanum-rich; n as x1-h37rv-rich. the assignations matching the standard are shown in bold characters. assignations failures are shown in italic. note that the "deletions" method provides the highest number of exact assignations and the least assignation failures. interestingly, beijing, x and eai families exhibited no incongruence between the "deletions" and the expert method, suggesting that these families are clearly and appropriately defined. as reported above, the jaccard method failed to assign most spoligotype patterns to any family; for instance, no spoligotype patterns could be assigned to beij, eai or x families with a maximum similarity to any reference not reaching 20% for beij family. "domain walls" and "blocks" methods provided either poor resolution between correctly and wrongly assigned spoligotype patterns, or a lower number of families with no discrepancy with the expert classification. assignations of u spoligotype patterns assignations thus seem phylogenetically relevant using the "deletions" method and the references of the well-acknowledged families. we thus propose an alternative spoligotype patterns classification on the spoligotypes reported in spoldb. assignation rate of "u" patterns was relatively low with this method as compared to others but may be more reliable as exemplified by three u patterns recently assigned: "deletions" method could only assign one of them but without error whereas two of the three assignations provided by the "domain walls" method and spotclust algorithm were erroneous. automatized identification of references by affinity propagation clustering the "deletions" method is highly useful to classify spoligotype patterns in the described families, but this classification highly depends on the identification of references. these references are widely acknowledged for major families but the relevance of finer classification is recurrently debated. affinity propagation is an algorithm that identifies a representative for each data point in an iterative manner until the chosen configuration of exemplars minimizes a suitable cost function that depends on the choice of the clusters. a parameter set by the user determines an additional cost for every exemplar found. when p is low, large clusters are built where some data points have relatively low similarity with their representative. as p increases, the clusters reach smaller sizes so that they become numerous, and the mean similarity with the representative increases. interestingly, when the number of clusters does not vary even if the penalty changes, this indicates that the data points are not evenly distributed, i.e., form meaningful clusters. when applying this method to the spoldb dataset, relevant numbers of clusters were found to be and. the mean similarity with the representative was higher using affinity propagation as compared to k-means or with bionumerics applying hierarchical clustering. the clustering in clusters reproduced most of the references identified by the experts. however, h family was divided in h and h none of them including the h h was grouped with t spoligotype patterns as suggested by previous studies that renamed it ural. we propose some renamings according to major families represented in each cluster. when performing clustering with clusters, many of the spoldb subfamilies were identified. some of them were however merged such as africanum2-africanum bovis1- pinnipedii-microtii, lam2-lam1-lam x and in x, etc.. among eai, four meaningful subfamilies were identified whereas only were among lam. this suggests that the lam family was oversplitted in the expert classification. in contrast, seven subfamilies were found among the t family. two of them exhibited complex signatures with few spoligotype patterns actually matching the whole signature. subfamilies t t and t were confirmed by this method. one family still had sit as a reference indicating that many spoligotypes still cannot be further classified according to their spoligotype pattern. last, one family was created from u spoligotypes and has sit as a reference. most patterns carried the deletion of spacers to that could constitute a new significant signature. countries in which the corresponding sits were most abundant surround the indian ocean: madagascar, thailand, india and vietnam. we thus named it sea. the significance of this signature compared to the classical eai signature, which differs only by the presence of spacer remains to be established. beij = beijing; afri=m. africanum; cas = central asia; lam = latino-american and mediterranean; h = haarlem; eai = east african indian. confirmed families are shown in bold. beij = beijing; afri=m. africanum; cas = central asia; lam = latino-american and mediterranean; h = haarlem; eai = east african indian. confirmed subfamilies are shown in bold. note that most of the patterns carry the 29- spacers deletion, and that most of them are unclassified by spoldb "main country" refers to the country where the highest number of isolates carrying this pattern were found according to spoldb. * indicates the spoligotype proposed as a reference by the affinity propagation algorithm. the countries are identified via the iso3166- alpha- code. tha = thailand; gbr = united kingdom; gnb = guinea-bissau; bra = brazil; est = estonia; mys = malaysia; bgd = bangladesh; geo = georgia; mdg = madagascar; nld = netherlands; vnm = vietnam; usa = united states. discussion here we first validated a simple distance method that can be used to classify crispr genetic profiles based on a worldwide m. tuberculosis spoligotype database. second, using a recent clustering algorithm exploiting a different approach with respect to those commonly used in the biological sciences community, we could identify an alternative m. tuberculosis classification. the comparison between the largely validated expert classification described in the international database spoldb and our alternative classification validates our approach for m. tuberculosis crispr profiles, opening the way for its use for other bacterial species where crispr were shown to provide interesting typing information. clustering power of crispr patterns m. tuberculosis complex has been infecting humans for at least years and could be years old or even much older. despite its restricted genetic diversity even between human and animal strains, phylogenetical relationships have been detected using polymorphic dna sequences. crispr loci characterized using the "spoligotyping" technique have been used to define families through the use of so-called signatures i.e. the absence and presence of characterized units of cripsr loci, the spacers. most of these families found independent support such as host range or congruence with independent genetic markers, even snps and regions of deletion. however, some of them were "ill-defined" i.e. had a signature that was shared by several other groups, and others were defeated by independent loci: h subfamily was renamed ural as it was related to t strains and not h strains, lam and lam were renamed tur and cameroon respectively as they are unrelated to lam strains. as a consequence, the use of crispr patterns to infer phylogenetical relationship was recurrently discussed. we used here an automatized approach for clustering crispr patterns. our clusters largely reproduced the well-acknowledged mtc families and provided meaningful clustering for ural, tur and cameroon. in fact, the misclassification of ural among haarlem family was due to the merging of all signatures having spacer deleted and spacer present disregarding the left border of the deletion. this classification criterion is not relevant knowing the evolutionary dynamics of crispr loci due either to the insertion of is elements or to the deletion of one of several adjacent spacers. this kind of errors is avoided if comparison is performed using an algorithm identifying complete signatures as included in our automatized approach. still, the fact that some families are "ill-defined" is an intrinsic problem of spoligotyping: crispr loci in m. tuberculosis are relatively short and they evolve at a rate that cannot exclude the absence or the insufficient number of mutation in some lineages. this intrinsically limits the power of our study, i.e. we cannot classify all strains, and not all of them with the same precision. however, this problem does not affect the assignation quality of the strains we classify which are in fact numerous. we thus argue that crispr profiles evolving by the insertion of transposable elements or by deletion such as those of m. tuberculosis contain relevant information for clustering and even inference of some phylogenetic links. the targeted locus must however not be missing for the individuals to be classified. to avoid this pitfall, the use of crispr loci should restrict to recently diverged groups as is the m. tuberculosis species complex. such organisms uncover diverse human pathogens such as yersinia pestis, salmonella enterica, bacilllus anthracis, mycobacterium leprae and mycobacterium ulcerans. still, the use of crispr profiles in phylogenetic reconstructions would benefit from further developments and validations for species with still active crispr loci. distance methods for crispr profiles if crispr can be used to infer phylogenetic relationship, the evolutionary model or distance method used during the inference is also of great importance. several developments had been proposed until now. we want to discuss here what our approach adds to previous ones. crispr profiles form a sequence of binary data. as such, it has been analyzed with tools developed for binary information such as the jaccard index that focuses on the sharing of every unit in the profile taken independently. this however ignores an essential feature of the corresponding crispr locus: that it evolves by the loss of spacers. these losses can occur either because of the insertion of a transposable element that disrupts the sequence used in the spoligotyping technique, or by deletion. deletions can occur for several spacers at once, even if the frequency of large deletions may be lower. as a consequence, the distance between two patterns, one carrying many spacers and the other carrying one large deletion, should not be considered as proportional to the number of spacers that were lost, but as corresponding to a single mutation event. the methods proposed by the bennett laboratory take into account the deletion process and add a probability function that best mimics the frequency of deletion size. in spotclust, a bayesian algorithm incorporating the inference of ancestral spoligotype patterns based on spoldb database is used to assign spoligotypes to spoldb subfamilies or to families built using a randomly initialized model. we showed here that, by simply using expert-defined references of main families and the "deletions" distance method that is based on deletion signatures, we could better assign unknown spoligotype patterns than spotclust as well as correct previous erroneous assignations in spoldb classification such as those to lam. for spotclust algorithm, this was true for both the spoldb3-based classification and the randomly initialized model. the reason for that could be either that the size of the database used by spotclust was too small to capture evolutionary steps relevant to mtc evolution, or that bayesian statistical inferences are too dependent on priors. performance of the affinity propagation algorithm on crispr profiles clustering affinity propagation is a message-passing algorithm that considers clustering as a problem of minimizing an "energy" function of the clusters configuration in the data set. this approach seems particularly promising and could help solving species delineations in asexual lineages where obligate gene exchange cannot be used as a delineation criterion. one of the main features of the algorithm is the possibility of regulating the total number of clusters as a function of an input parameter of the algorithm. also the high speed and thus the possibility to analyze very large networks is encouraging the use of this algorithm. with this method we identified both families and subfamilies in mtc. a single family out of made no sense. this is likely due to a lack of information in beijing spoligotype pattern as the large 1- deletion limits the recognition of other signatures. when considering patterns carrying a larger number of spacers, the classification was largely congruent with the literature. in addition, we could identify new signatures, especially one, termed sea among previously unclassified patterns. we therefore believe that this algorithm is very useful for classifying the widely used 43-spoligotype patterns in m. tuberculosis but could prove even more useful on patterns larger than spacers, e.g. the improved spacers format. "euro-american" lineage evolution despite large sequencing efforts, there has been a standing difficulty in unraveling the relationships inside "euro-american" lineage strains, especially in the so-called "t family" described in spoldb. here, using spoldb database, we could challenge expert-defined families and subfamilies. we first confirmed the validity of s and t subfamilies that we suggest to consider as families. the s family was first described in sicily and independently identified in québec where a sublineage was shown to harbor a peculiar pnca snp. the t family, defined by the absence of spacer was originally described as m. africanum however was shown later to be a bona fide m. tuberculosis subfamily. we also confirmed the reliability of haarlem family subclustering, if renaming h as ural, and suggest considering h1- and h as two families. we confirmed the validity of t and t families as well as t4-ceu. some lam subfamilies renamings based on vntr and snp loci are given further support, while other were merged. the tendency to merge many expert-defined families was not pervasive. indeed in the eai family, four subfamilies out of the expert-defined ones were confirmed. combining the families and subfamilies identification, we could provide a simplified evolutionary scheme for this lineage. we hope in the future, by applying affinity propagation on spoligotype patterns, to identify other euro-american subclusters.  this study describes 1) a novel distance method to be applied on genetic loci evolving by deletion, as for instance do inactive crispr loci, 2) a framework to take advantage of identified references for classifying individuals using such loci, 3) a way to identify new references using the affinity propagation algorithm, and 4) assignations and assignation tools for m. tuberculosis complex. the distance method and the framework to identify known references were largely validated by worldwide m. tuberculosis database at the crispr locus. this work encourages the use of crispr patterns to cluster strains in other organisms carrying such loci and for which wide genotyping has been undertaken as it is now the case for human pathogens such as yersinia pestis, salmonella enterica, bacilllus anthracis, mycobacterium leprae and m. ulcerans. affinity propagation could also be useful to cluster other genotyping data such as snps or minisatellites. databases larger than those available by now are however required to test the validity of this method on such markers. 
however, where to set limits between groups can be puzzling especially in clonal organisms. to adequately infer the relative divergence time between strains, we used a distance method inspired by the recent evolutionary model by reyes et al. we first confirm that this method performs better than the jaccard index commonly used to compare spoligotype patterns. it also describes well-supported families and subfamilies among m. tuberculosis complex, especially inside the modern "euro-american" lineage. here, we propose to use a method called affinity propagation that has been successfully used in image categorization to identify relevant patterns at the crispr locus in mtc. second, we document the support of each spoligotype family among the previous classification using affinity propagation on the international spoligotyping database spoldb this allowed us to propose a consensus assignation for all spoldb spoligotypes. altogether, this study shows how the new clustering algorithm affinity propagation can help building or refining clonal organims classifications. however, other groups such as t family and t subfamily correspond to non-monophyletic groups and still need to be refined. third, we propose new signatures to subclassify the t family. within the mycobacterium tuberculosis complex, the etiological agent of tuberculosis, experts have first identified several groups according to their pattern at repetitive sequences, especially at the crispr locus, and to their epidemiological relevance.
 classification and naming is a key step in the analysis, understanding and adequate management of living organisms. however, where to set limits between groups can be puzzling especially in clonal organisms. within the mycobacterium tuberculosis complex, the etiological agent of tuberculosis, experts have first identified several groups according to their pattern at repetitive sequences, especially at the crispr locus, and to their epidemiological relevance. most groups such as "beijing" found good support when tested with other loci. however, other groups such as t family and t subfamily correspond to non-monophyletic groups and still need to be refined. here, we propose to use a method called affinity propagation that has been successfully used in image categorization to identify relevant patterns at the crispr locus in mtc.  to adequately infer the relative divergence time between strains, we used a distance method inspired by the recent evolutionary model by reyes et al. we first confirm that this method performs better than the jaccard index commonly used to compare spoligotype patterns. second, we document the support of each spoligotype family among the previous classification using affinity propagation on the international spoligotyping database spoldb this allowed us to propose a consensus assignation for all spoldb spoligotypes. third, we propose new signatures to subclassify the t family.  altogether, this study shows how the new clustering algorithm affinity propagation can help building or refining clonal organims classifications. it also describes well-supported families and subfamilies among m. tuberculosis complex, especially inside the modern "euro-american" lineage. asexual organismsspecies delineationepidemiologydr locusclustered regularly interspaced short palindromic repeats 