Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Bashar Nuaimi

Bassam Alkindy
email: dr.balkindy@uomustansiriyah.edu.iq

Jean-Franc ¸ois Couchot
email: jean-francois.couchot@univ-fcomte.fr

Michel Salomon
email: michel.salomon@univ-fcomte.fr

Bashar Al-Nuaimi
email: bashartalib6@gmail.com

On the reconstruction of the ancestral bacterial genomes in genus M ycobacterium and Brucella

Keywords: Mycobacterium tuberculosis, genome rearrangements, ancestral reconstruction, bacterial lineages, pathogens, evolution

come

Background

Mycobacterium tuberculosis (MTB) is the etiologic agent of human tuberculosis (TB), that is one of the oldest recorded human afflictions which is still among the main worldwide death causes. In 2015, more than 10 million people became ill with TB and approximately 2 millions died from the disease, almost exclusively in low and middle income countries. Moreover, it induces a major global health problem, since about one-third of the world's population has latent TB. Hence this is the first infectious disease declared by the World Health Organization (WHO) as a global emergency. More precisely, tuberculosis is caused by pathogens belonging to the Mycobacterium tuberculosis complex (MTBC) which consists of different species that are typical human pathogens (Micobacterium canettii, africanum, and tuberculosis), rodent ones (M. microti), or even Mycobacteria with a large host spectrum like bovis [START_REF] Shamputa | Introduction and epidemiology of mycobacterium tuberculosis complex in humans. Tuberculosis, leprosy and mycobacterial diseases of man and animals: the many hosts of mycobacteria[END_REF][START_REF] Brosch | A new evolutionary scenario for the mycobacterium tuberculosis complex[END_REF]. Even if these organisms are genetically similar, they exhibit large differences with regard to epidemiology, pathogenicity, and host spectrum. Mycobacterium tuberculosis spreads throughout the human population since thousands of years, as the TB form that attacks bone and causes skeletal deformities can be still identified on individuals who died from it several thousands years ago, like ancient Egyptian mummies with apparent tubercular deformities.

The MTBC species are classified in 6 phylogenetic lineages which can be further divided into sublineages showing phenotypic differences reflecting for example their virulence (pathogenicity). The species members of the Mycobacterium tuberculosis complex have a clonal structure with large genome similarity (more than 99.9 percent of DNA sequences in common [START_REF] Mostowy | Genomic deletions suggest a phylogeny for the mycobacterium tuberculosis complex[END_REF]). Compared to more ancient species, this complex has more virulent chromosomes [START_REF] Yamada-Noda | Mycobacterium species identification-a new approach via dnaj gene sequencing[END_REF]. As they have the same ancestor [START_REF] Fabre | Molecular characteristics of "mycobacterium canettii" the smooth mycobacterium tuberculosis bacilli[END_REF], the fact that we can find rodent and human pathogens, and other with a larger spectrum, is indeed surprising. To study M. tuberculosis DNA sequence, its virulent laboratory strain M. tuberculosis H37Rv is commonly used. This strain consists of a single circular chromosome composed by 4,411,532 nucleotides and 3,906 protein genes. DNA homology studies and comparison of 16S rRNA coding regions have permitted to establish how they are linked, showing a 95 -100% DNA relatedness. For example, there is only one difference between the 16S rRNA gene sequence of M. tuberculosis and the one of M. bovis.

The long-term coevolution of Mycobacterium tuberculosis with humans [START_REF] Brites | Co-evolution of mycobacterium tuberculosis and homo sapiens[END_REF] has led to a more or less large geographic spread of the different phylogenetic lineages of MTBC. Moreover, some of the lineages appear to have a large geographic distribution, while others seem to be restricted to a smaller group of human host populations. Over time, MTBC genomes have evolved through genomic repetition or replacement (insertion sequences, etc.) and genomic modification at different scales of complexity. In this latter case, modifications range from small-scale ones resulting from mutation or indels to larger ones occurring on DNA strands (inversion, duplication, or deletion).

Obviously, understanding the past and future evolution of the MTBC would be of great interest, leading to the ability to study the ancestors and to understand the evolution history of species, and finally to an improved knowledge of the mechanisms of resistance and virulence acquisition in human tuberculosis. Fortunately, the relatively short time-frame during which the MTBC emerged (this bacteria is quite recent [START_REF] Wirth | Origin, spread and demography of the mycobacterium tuberculosis complex[END_REF]), the relatively low genomes lengths and the recombination scarcity, together with an easier access to ancient and current DNA sequences, are favourable factors to address this question. Therefore, it should be possible to design a model of evolution for this set of genomes, in order to recover their evolution history and to predict their future evolution.

Another interesting group of pathogenic bacteria to be investigated is the genus Brucella which causes Brucellosis, a disease that primarily affects animals, especially domesticated livestock, producing abortion and other reproductive disorders. Human can also be infected, mainly through animal-to-person spread, in which case longlasting flu-like symptoms are observed. Like tuberculosis, brucellosis is a global problem, since it is the most common bacterial infection spread from animals to humans worldwide. After the recent identification of the species B. vulpis, a total of eleven species have been identified within the genus Brucella according to their pathogenicity and preferential animal host [START_REF] Halling | Completion of the genome sequence of brucella abortus and comparison to the highly similar genomes of brucella melitensis and brucella suis[END_REF][START_REF] Foster | Whole-genome-based phylogeny and divergence of the genus brucella[END_REF] Clearly, a detailed knowledge of the Brucella phylogeny would also be of great interest. First, the phylogenetic reconstruction can lead to an enhanced understanding of the ecology, evolutionary history, and host relationships of this genus. Second, it can be used to discover suitable genotyping methods for rapid detection and diagnostic measures, used for example in epidemiological studies to facilitate human disease research. Moreover, as the Brucella genus is highly conserved and has low genetic variation, the phylogenetic reconstruction is still a challenge, even if the Brucella genus is probably easier to tackle than the MTBC.

This requires the development of new algorithms for the detection and evolution of genomic changes. Researchers studying this question focus mainly on the nucleotidic mutations prediction, and take specific forms for the matrix of mutations that seem not in accordance with recent experimental evaluations, see [START_REF] Bahi | Predicting the evolution of two genes in the yeast saccharomyces cerevisiae[END_REF]. These evolutionary models must be constructed in a different manner, to better reflect what really occurred. Moreover, the important effects of other genome changes (such as nucleotide insertions and deletions, large-scale recombination, or repeated sequence changes) have to be considered more deeply, and an effective ancestral reconstruction of ancient bacteria should be carried out.

This research work is an extension of an article presented to the 5th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO 2017, [START_REF] Guyeux | On the ability to reconstruct ancestral genomes from mycobacterium genus[END_REF]). Its main objective is to show that, if we focus on strongly related bacterial chromosomes, the reconstruction of their most recent common ancestors is possible in practice. In order to do so, we propose a pragmatic approach that mix already published reconstruction algorithms with new original scripts and a human cross-validation. As an illustrative example, we provide the ancestral reconstruction of 65 genomes of the Mycobacterium tuberculosis complex, and of the 47 Brucella genomes that are available on the NCBI database.

The dynamics of the evolution process in DNA sequences results from local evolutionary events that consist in SNPs or indels. Genomic rearrangements, which are larger alterations of the genetic organization, can take the form of inversions and transpositions, or occur by chromosome fusion and fission. Obviously, over time such large-scale mutations have affected gene order and content, therefore they have a prominent role in speciation [START_REF] Fertin | Combinatorics of Genome Rearrangements[END_REF]. A key problem when studying evolutionary change at the level of a DNA sequence, which is investigated by the research work presented in this article, is the problem of ancestral sequence reconstruction. This one is as follows: given an evolutionary tree relating organisms and the DNA genomic sequences of the leaf species, predict the DNA sequence of all ancestral species in the tree. Many biological studies have addressed this problem and thus various methods have been proposed for inferring ancestral sequences. Apart from ancestral genome reconstruction problem, biomolecular evolution is usually devised through the evolution of core and pan-genome. Below is a brief overview on ancestral genome reconstruction.

Similarities in sequences or in the gene order (genome composition) are usually considered in up-to-date ancestral reconstruction methods. The first case, based on sequence similarity, can be considered as resolved now, at least when indels are not considered [START_REF] Ma | Dupcar: reconstructing contiguous ancestral regions with duplications[END_REF][START_REF] Gagnon | A flexible ancestral genome reconstruction method based on gapped adjacencies[END_REF][START_REF] Jones | Anges: reconstructing ancestral genomes maps[END_REF][START_REF] Ma | Reconstructing contiguous regions of an ancestral genome[END_REF][START_REF] Hu | Probabilistic reconstruction of ancestral gene orders with insertions and deletions[END_REF][START_REF] Blanchette | Computational reconstruction of ancestral dna sequences[END_REF][START_REF] Rascol | Ancestral animal genomes reconstruction[END_REF][START_REF] Larget | A bayesian analysis of metazoan mitochondrial genome arrangements[END_REF][START_REF] Hannenhalli | Genome sequence comparison and scenarios for gene rearrangements: A test case[END_REF]. Indeed, considering a phylogenetic tree and its associated DNA alignment, Bayesian inference or maximum likelihood approaches can be applied to estimate ancestral states of nucleotides [START_REF] Bouckaert | Beast 2: a software platform for bayesian evolutionary analysis[END_REF][START_REF] Yang | Phylogenetic analysis by maximum likelihood (PAML)[END_REF]. The main problem is the insertion-deletion case, which is usually disregarded [START_REF] Paradis | Ape: analyses of phylogenetics and evolution in r language[END_REF]. The small number of models that consider indels focus on the parcimony approach, or consider the evolutionary model called Thorne-Kishino-Felsenstein [START_REF] Bouchard-Côté | Evolutionary inference via the poisson indel process[END_REF]. Combinatorics investigations are applied in the case of larger modifications, by modeling these recombinations as permutations of homologous sequences. This reformulation leads to the well-known genome rearrangement problem [START_REF] Watterson | The chromosome inversion problem[END_REF], in which the shortest edit operations that can map one chromosome to another are searched. Note that this NP-hard problem [START_REF] Fertin | Combinatorics of Genome Rearrangements[END_REF][START_REF] Even | The minimum-length generator sequence problem is np-hard[END_REF] is directly related to the sequence length and the number of mutations, while genomes considered in this article are quite small and have faced only a low amount of recombination: the difficulty can be circumvented for such genomes.

The remainder of this article is organized as follows. The methodology proposed for ancestral reconstruction is detailed in the next section. Results of the application of this approach on the Mycobacterium tuberculosis complex (specifically on two of its species, namely M. tuberculosis and M. canettii) and on the Brucella genus case (focusing specifically on the B. abortus and B. melitensis species) are investigated in the third section. Finally, this research article ends with a discussion and a conclusion with future work.

Methods

Let us now detail our concrete ancestral reconstruction for bacterial genomes, illustrated through a first set of strains detailed hereafter.

Data acquisition and processing

A python script has firstly been written to automatically download all the complete genomes of Mycobacterium genus available on the NCBI database, encompassing 2 africanum, 15 bovis, 5 canettii, 1 microti, and 42 tuberculosis. Note that canettii and tuberculosis are well represented in this dataset, which is helpful to study how virulence has appeared in the first species, and if the second one is at the origin of the MTBC complex 40,000 years ago. Details about these 65 genomes are provided in Table 1.

After the data acquisition stage, the next step is to align the downloaded sequences [START_REF] Kemena | Upcoming challenges for multiple sequence alignment methods in the high-throughput era[END_REF][START_REF] Warnow | Large-scale multiple sequence alignment and phylogeny estimation[END_REF]. Prior to the Multiple Sequence Alignment (MSA), genomes must be operated such that each sequence starts to the same location and is read in the same direction: we deal with circular genomes. This is why a sequence of reference (200 bp from M. tuberculosis H37Rv) and its reverse complement have been blasted locally. Then, a circular shift and/or a reverse complement of the whole sequence have been applied when required.

Most of the well-known alignment tools have failed to align these genomes, due to their size, while we do not want to split the sequences, to reduce the complexity of the alignment, as this multiplies the intermediate steps, increasing by doing so the risks of errors. It was not the case of AlignSeqs, available in the R module called decipher [START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF]. This latter achieved to perform the MSA in an accurate and rapid way. With this tool, multiple sequence alignments are done by aligning 2 genomes first, and then adds a third genome, etc., until all the sequences are aligned [START_REF] Gentleman | Bioconductor: open software development for computational biology and bioinformatics[END_REF].

Phylogeny

The alignment of multiple genomes of Mycobacterium leads to the visualization of synteny blocks, emphasizing the location of large inversions.

A manual reverse of these inversions were possible, leading to an improvement of the alignment of the 65 genomes. This is beneficial for the next stage of the pipeline, namely the phylogenetic investigation. This stage has been performed using RAxML, in which the phylogenetic tree is reconstructed according to a maximum likelihood approach [START_REF] Alkindy | Hybrid genetic algorithm and lasso test approach for inferring well supported phylogenetic trees based on subsets of chloroplastic core genes[END_REF]. Note that, thanks to the manual reverse of inversions, the obtained tree has been computed using almost all the complete genomes (only columns with indels are ignored), while without this manual operation, all columns inside the inversion are disregarded. Being based on almost all the genomes, and being strongly supported according to bootstrap values, the obtained tree is trustworthy, and we can reasonably consider it as a backbone to reconstruct ancestral states of MTBC nucleotides.

The proposed ancestral reconstruction is in two parts: 1-length modifications (SNPs and indels) are first considered, before investigating larger modifications (insertion, deletion, or duplication of large scale subsequences). These two case are detailed below.

Ancestral reconstruction: the mononucleotidic variants case

The treatment is divided in two sub-parts: insertion-deletions on the one hand, and single nucleotide polymorphisms on the other hand. The second case is simple, and its difficulty is only in the separation between real SNPs and polymorphism induced by an indel recombination. The first case is more complicated, as indels may be related to mobile elements or tandem repeats. These two cases are detailed below.

Ancestral reconstruction of SNPs is realized as follows. We first compute the marginal probability distributions in each nucleotide of internal vertices in the phylogeny obtained previously. Assuming a site independence, we have applied the sum-product message passing method [START_REF] Pearl | Reverend bayes on inference engines: A distributed hierarchical approach[END_REF] to calculate these distributions. This method has been applied by using PHAST [START_REF] Hubisz | Phast and rphast: phylogenetic analysis with space/time models[END_REF], which is able to reconstructs ancestral indels too (parsimony approach).

Ancestral reconstruction: the case of larger variants

In the case of mid-size modifications over time, a string algorithm has been first designed to detect sequence inversions (even in the case of small and noisy ones).

However, and due to the fact that MTBC complex is reputed to evolve in a clonal manner, only artifacts have been detected by applying this algorithm on supercomputer facilities. This will not be the case if this pipeline is applied to more recombinating bacteria like the Pseudomonas or Yersinia genus. Note that, up to now, duplications have not yet been regarded, as the synteny block analysis performed previously has shown that large scale duplications have not occurred in the MTBC case.

Conversely, midsize indels and SNPs have been investigated in details by using PHAST. This investigation has allowed us to notice that: [START_REF] Shamputa | Introduction and epidemiology of mycobacterium tuberculosis complex in humans. Tuberculosis, leprosy and mycobacterial diseases of man and animals: the many hosts of mycobacteria[END_REF] In most of the cases, the situation is obvious, leading either to a deletion or an insertion at a well specific location inside the phylogenetic tree, like in Figures 1 and2. (2) These larger variants events are rare in various lineages (e.g., tuberculosis), as illustrated in Table 2. (3) In the case of indels of size ≥ 2, the parsimony approach of PHAST produces frequently a wrong ancestral state deduction, which must be modified by hand. Note that its competitors have been tested too, and they all presented worse reconstructions on our specific dataset. (4) The inserted sequence has, in general, not faced additional mutations over times.

This semi-automatic pipeline for ancestral genomes has finally succeeded to reconstruct the genomes at each internal node of the tree, which can be done because the number of recombination of more than one nucleotide is low. These recombinations have mainly been deduced manually, while state-of-the-art tools have not been able to reach an acceptable level of accuracy.

Figure 3 summarizes all the ancestral reconstruction process, in which the gray boxes are operated manually, while the other stages are automatic. Indeed, obtained results on mononucleotidic variants have been carefully checked by naked eye, as the number of such variants is lower than one hundred, while ad hoc algorithms were designed to deal with variants of larger size, see Figure 4.

CRISPR investigation

Another particular DNA pattern that can evolve through Evolution is the so-called CRISPR one. CRISPR refers to repeated DNA sequences that help to preserve organisms from noticeable threats like viruses. These sequences are a fundamental component of some immune systems, which helps to protect their organism's health. Such repeated DNA sequences are found in archaeal and bacterial genomes. These sequences range in size from 23 to 47 base pairs.

The name of CRISPR refers to an acronym which stands for Clustered Regularly Interspaced Short Palindromic Repeat [START_REF] Barrangou | Crispr provides acquired resistance against viruses in prokaryotes[END_REF][START_REF] Grissa | Crisprfinder: a web tool to identify clustered regularly interspaced short palindromic repeats[END_REF]. The CRISPR system was initially found as part of an immune system of sorts in some bacteria, used for cutting apart foreign DNA. It consists of two parts of the protein itself, which is the workhorse of the CRISPR system: a bacterial enzyme named Cas9, and a small RNA, called the guide RNA, that matches the DNA sequence to be nicked [START_REF] Sander | Crispr-cas systems for editing, regulating and targeting genomes[END_REF].

Results

The Case of Mycobacterium Tuberculosis Complex All the 65 Mycobacterium genomes have been aligned thanks to the AlignSeqs function described previously. We thus obtained a first representation of synteny of all of them, see Figure 5. As can be seen, genomes are very similar in the MTBC case, and only a low number of recombinations have occurred within these genomes.

As an illustrative example of the phylogenetic study depicted in Sec. , the phylogeny of M. canettii is represented in Figure 6 (outgroup: M. tuberculosis). We selected the GTR Gamma model of nucleotide substitution as recommended by JModelTest 2.0, and the tree has been computed by RAxML. Note that the obtained tree is well-supported, as well as in the M. tuberculosis cased, whose supports are larger than 98% (cf. Figure 7). Indeed, with these bacteria, we have not to find the most supported tree based on the largest subset of core genes, as aligning the whole complete genomes leads to a well supported tree: it is not possible to improve the results, which is nice as the core genome is many times greater than in the chloroplast case (and so, it is not sure that the heuristic approach presented in our previous articles [START_REF] Alkindy | Hybrid genetic algorithm and lasso test approach for inferring well supported phylogenetic trees based on subsets of chloroplastic core genes[END_REF][START_REF] Alkindy | Binary particle swarm optimization versus hybrid genetic algorithm for inferring well supported phylogenetic trees[END_REF][START_REF] Alsrraj | Well-supported phylogenies using largest subsets of core-genes by discrete particle swarm optimization[END_REF] can succeed to find the optima).

The obtained results on mononucleotidic variants have been humanly verified, which has been possible due to a low number of variants (cf., for instance, to Tables 3 and4).

166 indels and 2,956 SNPs have finally been detected, when considering the 5 M. canettii (see Fig. 8). Figure 9, for its part, collects the positions of the 25 indels and 394 SNPs that have been detected in the clade of the 8 M. tuberculosis.

In the considered Mycobacterium strains, only a few important inversions have been detected, such as the inversion present in the last ancestor of 140070010, CIPT 140010059, 140070017, 140060008, and 140070008, as shown in Figure 10. 99% of DNA sequence identity has been obtained when considering all the blocks of synteny of tuberculosis. We can conclude that these genomes are highly conserved: highly similar regions without any rearrangement, with only small indels and a large inversion.

We can conclude from this study that ancestral genome reconstruction is possible when considering close or clonal bacteria, and all the material needed in such a pipeline has been designed. But, for the sake of comparison, it may be interesting to deep investigate the results of this semi-automatic reconstruction method on a quite more stable genus, namely the Brucella, on which human validation of algorithm results is easier (see Tables 5,[START_REF] Brites | Co-evolution of mycobacterium tuberculosis and homo sapiens[END_REF] and 8 for an illustration of their alignment and SNP differences). Such new investigations are conducted in the next section.

The Case of Brucella genus

The pipeline presented in the previous section is now applied on another genus, namely the Brucella one, for the sake of comparison and to broader the discussion. Complete sequences of the 47 available genomes have been downloaded from NCBI, namely by species: B. abortus (14 genomes), melitensis [START_REF] Halling | Completion of the genome sequence of brucella abortus and comparison to the highly similar genomes of brucella melitensis and brucella suis[END_REF], sui [START_REF] Ma | Reconstructing contiguous regions of an ancestral genome[END_REF], ovis (1), canis (3), ceti (2), pinnipedialis (2), neotomae (0), microti, inopinata, and vulpis, as described in Table 7.

Note that the genome of Brucella abortus has two circular chromosomes. The first one is 2,124,241 bp long in the Brucella abortus biovar 1 str. 9-941 reference genome, while the second chromosome is of 1,162,204 bp. Other species in the Brucella genus are comparable in genome size. For instance, the Brucella melitensis strain 16M is constituted of 3,294,931 bp disseminated in two circular chromosomes: chr. I has 2,117,144 bp, while chromosome II has 1,177,787 bp. On both of these chromosomes, approximately 3,100 ORFs were predicted. In the latter, genes encoding for DNA replication, protein synthesis, core metabolism, and cell-wall biosynthesis can be found on both chromosomes [START_REF] Delvecchio | The genome of brucella melitensis[END_REF][START_REF] Michaux-Charachon | Genome structure and phylogeny in the genus brucella[END_REF].

We operated the sequences so that they share the same orientation (which may need a transconjugate operation) and the same sequence of 200 nucleotides as starting point (which may require a circular shift), if we except local SNPs. This has been achieved using a local blast, with the beginning of Brucella abortus 2308 as an arbitrary reference. After such operations, a syntheny representation of Brucella genomes can be obtained, as shown in Figure 11. The particular case of B. abortus is depicted in Figure 12.

A few inversions have appeared in this representation. For instance, in the B.abortus case, we found a significant inversion at the last common ancestor of strains"biovar 1 str. 9-941", S19, A13334, "strain BDW", "bv. 2 str. 86/8/59", and 104M. We have manually reversed these inversions, so that an accurate alignment of the whole genomes can be performed. Using this alignment, a very well supported phylogenetic tree has been obtained. For the sake of illustration, a subtree corresponding to the phylogeny of the Brucella abortus species is depicted in Figure 13, and in Figure 14 for B. melitensis. It has been obtained using the entire genome sequences with RaxML, GTR Gamma model, and Brucella melitensis as outgroup. As can be shown, all branches exhibit a 100% bootstrap support value.

At this stage, all the material required to attack the ancestral reconstruction of Brucella genomes are on hand. We first have focused on the abortus and metilensis reference species, to investigate the potential origin and the history of the global spread of these Brucellas. We have considered the global alignment of both chromosomes 1 and 2 of the available complete strains, using decipher R package [START_REF] Wright | Using decipher v2. 0 to analyze big biological sequence data in r[END_REF], and the tree depicted in Figure . 13 and 14. We firstly achieved a comparative whole-genome single nucleotide polymorphism analysis of these strains collected and downloaded from the NCBI. 32 indels and 373 SNPs have been detected in the clade containing these 6 variants of chromosome 2, and 609 SNPs and 325 indels in chromosomes 1, as shown in Figure 15. The same has been computed for B. melitensis, leading to 6178 variants and 335 indels, see Figure . 16. This has been achieved using homemade python scripts on aligned sequences.

At mononucleotidic variant level, the treatments of SNPs and of indels have been separated. Examples of mononucleotidic ancestral reconstructions are provided in Figure 17. Differences between ancestors and their children are, for their part, provided in Table 6 (abortus) and 8 (melitensis).

Figure 12 shows homologous regions among many Brucella abortus genomes, as identified by FindSynteny (R). On the one hand, the similarity and preservation of synteny blocks on Brucella abortus are especially pronounced in chromosome 1, with highly similar regions and without rearrangement of homologous backbone sequences as shown in Figure 12(a). Chromosome 2, on the other hand, is more diverse. There is above all a significant reversal in the Brucella abortus genomes of the clade consisting of abortus 0, 1, 2, 4, 10, and 12 as shown in Figure 12(b). The same information is provided for B. melitensis (chromosome 1) in Figure 18. These differences most likely represent distinct evolutionary origins, for instance related to the nature of functional genes in the two chromosomes.

We finally analyzed the CRISPR locus sequences of 14 Brucella abortus strains by using CRISPRs web service (http://crispr.i2bc.paris-saclay.fr). The orthologous sequence shared between Brucella abortus genomes and the CRISPR spacer have shown a significant similarity of the spacer sequences. Figure 19, for its part, shows the CRISPR space sequence lengths and their positions inside abortus genomes. For the B. melitensis case, information are provided in Figure 20.

Discussion

Various algorithms and methods can be found in the literature to resolve, at least partially, the ancestral genome reconstruction problem. We have shown that these existing methods are not accurate and mature enough to be applied on a real case scenario. This is particularly evident when indels or single nucleotide polymorphisms are mixed with repeated sequences. The main drawback of these methods is that they intend to solve all the cases, while some situations are up-to-now too difficult to be resolved automatically. However, in mid-size genomes that have faced a low number of recombinations over time, as for Brucella and Mycobacterium, these problematic situations can be signaled, and a human cross-validation can reinforce the accuracy of the ancestral reconstruction algorithm.

As a proof of concept, all ancestral genomes of all M. canettii available on the NCBI database have been reconstructed, as well as all the ancestors of the available M. tuberculosis complete genomes. At each time, the single nucleotide polymorphism level has first been investigated, before considering the cases of indels and large scale recombination.

Obtained results show that a concrete and accurate reconstruction can be achieved by coupling human decisions on problematic situations with automatic inference of ancestral states in easy to resolve ones, at least for some non recombinant bacteria. With such a reconstruction, it may be possible to deeply investigate the evolution of genomes over time, and possibly to predict their future modifications.

Conclusion

In this article, we presented a semi-automatic pipeline that achieves to completely and accurately reconstruct the ancestral genomes of some clonal bacteria. In this pipeline, the case of SNPs and indels of 1 nucleotide has been resolved using the sum-product message passing algorithm, while larger modifications have been studied by a parsimony approach coupled with a manual deduction.

The obtained ancestors have not yet been investigated in this study, as it was not the objective of this proof of concept. They will be studied with ad hoc algorithms to design, to investigate the evolution of gene content on the one hand, and of mobile elements on the other hand [START_REF] Al'nayyef | Relation between insertion sequences and genome rearrangements in pseudomonas aeruginosa[END_REF][START_REF] Al-Nuaimi | Relation between gene content and taxonomy in chloroplasts[END_REF]. The rate at which such loss or gain occurs will be examined carefully, and we will study if some particular functionality are more affected by these mutations. To say this differently, we will investigate if modifications have a real impact during the evolution of genomes.

FiguresFigure 1

 1 Figures

Figure 2

 2 Figure 2 Ancestral reconstruction of one problematic indel in the alignment.

Figure 3 TablesFigure 4

 34 Figure 3 Flowchart of the proposed approach.

Figure 5 Figure 6 MFigure 7 M

 567 Figure 5 Synteny blocks of Mycobacterium strains available online.

Figure 8

 8 Figure 8 SNPs location of mononucleotidic variants of M. canettii.

Figure 9

 9 Figure 9 SNPs location of mononucleotidic variants of M. turberculosis.

Figure 10

 10 Figure 10 Synteny blocks in M. canettii. Each genome is colored according to the position of the corresponding region in the first genome (gray if a region is unshared).

Figure 11

 11 Figure 11 Brucella, chromosome 1: a high sequence similarity with little recombination events.

Figure 12

 12 Figure 12 Synteny map of Brucella abortus (a) chromosome 1 and (b) chromosome 2. Genomes investigation tends to show a high sequence similarity with little recombination events. Each genome is colored according to the position of the corresponding region in the first genome, or gray if a region is unshared.

Figure 13 Figure 14

 1314 Figure 13 Well-supported phylogeny of Brucella abortus species calculated on the entire chromosome 1. The outgroup is melitensis, while RaxML has been launched with the GTR Gamma model.

Figure 15

 15 Figure 15 SNPs location in Brucella abortus species.(a) Chromosome 1, (b) chromosome 2.

Figure 16

 16 Figure 16 Single nucleotide polymorphism in Brucella melitensis species.

Figure 17 Figure 18

 1718 Figure 17 Nucleotides in the ancestral nodes and their children on Brucella abortus species.

Figure 19

 19 Figure 19 Brucella abortus phylogenetic tree: estimation of the CRISPRs length and locations by using the CRISPRFinder web server [36].

Figure 20 CRISPR

 20 Figure 20 CRISPR investigation in B. melitensis.

  , among which the six classically recognized species are: B. melitensis, B. abortus, B. suis, B. ovis, B. canis, and B. neotomae. B. abortus and B. melitensis are the most important species regarding prevalence and morbidity in humans and domestic animals.

Table 1 The considered Mycobacterium strains M. canettii SNPs M. tuberculosis SNPs Father Children No. of SNPs

 1

	Accession (GenBank)	Organism name	Sequence length (bp)	Nickname
	CP010335.1	Mycobacterium tuberculosis strain 2242	4,419,839	tuberculosis1
	CP010336.1	Mycobacterium tuberculosis strain 2279	4,405,033	tuberculosis2
	NC 000962.3	Mycobacterium tuberculosis H37Rv	4,411,532	tuberculosis3
	NC 002755.2	Mycobacterium tuberculosis CDC1551	4,403,837	tuberculosis4
	NC 009525.1	Mycobacterium tuberculosis H37Ra	4,419,977	tuberculosis5
	NC 009565.1	Mycobacterium tuberculosis F11	4,424,435	tuberculosis6
	NC 012943.1	Mycobacterium tuberculosis KZN 1435	4,398,250	tuberculosis7
	NC 016768.1	Mycobacterium tuberculosis KZN 4207	4,394,985	tuberculosis8
	NC 016934.1	Mycobacterium tuberculosis UT205	4,418,088	tuberculosis9
	NC 017522.1	Mycobacterium tuberculosis CCDC5180	4,405,981	tuberculosis10
	NC 017524.1	Mycobacterium tuberculosis CTRI-2	4,398,525	tuberculosis11
	NC 018078.1	Mycobacterium tuberculosis KZN 605	4,399,120	tuberculosis12
	NC 018143.2	Mycobacterium tuberculosis H37Rv	4,411,709	tuberculosis13
	NC 020089.1	Mycobacterium tuberculosis 7199-99	4,421,197	tuberculosis14
	NC 020559.1	Mycobacterium tuberculosis str. Erdman = ATCC 35801 DNA	4,392,353	tuberculosis15
	NC 021054.1	Mycobacterium tuberculosis str. Beijing/NITR203	4,411,128	tuberculosis16
	NC 021194.1	Mycobacterium tuberculosis EAI5/NITR206	4,390,306	tuberculosis17
	NC 021251.1	Mycobacterium tuberculosis CCDC5079	4,414,325	tuberculosis18
	NC 021740.1	Mycobacterium tuberculosis EAI5	4,391,174	tuberculosis19
	NC 022350.1	Mycobacterium tuberculosis str	4,408,224	tuberculosis20
	NZ AP014573.1	Mycobacterium tuberculosis str. Kurono DNA	4,415,078	tuberculosis21
	NZ CP002871.1	Mycobacterium tuberculosis HKBS1	4,407,929	tuberculosis22
	NZ CP002882.1	Mycobacterium tuberculosis BT2	4,401,899	tuberculosis23
	NZ CP002883.1	Mycobacterium tuberculosis BT1	4,399,405	tuberculosis24
	NZ CP002885.1	Mycobacterium tuberculosis CCDC5180	4,414,346	tuberculosis25
	NZ CP007027.1	Mycobacterium tuberculosis H37RvSiena	4,410,911	tuberculosis26
	NZ CP007803.1	Mycobacterium tuberculosis K	4,385,518	tuberculosis27
	NZ CP007809.1	Mycobacterium tuberculosis strain KIT87190	4,410,788	tuberculosis28
	NZ CP009100.1	Mycobacterium tuberculosis strain ZMC13-264	4,411,507	tuberculosis29
	NZ CP009101.1	Mycobacterium tuberculosis strain ZMC13-88	4,411,515	tuberculosis30
	NZ CP009426.1	Mycobacterium tuberculosis strain 96075	4,379,376	tuberculosis31
	NZ CP009427.1	Mycobacterium tuberculosis strain 96121	4,410,945	tuberculosis32
	NZ CP009480.1	Mycobacterium tuberculosis H37Rv	4,396,119	tuberculosis33
	NZ CP010330.1	Mycobacterium tuberculosis strain F28	4,421,903	tuberculosis34
	NZ CP010337.1	Mycobacterium tuberculosis strain 22115	4,401,829	tuberculosis35
	NZ CP010338.1	Mycobacterium tuberculosis strain 37004	4,417,090	tuberculosis36
	NZ CP010339.1	Mycobacterium tuberculosis strain 22103	4,399,422	tuberculosis37
	CP010340.1	Mycobacterium tuberculosis strain 26105	4,426,489	tuberculosis38
	NZ CP012090.1	Mycobacterium tuberculosis W-148	4,418,548	tuberculosis39
	NZ CP012506.1	Mycobacterium tuberculosis strain SCAID 187.0	4,379,515	tuberculosis40
	NZ HG813240.1	Mycobacterium tuberculosis 49-02	4,412,379	tuberculosis41
	CP010329.1	Mycobacterium tuberculosis strain F1	4,428,621	tuberculosis42
	NC 015758.1	Mycobacterium africanum GM041182	4,389,314	africanum1
	CP010334.1	Mycobacterium africanum strain 25	4,386,422	africanum0
	CP010333.1	Mycobacterium microti strain 12	4,370,115	microti
	NC 015848.1	Mycobacterium canettii CIPT 140010059	4,482,059	canettii0
	NC 019951.1	Mycobacterium canettii CIPT 140070010	4,525,948	canettii1
	NC 019950.1	Mycobacterium canettii CIPT 140060008	4,432,426	canettii2
	NC 019952.1	Mycobacterium canettii CIPT 140070017	4,524,466	canettii3
	NC 019965.1	Mycobacterium canettii CIPT 140070008	4,420,197	canettii4
	NC 002945.3	Mycobacterium bovis AF2122/97	4,345,492	bovis0
	NC 008769.1	Mycobacterium bovis BCG Pasteur 1173P2	4,374,522	bovis1
	NC 012207.1	Mycobacterium bovis BCG str. Tokyo 172 DNA	4,371,711	bovis2
	NZ CP003494.1	Mycobacterium bovis BCG str. ATCC 35743	4,334,064	bovis3
	NC 016804.1	Mycobacterium bovis BCG str. Mexico	4,350,386	bovis4
	NC 020245.2	Mycobacterium bovis BCG str. Korea 1168P	4,376,711	bovis5
	NZ CP009449.1	Mycobacterium bovis strain ATCC BAA-935	4,358,088	bovis6
	NZ AM412059.1	Mycobacterium bovis BCG str. Moreau RDJ	4,340,116	bovis7
	NZ CP008744.1	Mycobacterium bovis BCG strain 3281	4,410,431	bovis8
	NZ CP012095.1	Mycobacterium bovis strain 1595	4,351,712	bovis9
	NZ CP009243.1	Mycobacterium bovis BCG strain Russia 368	4,370,138	bovis10
	NZ CP013741.1	Mycobacterium bovis strain BCG-1 (Russia)	4,370,705	bovis11
	CP010331.1	Mycobacterium bovis BCG strain 26	4,351,313	bovis12
	CP010332.1	Mycobacterium bovis strain 30	4,336,227	bovis13
	NZ CP014566.1	Mycobacterium bovis BCG str. Tokyo 172 substrain TRCS	4,371,707	bovis14

Table 2 Single nucleotide polymorphism between species (100.X is the name of an ancestral species, cf. the phylogeny)

 2

		canettii0	canettii1	canettii2	canettii3	canettii4	tuberculosis1
	tuberculosis1	3354	1150	27437	61346	7510	0
	canettii4	4833	7971	27468	60987	0	7510
	canettii3	60957	61233	62717	0	60987	61346
	canettii2	27256	27260	0	62717	27468	27437
	canettii1	3524	0	27260	61233	7971	1150
	canettii0	0	3524	27256	60957	4833	3354

Table 3 Number of columns of the MSA with SPNs or indels for M. canettii (large deletions are counted character by character).

 3

		Chromosome 1 SNPs
	Fathers	Children	No. of SNPs
	100.4	100.3 melitensis1	64 74
	100.2	melitensis3 melitensis2	106 8
	100.X	100.5 melitensis0	4458 104
	100	melitensis6 melitensis5	840 997
	100.5	100 100.4	372 689
	100.3	100.2 melitensis7	23 26

Table 6 Single nucleotide polymorphism in Brucella melitensis

 6

	Accession (GenBank)	Organism name	Sequence length(bp)	Nickname
	NC 006932.1 NC 006933.1	Brucella abortus biovar 1 str. 9-941 chromosome 1 Brucella abortus biovar 1 str. 9-941 chromosome 2	2,124,241 1,162,04	abortus0
	NC 010742.1 NC 010740.1	Brucella abortus S19 chromosome 1 Brucella abortus S19 chromosome 2	2,122,487 1,161,449	abortus1
	NC 016795.1 NC 016777.1	Brucella abortus A13334 chromosome 1 Brucella abortus A13334 chromosome 2	2,123,773 1,162,259	abortus2
	NZ CP007663.1 NZ CP007662.1	Brucella abortus strain 63 75 chromosome 1 Brucella abortus strain 63 75 chromosome 2	2,124,677 1,155,633	abortus3
	NZ CP007681.1 NZ CP007680.1	Brucella abortus strain BDW chromosome 1 Brucella abortus strain BDW chromosome 2	2,128,683 1,160,817	abortus4
	NZ CP007682.1 NZ CP007683.1	Brucella abortus strain BER chromosome 1 Brucella abortus strain BER chromosome 2	2,125,180 1,163,338	abortus5
	NZ CP007700.1 NZ CP007701.1	Brucella abortus strain NCTC 10505 chromosome 1 Brucella abortus strain NCTC 10505 chromosome 2	2,123,620 1,161,669	abortus6
	NZ CP007705.1 NZ CP007706.1	Brucella abortus bv. 9 str. C68 chromosome 1 Brucella abortus bv. 9 str. C68 chromosome 2	2,124,100 1,155,846	abortus7
	NZ CP007709.1 NZ CP007710.1	Brucella abortus bv. 6 str. 870 chromosome 1 Brucella abortus bv. 6 str. 870 chromosome 2	2,124,096 1,157,058	abortus8
	NZ CP007738.1 NZ CP007737.1	Brucella abortus strain BFY chromosome 1 Brucella abortus strain BFY chromosome 2	2,124,832 1,1633,26	abortus9
	NZ CP007765.1 NZ CP007764.1	Brucella abortus bv. 2 str. 86/8/59 chromosome 1 Brucella abortus bv. 2 str. 86/8/59 chromosome 2	2,123,991 1,162,137	abortus10
	NZ CP008774.1 NZ CP008775.1	Brucella abortus strain BAB8416 chromosome 1 Brucella abortus strain BAB8416 chromosome 2	2,116990 1,156,120	abortus11
	NZ CP009626.1 NZ CP009625.1	Brucella abortus 104M chromosome 2 Brucella abortus 104M chromosome 1	1,162,580 2,122,847	abortus12
	NZ LN997863.1 NZ LN997864.1	Brucella sp. F60 genome assembly BVF60 chromosome 1 Brucella sp. F60 genome assembly BVF60 chromosome 2	2,177,010 1,061,127	sp
	NZ CP007759.1 NZ CP007758.1	Brucella canis strain RM6/66 chromosome 2 Brucella canis strain RM6/66 chromosome 1	1,206,801 2,105,950	canis3
	NC 010103.1 NC 010104.1	Brucella canis ATCC 23365 chromosome 1 Brucella canis ATCC 23365 chromosome 2	2,105,69 1,206,800	canis0
	NC 016778.1 NC 016796.1	Brucella canis HSK A52141 chromosome 1 Brucella canis HSK A52141 chromosome 2	2,107,023 1,170,489	canis1
	NZ CP007629.1 NZ CP007630.1	Brucella canis strain SVA13 chromosome 1 Brucella canis strain SVA13 chromosome 2	2,106,955 1,203,360	canis2
	NC 022905.1 NC 022906.1	Brucella ceti TE10759-12 chromosome 1 Brucella ceti TE10759-12 chromosome 2	2,117,718 1,160,316	ceti
	NC 007618.1 NC 007624.1	Brucella melitensis biovar Abortus 2308 chromosome 1 Brucella melitensis biovar Abortus 2308 chromosome 2	2,121,359 1,156,948	melitensis0
	NZ CP008751.1 NZ CP008750.1	Brucella melitensis strain 20236 chromosome 2 Brucella melitensis strain 20236 chromosome 1	1,185,741 2,126,134	melitensis7
	NZ CP007762.1 NZ CP007763.1	Brucella melitensis bv. 1 str. 16M chromosome 2 Brucella melitensis bv. 1 str. 16M chromosome 1	1,177,791 2,116,984	melitensis6
	NZ CP007761.1 NZ CP007760.1	Brucella melitensis bv. 3 str. Ether chromosome 2 Brucella melitensis bv. 3 str. Ether chromosome 1	1,187,961 2,122,766	melitensis5
	NC 017283.1 NC 017248.1	Brucella melitensis NI chromosome 2 Brucella melitensis NI chromosome 1	1,176,758 2,117,717	melitensis4
	NC 017247.1 NC 017246.1	Brucella melitensis M5-90 chromosome 2 Brucella melitensis M5-90 chromosome 1	1,185,778 2,126,451	melitensis3
	NC 017245.1 NC 017244.1	Brucella melitensis M28 chromosome 2 Brucella melitensis M28 chromosome 1	1,185 615 2,126,133	melitensis2
	NC 012442.1 NC 012441.1	Brucella melitensis ATCC 23457 chromosome 2 Brucella melitensis ATCC 23457 chromosome 1	1,185,518 2,125,701	melitensis1
	NC 013119.1 NC 013118.1	Brucella microti CCM 4915 chromosome 1 Brucella microti CCM 4915 chromosome 2	2,117,050 1,220,319	microti
	NC 009505.1 NC 009504.1	Brucella ovis ATCC 25840 chromosome 1 Brucella ovis ATCC 25840 chromosome 2	2,111,370 1,164,220	ovis
	NC 015857.1 NC 015858.1	Brucella pinnipedialis B2/94 chromosome 1 Brucella pinnipedialis B2/94 chromosome 2	2,138,342 1,260,926	pinnipedialis0
	NZ CP007743.1 NZ CP007742.1	Brucella pinnipedialis strain 6/566 chromosome 1 Brucella pinnipedialis strain 6/566 chromosome 2	2,139,033 1,191,996	pinnipedialis1
	NZ CP010851.1 NZ CP010850.1	Brucella suis strain Human/AR/US/1981 chromosome 2 Brucella suis strain Human/AR/US/1981 chromosome 1	1,207,241 2,107,845	suis0
	CP009095.1 CP009094.1	Brucella suis strain ZW043 chromosome 2 Brucella suis strain ZW043 chromosome 1	1,215,956 2,224,908	suis1
	CP009097.1 CP009096.1	Brucella suis strain ZW046 chromosome 2 Brucella suis strain ZW046 chromosome 1	1,311,857 2,181,422	suis2
	NZ CP008756.1 NZ CP008757.1	Brucella suis strain BSP chromosome 2 Brucella suis strain BSP chromosome 1	1,410,995 1,902,870	suis3
	NZ CP007718.1 NZ CP007719.1	Brucella suis bv. 3 str. 686 chromosome 2 Brucella suis bv. 3 str. 686 chromosome 1	1,190,208 2,107,052	suis4
	NZ CP007716.1 NZ CP007717.1	Brucella suis strain 513UK chromosome 2 Brucella suis strain 513UK chromosome 1	1,187,980 2,131,717	suis5
	NZ CP007696.1 NZ CP007695.1	Brucella suis bv. 2 strain Bs143CITA chromosome 2 Brucella suis bv. 2 strain Bs143CITA chromosome 1	1,398,244 1,926,295	suis6
	NZ CP007721.1 NZ CP007720.1	Brucella suis bv. 2 strain Bs396CITA chromosome 2 Brucella suis bv. 2 strain Bs396CITA chromosome 1	1,401,375 1,927,083	suis7
	NZ CP007698.1 NZ CP007697.1	Brucella suis bv. 2 strain Bs364CITA chromosome 2 Brucella suis bv. 2 strain Bs364CITA chromosome 1	1,401,378 1,927,594	suis8
	NC 004310.3 NC 004311.2	Brucella suis 1330 chromosome 1 Brucella suis 1330 chromosome 2	2,107,794 1,207,381	suis9
	NC 010169.1 NC 010167.1	Brucella suis ATCC 23445 chromosome 1 Brucella suis ATCC 23445 chromosome 2	1,923,763 1,400,844	suis10
	NC 017251.1 NC 017250.1	Brucella suis 1330 chromosome 1 Brucella suis 1330 chromosome 2	2,107,783 1,207,380	suis11
	NC 016797.1 NC 016775.1	Brucella suis VBI22 chromosome 1 Brucella suis VBI22 chromosome 2	2,108,637 1,207,451	suis12
	NZ CP006961.1 NZ CP006962.1	Brucella suis bv. 1 str. S2 chromosome 1 Brucella suis bv. 1 str. S2 chromosome 2	2,107,842 1,207,433	suis13
	NZ CP007691.1 NZ CP007692.1	Brucella suis bv. 2 strain PT09143 chromosome 1 Brucella suis bv. 2 strain PT09143 chromosome 2	1,926,480 1,398,285	suis14
	NZ CP007693.1 NZ CP007694.1	Brucella suis bv. 2 strain PT09172 chromosome 1 Brucella suis bv. 2 strain PT09172 chromosome 2	1,926,716 1,398,326	suis15

Table 7 Brucella genus: genome information Chromosome 1 SNPs Chromosome 2 SNPs Fathers Children No. of SNPs Children No. of SNPs

 7

	100.2	abortus10	55	abortus10	41
		abortus0	72	abortus0	38
	100	abortus2	37	abortus2	25
		abortus1	55	abortus1	15
	100.3	100	37	100	17
		100.2	5	100.2	0
	100.X	100.3	24	100.3	15
		abortus4	84	abortus4	51

Table 8 Single nucleotide polymorphism in Brucella abortus.

 8

tuberculosis4

Funding

The publication costs of this article was funded by the University of Bourgogne Franche-Comté.

Availability of data and materials

The datasets supporting the conclusions of this article have been downloaded from the NCBI website https://www.ncbi.nlm.nih.gov. Scripts to download them automatically are available on demand.

Abbreviations

MTB

Competing interests

The authors declare no competing financial interests.

Ethics approval and consent to participate

No human, animal or plant experiments were performed in this study, and ethics committee approval was therefore not required.

Consent for publication

Informed consent has been obtained from all participants included in the analyzed studies, and the studies are being conducted in accordance with the declaration of Helsinki.

Authors' contributions

All authors have conceived and commented on the initial drafts of the manuscript and approved its final version. CG, BN, BA, JFC, and MS designed and performed experiments, analysed data and wrote the paper. All authors have read and approved the final manuscript.

Author details


Svenja Hermann

Dr Laure Arbenz

Christophe Espanet

Prof Christophe Espanet

About the use of magnetically hard flexible membranes for tactile interfaces

published or not. The documents may come

About the use of magnetically hard flexible membranes for tactile interfaces

Introduction

During the last years, machines have become an integral part of our lives. Consequently there has been an increase of attention given to the subject "Human Machine Interface" (HMI), inter alia containing tactile interfaces. The existing functional principles of tactile interfaces are mostly susceptible to humidity and can be used only with bare hands (resistive, capacitive) or are quite costly (NFI) and offer only optical feedbacks. The introduction of flexible magnetic material to the technical domain of tactile interfaces offers an alternative functional principle that can overcome these deficiencies.

Physical effect

The possibility of using composite membranes for tactile interfaces is based on the material's composition. Rare earth magnetic material particles of NdFeB are dispersed in a silicone membrane. The composite is magnetized in the direction perpendicular to its surface and, as a result, possesses a magnetic field. The flexibility of the hyperplastic material enables a change of the form of the membrane easily. A consequence of this change in form is a change of magnetic field created by the membrane (Figure 1). The membrane represents a passive primary sensor: without an external energy supply it is capable of creating different information which can be captured by a secondary sensor.

Development of a prototype

To demonstrate the usability of this effect in a device, a prototype of a tactile interface was developed. On the membrane's surface, a square was divided in 9 regions comparable to a 9 key keyboard (Figure 3). The prototype is expected to recognize the region in which the membrane is deformed by the user.

Numerical simulations of the membranes behavior concerning the magnetic and mechanical domain have been performed for a circular shaped membrane. It was deformed at three different positions and the changes in magnetic field were evaluated in a plane parallel to the membrane at a fixed distance. Simulations show, that the magnitude of the magnetic field decreases at the position where the membrane is deformed. In an experimental study, the cases of numerical simulation were reconstructed and confirmed the tendencies of the simulations as shown in Figure 2.. In order to reduce the number of secondary sensors in the prototype, the spatial components of the magnetic field have been analyzed. By using a unidirectional magnetic field sensor placed between two regions (Figure 3) the change in magnetic field takes place in opposite directions. According to an optimization process that was used to find the smallest possible number of secondary sensors, not more than five magnetic field sensors have to be used to assign a deformation to one of the 9 regions.

Conclusion and Perspectives

The possibility of using magnetic composite membranes for tactile interfaces has been demonstrated. The next steps are on the one hand the improvement of the secondary sensor aiming a completely self-sufficient generation of information by the help of electromagnetic induction. On the other hand, the possibility to give tactile feedback to the user by actuation the membrane will be studied.

Figure 1 :

 1 Figure 1: Functional principle

Figure 2 :

 2 Figure 2: Scheme of the deformation of a membrane at different positions and experimental results

Figure 3 :

 3 Figure 3: Regions to distinguish on the membranes surface and experimental result for one position of a sensor sensible in y-direction

Figure 4 :

 4 Figure 4: Exploded view of the prototype

Figure 6 :

 6 Figure 6: Working principle of the prototype


Amir Mujkanovic

Andreas Bollin
email: andreas.bollin@aau.at

Personality-Based Group Formation

Keywords: Software engineering, systematic group formation, improving group outcomes

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A winning team is required in almost any business and engineering discipline to achieve quality results such as, for example, the development of a product or the delivery of a service to clients. One can argue that every team within a company has to be successful in achieving their goals and many experts confirm that the composition of the team is the key to success. Examples of group types include business teams which might exist to generate financial profit, project teams which might exist to achieve certain project goals, club teams which might exist to have fun, families which might exist for reproduction purposes or educational groups which might exist to achieve certain learning outcomes. Panitz [START_REF] Panitz | The case for student centered instruction via collaborative learning paradigms[END_REF] points out a number of benefits that result from collaborative work in educational settings. These benefits include academic, social and psychological aspects which have been discussed in detail by Mujkanovic and Bollin [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF] and by Mujkanovic et al. [START_REF] Mujkanovic | Adaptive group formation to promote desired behaviours[END_REF]. Groups generally exist for a particular reason and they typically target one or multiple outcomes [START_REF] Donelson | Group Dynamics[END_REF].

A systematic and thorough construction of groups is a very demanding challenge, especially in composing the group members in a way that the intended group outcomes can be improved [START_REF] Cole | Organisational Behaviour[END_REF]. Many factors will have an impact on these outcomes, including the context in which the group activity takes place, the individual characteristics, the individual behaviour and the group composition. The meaning of these factors will be fully discussed in section 2.1.

The composition of groups plays a significant role in achieving the outcomes, but we still do not know much about the strength of this influence. Therefore, this research assesses the extent to which a systematic formation of software engineering groups affects the outcomes of these groups. Specifically, we aim at assessing the extent to which group outcomes can be improved through systematic reformation of groups during an ongoing lecture. Additionally, we are interested in the extent to which the outcomes of a lecture can be improved through a systematic reformation of groups.

This paper presents the results of an examination of data that have been collected over more than 10 years, involving randomly formed and systematically formed groups. The systematic formation is based on personality types and skills of each participants. The results show an improvement in the group outcomes when groups were systematically formed.

We commence with reviewing and studying the existing literature in section 2. Section 3 discusses the approach that has been taken to address the hypothesis and the subsequent research questions. Section 4 presents the findings of this research. Threats to validity will be discussed in section 5, and conclusions and further work will be addressed in section 6.

Background

There are important terms that will be used throughout this paper. It is therefore important to clarify the meaning of these terms. Individual characteristics are observable traits that can be used to differentiate between individuals. These traits exist independently of a human's behaviour and include cognitive and physical abilities, cultural values, personality traits, etc. Examples of individual characteristics include the age, the level of knowledge or the intelligence quotient of an individual. Individual behaviours are the actions of an individual within the context established by a particular task occurring within a particular environment. Examples include the level and diversity of chat dialogue that occurs between group members or potentially the number and nature of requests for assistance, etc. Context is the environment in which group activities take place. Group outcomes is the evaluation criterion that is defined to assess the group results. The group composition is a systematic arrangement of group members with certain personalities and skills which will contribute towards achieving the group outcomes.

In the following, we now briefly summarise related work in respect to group formation, project-based learning and the five-factor model, before presenting the research objectives that are covered by our study.

Many researchers [6 -8] have studied the group formation problem. An overview is given by Magnisalis [START_REF] Magnisalis | Adaptive and Intelligent Systems for Collaborative Learning Support: A Review of the Field[END_REF], in which the approaches to group formation have been summarised and clustered by the methods used to form these groups. Various approaches have used clustering techniques [START_REF] Zakrzewska | Cluster Analysis in Personalized E-Learning[END_REF], fuzzy and genetic algorithms [START_REF] Crespo | An algorithm for peer review matching using student profiles based on fuzzy classification and genetic algorithms[END_REF] and hidden Markov models, as well as approaches that used learning styles of students.

Graf and Bekele [START_REF] Graf | Forming Heterogeneous Groups for Intelligent Collaborative Learning Systems with Ant Colony Optimization[END_REF] point out the importance of collaborative learning and the group formation process. They address the formation of heterogeneous groups that is defined as the level of diversity of achievements within the groups. The heterogeneity is measured by the Euclidean distance between the attributes of group members. Ant colony optimisation is applied to improve the "goodness of the heterogeneity" of groups. Their research addresses the problem of the famous travelling salesman that is often discussed in literature on optimisation problems. Students are represented as nodes and the travelling salesman optimisation is applied to find the closest students and create groups. The evaluation of this approach has been made through a study that involved 512 students. The authors show also the scalability of their proposed method and the application to the real world. While their work uses sophisticated artificial intelligence methods to address an important problem and improve the group formation process, it does not consider the formation of homogeneous groups. The focus of their research seems to be the quality of the group formation process itself [START_REF] Graf | Forming Heterogeneous Groups for Intelligent Collaborative Learning Systems with Ant Colony Optimization[END_REF].

We are not aware of any existing research that has used personality types and skills for the systematic reformation of groups during an ongoing software project management course and a project-based learning scenario. Our approach uses a simple and scalable group formation model with focus on systematic group reformation within a well-established simulation environment called AMEISE. The reasons for using the AMEISE framework in our research include a high standard of the lecture's content that has not changed much over the past few years, as well as the nature of the lecture in which student groups perform two simulations. This provides a perfect context to test our hypothesis with random groups (1 st simulation) and systematically formed groups (2 nd simulation). Another reason that make the AMEISE a perfect environment for our research is the very stable assessment scheme of the entire lecture. More information on the AMEISE simulation framework and a justification for using this framework for this research can be foundin a previous paper [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF].

Concerning project-based learning, there are countless reasons for its importance for student careers. Krajcik and Blumenfeld [START_REF] Krajcik | Project-Based Learning[END_REF] give an overview on the key elements that should be considered in project-based learning environments. These elements include: (1) a formulation of the key questions and hence a problem that has to be solved; (2) students tackle the problem by engaging in real problem-solving processes that are essential to expert work in the field; (3) teaching staff and fellow students including the community begin to engage in collaborative activities and support the project team; and (4) students develop a set of outcomes that represent the learning outcomes of the lecture. In project-based learning, students solve real-world problems and gain knowledge and skills and they also reflect on their skills and their personality [START_REF] Graham | UK Approaches to Engineering Project-Based Learning[END_REF]. To test our hypothesis, it is required to categorise individuals into different personalities. One way is using the Five-Factor Model. Salleh et al. [START_REF] Salleh | An empirical study of the effects of personality in pair programming using the five-factor model[END_REF] and Yamada et al. [START_REF] Yamada | The impacts of personal characteristic on educational effectiveness in controlled-project based learning on software intensive systems development[END_REF] confirm that the personality has an impact on students' performances. They used the Five Factor Model (Extroversion, Agreeableness, Consciousness, Neuroticism, Openness) to assess the impact of personality on the outcomes. Salleh et al. found out that consciousness and openness had an impact on the performances of students. Yamada et al. suggest constructing the groups with members with different individual characteristics. Another study by Alfonseca et al. [START_REF] Alfonseca | The impact of learning styles on student grouping for collaborative learning: a case study[END_REF] found that certain learning styles impact on student performances and that collaborative learning might be improved through systematic formation of groups. Systematic group formation is exactly the core of this research, which aims at improving group outcomes.

In an initial study [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF], we assessed the impact of the findings by other researchers [START_REF] Salleh | An empirical study of the effects of personality in pair programming using the five-factor model[END_REF][START_REF] Yamada | The impacts of personal characteristic on educational effectiveness in controlled-project based learning on software intensive systems development[END_REF] in our context. As the results of our initial study provided promising results that supported our hypothesis, we felt strengthened to use these results for further studies. The learnings from existing work and our own examinations were applied to our group outcomes model. Initial studies [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF] introduced the group outcome model where various factors that impact on these group outcomes had been discussed. This group outcome model had been further developed and includes now also the Five-Factor-Model (as represented in the top left in Figure 1), using individual characteristics to obtain the personality types of each individual. These personality types are then used to compose the groups in a way that the desired group outcomes will be more likely.

To our knowledge, there has been no consideration of how groups might be reorganised during a lecture to improve learning outcomes. We have therefore formulated the following hypothesis and research questions that will address this research opportunity: Hypothesis: By systematically reconstructing groups of students it is possible to enhance their outcomes and improve the individual performances and therefore raise the outcome level of the software engineering lecture.

Research question RQ1:

To what extent is it possible to improve the group outcomes by systematically reorganising the student groups? Research question RQ2: To what extent is it possible to improve the outcomes and raise the total outcomes of the lecture by reorganising the student groups?

Methodological approach

The methodological approach was adapted from an initial pilot study in 2015 and was further developed through feedback of the pilot study [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF]. Before we start discussing the details, it is useful to explain the structure of the experiment and the overall approach, which has been conducted in its two major phases. In the first phase, participants of the study performed an assignment during a software project management course using the AMEISE simulation framework that provided empirically validated and quantitative data for grading. In the second phase, participants of the study were systematically placed into groups of four different cohorts aiming at addressing our hypothesis and improving their outcomes through rigorous and systematic reformation of the project groups. After both phases, the atmosphere was observed through a pre-test (after phase 1 means prior to systematic group formation) and a post-test (after phase 2 means after systematic group formation) to capture any circumstances (e.g. conflicts between group members) which might have had an impact on the outcomes. The participants were split into four different student cohorts that were systematically constructed depending on their personality and results of the first simulation run. These cohorts included a random cohort (RG), a cohort (MC) that included at least one manager or coach per group as recommended by Sunaga et al. [START_REF] Sunaga | Relation between Combinations of Personal Characteristic Types and Educational Effectiveness for Controlled Project-based Learning Course[END_REF], a cohort of students that achieved best results in phase 1 (UC), and a cohort that included at least one analyst or renovator per group (AR). No roles were assigned to the students (so, only personality traits were used to form the groups). Results from both phases were then compared to examine whether the results could be improved through systematic formation of groups.

The students at both institutions were used to working together in different team constellations (even though they preferred to work with colleagues they knew), and then, from a student's perspective, they were randomly assigned, as explained before. All students were informed that they were taking part in an experiment, and surveys at the end of the course showed that they were satisfied with their group re-formation.

RQ1 was addressed by comparing the results of phase one (randomly formed groups) and phase 2 (systematically formed groups). These results are fully discussed in section 4. RQ 2 was assessed by analysing the grades and historical data that was available for all the courses that used the AMEISE environment to teach software project management between 2006 and 2016. The group outcome (grade) is a weighted composite of a number of factors that were kept the same in both phases (for more details, see a previous paper [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF]). Both research questions are addressed in the largescale study reported here, designed and conducted at the University of Klagenfurt and the Technical University of Košice in 2016.

To address both research questions, two separate examinations were carried out. Research question one was addressed by analysing the results of the experiment as described above. During both phases, participants conducted a full AMEISE simulation which was assessed at the end of the course. A total number of 69 groups completed a software project management assignment and each group received grades on a scale between 1.0 and 5.0 (1=excellent, 2=good, 3=passed, 4=satisfactory, 5=fail). The data collection process and determination of individual characteristics (skills and personality) remained the same as in our pilot study [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF].

RQ2 was addressed by examining historical data of 2,397 software engineering students (961 groups) enrolled in a software engineering course at the Alpen-Adria University of Klagenfurt (59 groups) and the Technical University of Košice in Slovakia (532 groups) over an observation period of 12 years. The remaining 370 groups were enrolled in the same course at other institutions. The students worked on their assignment mostly in pairs and triads, and in Klagenfurt some of the students had, due to their software engineering focus, a slightly higher previous knowledge in project management. During the experiments, when systematic group formation had been applied, students only knew that they were being part of a scientific experiment, but they did not know any details about the experiment.

Results

RQ1 examines the extent to which the groups' outcomes can be improved by systematically reorganising the student groups during a software project management course. Figure 2(a) depicts at the left the group grades in phase one, in which groups were randomly formed, as well as the grades of all groups in phase two (the right boxplot) that were systematically formed. The AMEISE framework determines several performance measures which are automatically transformed into grades. This scheme is a well-established assessment method that has been used for ten years. As a result of our large-scale study, the average group outcomes improved from 3.2 to 2.32, which is an improvement of approximately 27.5 % on average. A comparison of the means through a t-test using the MATLAB function ttest2 returns additional insight. The h and p values (representing the test for the null hypothesis) returns h=1 and p<0.0001 which tells that our null hypothesis can be rejected at a significance level of 0.0001.

The median of achieved grades in phase one is 3.25. The 75% percentile is 3.7 and the upper adjacent (lowest grade) is 4.7. The 25% quartile is 2.7. The best grade achieved is 1.6. Half of the data (inter-quartile range) lie between grades 2.7 and 3.25.

In phase two, where systematic formation of groups was applied, the grades were improved. Figure 2 (a) shows at the right the grades achieved in phase two. The median lies at 2.35. The 75% quartile is at 2.9 and the maximum at 4.1, which is the lowest grade achieved by a group. The 25% quartile is at 1.75 and the lowest value (best grade) is exactly 1. Half of the data lie between 1.75 and 2.7. From these two box plots, it can be seen that in phase two, when the systematic formation of groups has been applied, the notches do not overlap with the notches of the results in phase 1. Krzywinski and Altman [START_REF] Krzywinski | Points of Significance: Visualizing samples with box plots[END_REF] confirm the medians differ significantly when notches do not overlapsupporting our hypothesis.

Figure 3 presents the distribution of the group grades in both. These grades were gathered from the AMEISE simulation framework with possible values between 1.0 and 5.0. Considering the histogram of random groups, it is obvious that this graph represents a unimodal (one peak) distribution with no outliers that is skewed left. We have a concentration of the grades among the lower grades, with a small number of good grades (2, meaning "good" on the Austrian grade scale) and no excellent grade. The centre of the distribution is around the average grade 3.2. The minimum value, which is the best grade achieved, is 1.6 and the highest value that represents the lowest grade is at 4.7. This represents a range of grades from 1.6 to 4.7 which is a range of 3.1. Now considering the distribution of the group grades when we applied our methodology of systematic formation of groups, we can report an improvement of the grades. The shape of the distribution is still a unimodal distribution that has changed the skew towards the right. The centre of the distribution is located around the average group grade 2.3. The minimum value is 1.00, which is the highest possible grade, and the maximum value is at 4.1. The range of grades remained the same (as in phase one where groups had been randomly formed); however, as the minimum and maximum values represent, we can report a shift of the mean to the right. RQ2 examines the extent to which the results of the software project management course can be improved by systematically constructing the groups. To assess this issue, it is useful to consider historical data from the past years of the same course. Figure 2(b) presents the achievements of groups between 2006 and 2016, when random group and self-assigned formation had been applied, as well as the results of studies when systematic group formation had been applied in 2015 [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF] and 2016.

The lower adjacent of the results between 2006 and 2016, and therefore the best grade achieved, is a 1, which corresponds to an excellent grade. The upper adjacent, and therefore the lowest grade achieved, is a 5, which corresponds to a fail. The 75% percentile is at 3.65 and the median is at 2.75. The lower and upper limits of the notch are about 2.62 and 2.87. The 25% percentile is at 1.95. The inter-quartile range lies between the grades 1.9 and 3.65.

The lower adjacent of the results in 2015, and therefore the best grade achieved, is a 1.4, which corresponds to an excellent grade. The upper adjacent, and therefore the lowest grade achieved, is 3.8, which corresponds to a satisfactory grade. The 75% percentile is at 2.55 and the median is at 2.13. The lower and upper limits of the notch are about 1.84 and 2.4. The 25% percentile is at 1.7. The inter-quartile range lies between the grades 1.7 and 2.55.

The lower adjacent of the results in 2016, and therefore the best grade achieved, is 1, which corresponds to an excellent grade. The upper adjacent, and therefore the lowest grade achieved, is 4.1, which corresponds to a satisfactory grade. The 75% percentile is at 2.9 and the median is at 2.35. The lower and upper limits of the notch are about 2.13 and 2.56. The 25% percentile is at 1.75. The inter-quartile range lies between the grades 1.75 and 2.9. It is worthwhile mentioning that during the study in 2016 a new teaching staff (therefore with little experience) prepared the simulations in AMEISE, which might have had an impact on the overall results.

Comparing both results from our initial study in 2015 and the large-scale study in 2016 with the data of the past 10 years, there has been an improvement of the outcomes when systematic group formation has been applied. A comparison of the historical data of 12 years (the left box plot in Figure 2 (b)) and the results of the study in 2016 (the right box plot in Figure 2 (b)) through a t-test returns h=1 and p=0.0028, which is evidence that our results can be claimed as statistically significant.

Threats to validity

Validity considers the entire scientific experiment and examines whether the findings meet the requirements of the scientific method. Before we discuss the details of validity issues, it is worthwhile mentioning that we kept everything the same between the pilot study in 2015 [START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF] and the study that examined research question one in this paper. The subject was taught by the same academic staff, with an additional teacher in 2016. Also, the course material including the assignments remained the same.

Internal validity focuses on the examination if each and every step of the experiment follows the scientific method and whether other factors that have not been considered could have an impact on the results. External validity focuses on the generalisation of the results to other settings and to other populations.

Internal validity might be affected by the nature of the experiment, as involving humans in research studies is a known challenge and we are aware that capturing individual characteristics through a survey may not accurately represent the skills and personality types of each participant, especially when the characteristics are selfperceived. An idea that might provide more accurate individual characteristics could be a system that collects data of how people perceive others when they interact with each other. Such a system would enable additional individual characteristics that are not self-perceived. However, as we have approximately 2,400 students that were included in our study, we are confident that most students respond carefully and honestly to the personality tests.

The experiment has been set up in two different phases; there is a possibility that the improvement of grades has been achieved through a learning effect. However, if the results have been biased by a learning effect, then this learning effect has influenced all participating groups on average. Therefore, a possible learning effect can be seen as irrelevant. An additional issue might be given by the diversity of students' previous knowledge. Even if they undergo the same curricula, their previous background and therefore their skills might have camouflaged impact on our findings.

External validity is certainly an issue of these finding as it cannot be assumed that these findings can be applied to other settings with a guarantee to achieve the same results. The settings that have been chosen for our work include two different cultural environments, one at the Alpen-Adria University of Klagenfurt in Austria and the second at the Technical University of Košice in Slovakia.

Conclusion and further work

The work presented in this paper intended to test our hypothesis and to assess the extent to which group outcomes can be improved by systematically re-organising the student groups during a software project management course. The hypothesis has been decomposed into two core research questions which have been addressed separately. The findings of both research questions provide results in favour of our hypothesis and therefore contribute to the body of knowledge.

Research question one considered the improvements of grades by systematically reorganising the student groups. The findings suggest that there is a statistically significant improvement of group outcomes by 27.5% when they are rigorously and systematically constructed. Research question two considered the improvements of the software project management course through a systematic formation of project groups. A comparison of data over ten years showed that the results were significantly improved on average by 14.6% when systematic formation of groups was applied. The performance increase is based on simple methods and two central questions in the Five Factor Model, rather than on complicated artificial intelligence methods.

These findings are promising, as they provide evidence that a systematic formation of groups might enable business leaders and educators to systematically form their teams, especially in highly technical environments, and therefore improve the key performance indicators of their business.

Teaching staff could systematically form groups of students across different school levels and therefore increase the learning outcomes of students. A transfer of these results and further studies in various schools, as well as in semiconductor industry, will be subject to further work.

Figure 1 .

 1 Figure1. Group outcome model: Factors that have an impact on group outcomes[START_REF] Mujkanovic | Improving Learning Outcomes Through Systematic Group Reformation: The Role of Skills and Personality in Software Engineering Education[END_REF]

Figure 2 .

 2 (a) Box plot of the group outcomes of randomly formed groups in phase 1 (to the left, n = 69 groups) and systematically formed groups in phase 2 (to the right, n = 69 groups) and 140 individuals. (b) Box plot of grades achieved in software project management lectures at the University of Klagenfurt using AMEISE between 2006 and 2016 (left, n=666) and 2015 (middle, n=22) and in 2016 (right, n=69).

Figure 3 .

 3 Figure 3. Distribution of the outcomes of randomly formed groups from the different phases.