Charles Guyon

Thierry Bouwmans
email: thierry.bouwmans@univ-lr.fr

El-Hadi Zahzah

Foreground Detection via Robust Low Rank Matrix Decomposition including spatio-temporal Constraint

Foreground detection is the first step in video surveillance system to detect moving objects. Robust Principal Components Analysis (RPCA) shows a nice framework to separate moving objects from the background. The background sequence is then modeled by a low rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers. In this paper, we propose to use a low-rank matrix factorization with IRLS scheme (Iteratively reweighted least squares) and to address in the minimization process the spatial connexity and the temporal sparseness of moving objects (e.g. outliers). Experimental results on the BMC 2012 datasets show the pertinence of the proposed approach.

Introduction

The detection of moving objects is the basic low-level operations in video analysis. This detection is usually done using foreground detection. This basic operation consists of separating the moving objects called "foreground" from the static information called "background". Recent research on robust PCA shows qualitative visual results with the background variations appromatively lying in a low dimension subspace, and the sparse part being the moving objects. First, Candes et al. [START_REF] Candes | Robust principal component analysis? International[END_REF] proposed a convex optimization problem to address the robust PCA problem. The observation matrix is assumed represented as: A = L + S where L is a low-rank matrix and S must be sparse matrix with a small fraction of nonzero entries. This research seeks to solve for L with the following optimization problem: min

L,S ||L|| * + λ||S|| 1 subj A = L + S (1)
where ||.|| * and ||.|| 1 are the nuclear norm (which is the L 1 norm of singular values) and l 1 norm, respectively, and λ > 0 is an arbitrary balanced parameter. Under these minimal assumptions, this approach called Principal Component Pursuit (PCP) solution perfectly recovers the low-rank and the sparse matrices.

In this paper, we propose a robust low-matrix factorization with IRLS scheme to adress the second limitation. For a data matrix A containing the sequence, we assume that a part is approximatively low-rank and product of two matrices, and a small part of this matrix is corrupted by the outliers. Furthermore, we directly introduced a spatial term in the l 1 minimization to address the spatial connexity of the pixels. So, our contributions can be summarized as follows: 1) Addition of spatial constraint to minimization process, 2) IRLS alternating scheme for weighted the 2-parameters ||.|| α,β for matrix low-rank decomposition. The rest of this paper is organized as follows. The Section 2 focus on IRLS method applied on vector regression problems. In Section 3, we present a robust low-rank matrix factorization which allows us to detect foreground objects in dynamic backgrounds. In Section 4, we present results on the BMC 2012 datasets1 and the Section 5 provides the conclusion.

L p Minimization with spatial constraint

In most applications, video surveillance data is assumed to be compose of background, foreground and noise. Regression task is a crucial part of the proposed decomposition algorithm. We consider the following minimization problem [START_REF] Osborne | Finite algorithms in optimization and data analysis[END_REF], where A is a dictionary matrix (row order) and b is a row vector, the second term forces the error E to be a connexe shape, through the TV (Total Variation) of the residual must be small, where the matrix ∇ s is a spatial gradient.

argmin x ||Ax -b|| α + λ||∇ s (Ax -b)|| 1 (2)
The left part of the problem (3) is convex for α > 1 and the usual IRLS (Iteratively reweighted least squares) scheme for solve argmin

x ||Ax -b|| α is given by

D (i) = diag((ε + |b -Ax (i) |) α-2 ) x (i+1) = (A t D (i) A) -1 A t D (i) b (3)
It was proven that a suitable IRLS method is convergent for 1 ≤ α < 3 [START_REF] Osborne | Finite algorithms in optimization and data analysis[END_REF]. Since if the process is expressed with a residual formulation, we gain more numericaly stability and let us to choose freely α ∈ [1, ∞[ with an adapted step size λ opt on every iteration.

r (i) = b -Ax (i) D = diag((ε + |r (i) |) α-2 ) y (i) = (A DA) -1 A Dr (i) x (i+1) = x (i) + (1 + λ opt )y (i) (4)
With a fixed λ opt , we should choose λ opt as developed [START_REF] Guyon | Foreground detection via robust low rank matrix factorization including spatial constraint with iterative reweighted regression[END_REF].

Otherwise, the algorithm is twice iterative, where we try to get an optimal x and an optimal λ at each step.

c (i) = Ay (i) d (i) = b -A(x (i) + y (i) ) argmin λ opt ||c (i) λ -d (i) ||α λ (0) = Λ(α) s (k) = d -λ (k) c E = diag((ε + |s (k) |) α-2 ) z (k) = c t Es (k) c t Ec λ (k+1) = λ (k) + (1 + Λ(α))z (k)
(5)

Only few iterations (≈ 10) is enough for acceptable approximation of λ opt of the λ (k) sequence. Moreover, the convergence is usually improved by a Aitken process or an other acceleration technique. Note for case α > 2, convergence is achieved when 0 < 1 + λ < 2 α-1 . Additionally, TV is particular case of the following problem:

argmin x ||Ax -b|| α + λ||Cx -d|| β (6)
By derivation, the associated IRLS scheme is,

r1 = b -Ax (i) , r2 = d -Cx (i) , e1 = ε + |r1|, e2 = ε + |r2| D1 = ( e α 1 ) 1 α -1 diag(e α-2 1
), D2 = λ( e β 2 )

1 β -1 diag(e β-2 2 ) y (i) = (A D1A + C D2C) -1 (A D1r1 + C D2r2) x (i+1) = x (i) + (1 + λopt)y (i) (7)
More generally, we consider the following matrix regression problem with two parameters norm (α, β) and a weighted matrix (W ), min

X ||AX -B|| α,β W with ||M ij || α,β W = ( n i=1 ( m j=1 W ij |M ij | β ) α β ) 1 α (8)
The problem is solved in the same manner on matrices with a reweighted regression strategy,

Until X is stable, repeat on each k-columns R ← B -AX S ← ε + |R| D k ← diag(S β-2 ik • ( j (S β ij • Wij)) α β -1 • W ik ) k X ik ← X ik +(1+Λ(max(α, β)))(A t D k A) -1 A t D k R ik (9)

Foreground Detection via Robust Low-Rank Matrix Factorization and temporal constraint

The training video sequence A ∈ R n×m is stored as a matrix with a particular structure. Columns are spatial frames and rows are values of a fixed pixel over time. For A = I 1 , . . . , I m , I j denotes a vectorized frame of n pixels at j-time with m is the number of frames. A y+hx,t implies the pixel intensity at coordinate Fig. 1. Overview of the learning and evaluation process. Learning process needs GT (Groundtruth) for better fits the eigenbackground components.

x, y, t. The background modeling process finds an ideal subspace of the video sequence, which describes the best as possible the (dynamic) background as shown in Fig. 2. Then, the decomposition involves the following model:

A = L + S = BC + S ( 10
)
where B is a low-rank matrix corresponding to the background model plus noise and C allows to approximate L by linear combination. S is a sparse matrix which corresponds to the foreground component obtained by subtraction. The model involves the error reconstruction determined by the following constraints:

min B∈R n×p ,C∈R p×m ||(A -BC) • W || α,β + µ||BC|| * (11)
where ||.|| * denote the nuclear norm. The decomposition is split into two parts. Firstly, we track 1-Rank decomposition since the first eigen-vector is strongly dominant in video surveillance. Furthermore, this norm enforce temporarily sparseness of outliers as shown in Fig. 4. In the case where α = β = 2, the decomposition is usually solved by a SVD (Singular Value Decomposition). Thus, our SVD algorithm can be seen as an iterative regression. The proposed scheme determines alternatively the optimal coefficients, it means searching C for B fixed and searching B for C fixed.

R 1 = A -B 1 C 1 min B1,C1 ||R 1 || 1,1 R = A -B 1 C 1 -B r C r min Br,Cr ||R • φ(R 1 )|| 2,1→0 (12)
C (k+1) = (A t A) -1 A t B (k) C(k+1) = C (k+1) √ C t(k+1) C (k+1) -1 B (k+1) = (A t A) -1 A t C(k+1) (13)
Additionnaly, this alternating regression framework allows to associate a weigthed matrix W which is entrywise multiplied to the error term,

min B,C ||(A -BC) • W || α,β (14)
The W mask is iteratively computed and aims to enforce the fit exclusively on guessed background region.

We define a function φ that have two goals, smooth the error (like spatial median filtering) and transform the error for obtain a suitable weighted mask for regression.

W = φ(|A -BC|) , φ(E) = e -γT V (E) (15)
By including local penalty as a constraint in RPCA, this explicitly increases local coherence of the sparse component as filled/plain shapes (therefore moving object).

Experimental Results

Here, we show experimental results on the real dataset of BMC,

Conclusion

In this paper, we have presented a robust matrix factorization for foreground detection. This method is conceptually simple, easy to implement and efficient. Furthermore, experiments on video surveillance datasets show that this approach is more robust than recent RPCA approaches in the presence of dynamic backgrounds and illumination changes. Further research consists in developping an incremental version to update the model at every frame and to achieve real-time requirements.

Fig. 2 .

 2 Fig. 2. At left: The common process of background subtraction via PCA (Principal Component Analysis). At final step, an adaptative threshold is used to get a binary result.

Fig. 3 .

 3 Fig. 3. At right: Using the previous decomposition on a low-rank random matrix plus noise, different kind of pattern on residual matrix emerge with the choice of the norm.

Fig. 4 .

 4 Fig. 4. At Left: Schema ofideal PCA processing. The eigenbackground are computed using a Weighted-PCA with GroundTruth.

Fig. 5 .

 5 Fig. 5. At right: First eigenBackground of the fifths sequence of Rotary (BMC) with the norms ||.||opt, ||.||1,1 and ||.||2,1. Last row shows eigenBackground on real dataset with ||.||2,1.

Table 1 .

 1 Quantitative results with common criterions. Last column show the original, GT and result of the first four real video sequences.

	Video Recall Precision F-measure PSNR	Visual Results
	1	0.9139	0.7170	0.8036	38.2425
	2	0.8785	0.8656	0.8720	26.7721
	3	0.9658	0.8120	0.8822	37.7053
	4	0.9550	0.7187	0.8202	39.3699
	5	0.9102	0.5589	0.6925	30.5876
	6	0.9002	0.7727	0.8316	29.9994
	7	0.9116	0.8401	0.8744	26.8350
	8	0.8651	0.6710	0.7558	30.5040
	9	0.9309	0.8239	0.8741	55.1163

http://bmc.univ-bpclermont.fr


Huda Al-Nayyef

Christophe Guyeux

Marie Petitjean

Didier Hocquet

Jacques M Bahi
email: jacques.bahi@univ-fcomte.frdhocquet@chu-besancon.fr

Relation between Insertion Sequences and Genome Rearrangements in Pseudomonas aeruginosa

Keywords: Rearrangements, Inversions, Insertion Sequences, Pseudomonas aeruginosa

During evolution of microorganisms genomes underwork have different changes in their lengths, gene orders, and gene contents. Investigating these structural rearrangements helps to understand how genomes have been modified over time. Some elements that play an important role in genome rearrangements are called insertion sequences (ISs), they are the simplest types of transposable elements (TEs) that widely spread within prokaryotic genomes. ISs can be defined as DNA segments that have the ability to move (cut and paste) themselves to another location within the same chromosome or not. Due to their ability to move around, they are often presented as responsible of some of these genomic recombination. Authors of this research work have regarded this claim, by checking if a relation between insertion sequences (ISs) and genome rearrangements can be found. To achieve this goal, a new pipeline that combines various tools has firstly been designed, for detecting the distribution of ORFs that belongs to each IS category. Secondly, links between these predicted ISs and observed rearrangements of two close genomes have been investigated, by seeing them with the naked eye, and by using computational approaches. The proposal has been tested on 18 complete bacterial genomes of Pseudomonas aeruginosa, leading to the conclusion that IS3 family of insertion sequences are related to genomic inversions.

Introduction

The study of genome rearrangements in microorganisms has become very important in computational biology and bio-informatics fields, owing to its applications in the evolution measurement of difference between species [START_REF] Chih | Spring: a tool for the analysis of genome rearrangement using reversals and block-interchanges[END_REF]. Important elements in understanding genome rearrangements during evolution are called transposable elements, which are DNA fragments or segments that have the ability to insert themselves into new chromosomal locations, and often make duplicate copies of themselves during transposition process [START_REF] Hawkins | Differential lineage-specific amplification of transposable elements is responsible for genome size variation in gossypium[END_REF]. Indeed, within bacterial species, only cut-and-paste of transposition mechanism can be found, the transposable elements involved in such way being the insertion sequences. These types of mobile genetic elements (MGEs) seem to play an essential role in genomes rearrangements and evolution of prokaryotic genomes [START_REF] Siguier | Insertion sequences in prokaryotic genomes[END_REF][START_REF] Bergman | Discovering and detecting transposable elements in genome sequences[END_REF]. In this research work, we questioned the relation between the movement of insertion sequences on the one hand, and genome rearrangements on the other hand, and tested whether the type of IS family influences this relation. Investigations will focus on inversion operations of rearrangement (let us recall that an inversion occurs within genomes when a chromosome breaks at two points, and when the segment flanked with these breakpoints is inserted again but in reversed order, this event being potentially mediated with molecular mechanisms [START_REF] Kirkpatrick | How and why chromosome inversions evolve[END_REF][START_REF] José M Ranz | Principles of genome evolution in the drosophila melanogaster species group[END_REF]). To achieve our goal, we built a pipeline system module that combines existing tools together with the development of new ones, for finding putative ISs and inversions within studied genomes. We will then use this system to investigate the structure of prokaryotic genomes, by searching for IS elements at the boundaries of each inversion.

The contributions of this article can be summarized as follows. (1) A pipeline for insertion sequences discovery and classification is proposed. It uses unannotated genomes and then combines different existing tools for ORF predictions and clustering. It also classifies them according to an international IS database specific to bacteria. Involved tools in this stage are, among others, Prodigal [START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF], Markov Cluster Process (MCL) [START_REF] Van Dongen | Graph clustering by flow simulation[END_REF], and ISFinder1 [START_REF] Siguier | Isfinder: the reference centre for bacterial insertion sequences[END_REF]. [START_REF] Hawkins | Differential lineage-specific amplification of transposable elements is responsible for genome size variation in gossypium[END_REF] We then use two dif-ferent strategies to check the relation between ISs and genomic rearrangements. The first one used a well-supported phylogenetic tree, then genomes of close isolates are drawn together, while the questioned relation is checked with naked eye. In the second strategy, inversion cases are thoroughly investigated with ad hoc computer programs. And (3), the pipeline is tested on the set of 18 complete genomes of Pseudomonas aeruginosa provided in Table 1. After having checked left and right inversion boundaries according to different window sizes, the probability of appearance of each type of IS family is then provided, and biological consequences are finally outlined.

The remainder of this article is organized as follows. The proposed pipeline for detecting insertion sequences in a list of ORFs extracted from unannotated genomes is detailed in Section 2. Rearrangements found using drawn genomes of close isolates is detailed in Section 3, while a computational method for discovering inversions within all 18 completed genomes of P. aeruginosa and results are provided in Section 3.2. This article ends by a conclusion section, in which the contributions are summarized and intended future work is detailed.

Methodology for IS detection

In a previous work [START_REF] Al-Nayyef | A pipeline for insertion sequence detection and study for bacterial genome[END_REF], we have constructed a pipeline system that combines three annotation tools (BASys [START_REF] Gary H Van Domselaar | Basys: a web server for automated bacterial genome annotation[END_REF], Prokka [START_REF] Seemann | Prokka: rapid prokaryotic genome annotation[END_REF], and Prodigal [START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF]) with OA-SIS [START_REF] David G Robinson | Oasis: an automated program for global investigation of bacterial and archaeal insertion sequences[END_REF], that detected IS elements within prokaryotic genomes. This pipeline produces various information about each predicted IS, each IS is bordered by an Inverted-Repeat (IR) sequence, number of ORFs in each IS family and group, etc. As we are now only interested in detecting which ORFs are insertion sequences, we have developed a new lightweight pipeline that focuses on such open reading frames.. This pipeline, depicted in Figure 1, relies on ISFinder database [START_REF] Siguier | Isfinder: the reference centre for bacterial insertion sequences[END_REF], the up-to-date reference for bacterial insertion sequences. The main function of this database is to assign IS names and to provide a focal point for a coherent nomenclature. This is also a repository for ISs that contains all information about insertion sequences such as family and group.

The proposed pipeline can be summarized as follows.

Step 1: ORF identification. Prodigal is used as annotation tool for predicting gene sequences. This tool is an accurate bacterial and archaeal gene finding software provided by the Oak Ridge National Laboratory [START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF]. Table 1 lists the number of the predicted genes in each genome.

Step 2: ORF clustering. The Markov Cluster Process (MCL) algorithm is then used to achieve clustering of detected ORFs [START_REF] Van Dongen | Graph clustering by flow simulation[END_REF][START_REF] Enright | An efficient algorithm for large-scale detection of protein families[END_REF].

Step 3: Clusters classification. The IS family and group of the centroid sequences of each cluster is determined with ISFinder database. BLASTN program is used here: if the e-value of the first hit is equal to 0, then the cluster of the associated sequence is called a "Real IS cluster". Otherwise, if the e-value is lower than 10 -8 , the cluster is denoted as "Partial IS". At each time, family and group names of ISs that best match the considered sequence are assigned to the associated cluster. In Table 2 summarizes founded IS clusters found in the 18 genomes of P. aeruginoza.

Rearrangements in Pseudomonas aeruginosa

At the nucleotide level, genomes evolve with point mutations and small insertions and deletions [START_REF] Garcia | Mechanism of a genetic glissando: structural biology of indel mutations[END_REF], while at genes level, larger modifications including duplication, deletion, or inversion, of a single gene or of a large DNA segment, affect genomes by large scale rearrangements [START_REF] Hurles | Gene duplication: the genomic trade in spare parts[END_REF][START_REF] Proost | i-adhore 3.0fast and sensitive detection of genomic homology in extremely large data sets[END_REF]. The pipeline detailed previously investigated the relations between insertion sequences and these genome rearrangements, by using two different methods that will be described below.

Naked eye investigations

In order to visualize the positions of IS elements involved in genomic recombination that have occurred in the considered set of Pseudomonas, we have first designed Python scripts that enable us to humanly visualize close genomes. Each complete genome has been annotated using the pipeline described in the previous section, and the strict core genome has been extracted. This latter is constituted by genes shared exactly once in each genome. Thus polymorphic nucleotides in these core genes have been extracted, and a phylogeny using maximum likelihood (RAxML [START_REF] Stamatakis | Raxml version 8: A tool for phylogenetic analysis and post-analysis of large phylogenies[END_REF][START_REF] Alkindy | Finding the core-genes of chloroplasts[END_REF] with automatically detected mutation model) has been inferred. (Figure 2). For each close isolates, a picture has then been produced using our designed Python script, for naked eye investigations. Real and Partial IS are represented with a red and green circles,respectively. Additionally, DNA sequences representing the same gene have been linked either with a curve (two same genes in the same isolate) or with a line (two same genes in two close isolates). Example of recombination events are given below. Fig. 4: The surrounding insertion sequences are within the same IS family (IS6) in the NCGM2.S1 genome. We have found too that insertion sequences are not always exactly at the beginning and end positions of the inversion, but they are overrepresented near these boundaries.

We will focus now on the link between large scale inversions and ISs as shown in Figure 4, by designing another pipeline that automatically investigate the inversions.

Automated investigations of inversions

The proposal is now to automatically extract all inversions that have occurred within the set of 18 genomes under consideration, and then to investigate their relation with predicted IS elements. The proposed pipeline is described in -Step1: Convert genomes from the list of predicted coding sequences in the list of integer numbers, by considering the cluster number of each gene. -Step2: Extract sets of inversion from all input genomes. 719 inversions have been found (see Table 3). -Step 3: Extract IS clusters (Partial and Real IS) using the first pipeline, as presented in a previous section. As presented in Figure 8, there is no major problem in dealing with small inversions because the small inversions having small ratio of increment as compared with big inversions (i.e., during window size increment of inversion boundaries, the small inversions, which have length lower than 4 genes, have small increase ratios compared to large inversions).

Table 4 details the roles of IS in largest inversions found within two close isolates. The IS family of type IS3 always have the most probability of appearance with left and right boundaries of inversions.(Figure 9)

Conclusion

We designed a pipeline that detects and classify all ORFs that belong to IS. It has been done by merging various tools for ORF prediction, clusterization, and by finally using ISFinder database for classification.

This pipeline has been applied on a set of Pseudomonas aeruginosa, showing an obvious improvement in ORFs detection that belong to insertion sequences. Furthermore, relations between inversions and insertion sequences have been emphasized, leading to the conclusion that the so-called IS3 family has the largest probability of appearance inside inversion boundaries.

In future works, we intend to investigate more deeply the relation between ISs and other genomic recombination such as deletion and insertion. We will then focus on the implication of other types of genes like rRNA (rrnA, rrnB, rrnC, rrnD) in P. aeruginosa recombination [START_REF] Stover | Complete genome sequence of pseudomonas aeruginosa pao1, an opportunistic pathogen[END_REF]. By doing so, we will be able to determine genes that are often associated with deletion, inversion, etc. The pipeline will be finally extended to eukaryotic genomes and to other kinds of transposable elements.

Fig. 1 :

 1 Fig. 1: Pipeline for detecting IS clusters in genomes of P.aeruginosa

Fig. 2 :

 2 Fig. 2: Phylogeny of P. aeruginosa based on mutations on core genome

  (a) Insertion events of IS sequences have occurred in this set of 18 P. aeruginosa species. For instance, when comparing DK2 and RP73, we have found that IS3-IS3 (2 ORFs) and IS3-IS407 (2 ORFs too) have been inserted inside RP73. (b) Deletions of insertion sequences can be found too, IS5 (Partial IS) is present in the genome of DK2, while it is deleted in the close isolates RP73.(c) A duplication occurs in the insertion sequence type IS110-IS1111 that contains one ORF (Real IS), as there are 6 copies of this insertion sequence in both PAO1 and C7447m genomes.

Fig. 3 :

 3 Fig. 3: Examples of genomic recombination events: Insertion, Deletion, and Duplication.

Fig. 5 :

 5 Fig. 5: Pipeline for detecting the role of ISs in inversions

( a )Fig. 6 :

 a6 Fig. 6: Using different window size within all inversions

Fig. 7 :

 7 Fig. 7: Different cases of IS inversions

Fig. 8 :

 8 Fig. 8: Small inversions ( 4 genes) vs. large inversions (> 4 genes).

Fig. 9 :

 9 Fig. 9: IS distribution using different windows size.

Table 1 :

 1 P. aeruginosa isolates used in this study.

	Isolates	NCBI accession number Number of genes
	19BR	485462089	6218
	213BR	485462091	6184
	B136-33	478476202	5818
	c7447m	543873856	5689
	DK2	392981410	5871
	LES431	566561164	6006
	LESB58	218888746	6059
	M18	386056071	5771
	MTB-1	564949884	6000
	NCGM2.S1	386062973	6226
	PA1	558672313	5981
	PA7	150958624	6031
	PACS2	106896550	5928
	PAO1	110645304	5681
	RP73	514407635	5804
	SCV20265	568306739	6190
	UCBPP-PA14	116048575	5908
	YL84	576902775	5856

Table 2 :

 2 Summary of detected IS clusters

		No. of Clusters Max. size of Cluster Total no. of IS genes
	Partial IS	94	57	362
	Real IS	66	49	238
	Total IS Cluster	160	-	600

Table 3 :

 3 Small and large inversions detected from all genomes

	Genome 1 Start Stop Genome 2 Start Stop Length (genes)
	19BR	1001 1002	213BR	5094 5095	2
	19BR	2907 2920	213BR	2933 2946	14
	19BR	684 685	LES431 4689 4690	2
	19BR	850 978	LES431 4393 4521	129
	PAO1	997 998	c7447m	1977 1978	2
	LESB58	4586 4587 LES431 2347 2348	2
	DK2	2602 2603	RP73	2516 2517	2
	DK2	1309 1558	RP73	3489 3738	250
	DK2	260 261 SCV20265 3824 3825	2
	DK2	2846 2852 SCV20265 3065 3071	7
	M18	3590 3591 PACS2	1920 1921	2
	M18	3194 3579 PACS2	2076 2461	386
	MTB-1	5581 5582 B136-33 4742 4743	2
	UCBPP-PA14 4820 4821 B136-33 2871 2872	2
	NCGM2.S1 1053 1307 MTB-1	4507 4761	255
	NCGM2.S1 1742 1743 MTB-1	4882 4883	2
	PA1	95	96	B136-33 2691 2692	2
	PA1	1334 1491 B136-33 1286 1443	158
	PACS2	94	97	PA1	495 498	4
	PACS2	970 1206	PA1	2220 2456	237
	SCV20265	45	46	YL84	721 722	2
	SCV20265	261 462	YL84	306 507	202
	UCBPP-PA14 259 260	B136-33 3507 3508	2
	YL84	721 722	M18	43	44	2
	YL84	768 983	M18	5555 5770	216
	YL84	721 722	PAO1	44	45	2
	YL84	1095 1264	PAO1	5192 5361	170

Table 4 :

 4 Summary of large inversion sets within closed genomes

	Genome 1 Genome 2 Inversions no. Largest inversion IS family	Boundary	Window
	19BR	213BR	9	14	IS110	LB1-RB2	w=0
	PAO1	c7447m	2	2	IS3	(LB1-RB2)/(LB2-RB1)	w=0
	LES431	LESB58	3	2	IS3	(LB1-RB2)/(LB2-RB1)	w=0
	DK2	RP73	93	250	Tn3	LB1-RB2	w=3
	UCBPP-PA14	B136-33	7	2	IS3	(LB1-RB2)/(LB2-RB1)	w=0
	NCGM2.S1	MTB-1	91	255	IS5	LB1-RB2	w=5

www-is.biotoul.fr