BASc Roxanne Dubé-Cyr

PhD, PEng Carl-Éric Aubin
email: carl-eric.aubin@polymtl.ca

PhD, PEng Isabelle Villemure

PhD Rohan-Jean Bianco

Yves Godio-Raboutet

Meng

PhD Pierre-Jean Arnoux

Biomechanical analysis of two insertion sites for the fixation of the sacroiliac joint via an oblique lateral approach

Keywords: Sacroiliac joint, sacroiliac joint fixation, sacroiliac joint fusion, arthrodesis, biomechanics, minimally invasive surgery

Background. The sacroiliac joint is an important source of low back pain. In severe cases, sacroiliac joint fusion is used to reduce pain, but revision rates can reach 30%. The lack of initial mechanical stability may lead to pseudarthrosis, thus not alleviating the patient's symptoms. This could be due to the damage induced to the interosseous ligament during implant insertion. Decoupling instrumentation steps (drillingtapping and implant insertion) would allow to verify this hypothesis. Moreover, no biomechanical studies have been published on sacroiliac joint fixation with an oblique lateral approach, while it has important clinical advantages over the lateral approach.

Methods. Eight cadaveric human pelves with both ischia embedded were tested in three sequential states: intact, drilled-tapped and instrumented with one cylindrical threaded implant with an oblique lateral trajectory. Specimens were assigned one of two insertion sites (distal point; near the posterior superior iliac spine, and proximal point; anterosuperior to the distal point) and tested in compression and flexionextension. Vertical and angular displacements of the sacroiliac joint were measured locally using digital image correlation methods.

Findings. In compression, instrumentation significantly reduced vertical displacements (17% (SD 22%), P=0.04) but no difference was found for angular displacements or flexion-extension loads (P>0.05).

Drilling-tapping did not change the stability of the sacroiliac joint (P>0.05); there was no statistical difference between the insertion sites (P>0.05).

Interpretations. Insertion of one implant through either the distal or proximal insertion site with an oblique lateral approach significantly reduced vertical displacements of the sacroiliac joint in compression, a predominant load of this joint.

Introduction

The sacroiliac joint (SIJ) ensures the transmission of important forces from the spine and upper body to the lower limbs. The SIJ generates pain in 15 to 30% of patients suffering from low back pain [START_REF] Cohen | Sacroiliac joint pain: a comprehensive review of epidemiology, diagnosis and treatment[END_REF] . Treatment options include anti-inflammatory medication, physical therapy, sacral belt, and in last resort, surgical fusion. For the latter, implants are inserted across the sacrum and ilium through the SIJ to allow mechanical stability. An osseointegration process begins and the opposing bony surfaces start to biologically fuse. In a meta-analysis evaluating five clinical outcome measures, minimally invasive SIJ fusion was proven effective for alleviating girdle pain 2 . Minimally invasive SIJ surgeries limit tissue exposure during surgery and only necessitate a 3-cm long incision while offering greater pain relief than open surgeries [START_REF] Smith | Open versus minimally invasive sacroiliac joint fusion: a multicenter comparison of perioperative measures and clinical outcomes[END_REF] . Still, the fusion rate ranges from 25 to 88% after 12 months [START_REF] Duhon | Triangular Titanium Implants for Minimally Invasive Sacroiliac Joint Fusion: 2-Year Follow-Up from a Prospective Multicenter Trial[END_REF][START_REF] Rudolf | Five-year clinical and radiographic outcomes after minimally invasive sacroiliac joint fusion using triangular implants[END_REF][START_REF] Treon | Fusion rates following distraction interference arthrodesis of the sacroiliac joint. A retrospective study of post-operative computerized tomography (CT) scans[END_REF][START_REF] Cross | Minimally Invasive Sacroiliac Joint Fusion: 2-Year Radiographic and Clinical Outcomes with a Principles-Based SIJ Fusion System[END_REF][START_REF] Kube | Sacroiliac Joint Fusion: One Year Clinical and Radiographic Results Following Minimally Invasive Sacroiliac Joint Fusion Surgery[END_REF] . Patients with persistent or recurrent pain may require a revision surgery, with revision rates reaching 30% after 4 years [START_REF] Spain | Surgical Revision after Sacroiliac Joint Fixation or Fusion[END_REF] .

As the quality of the biological fusion and osseointegration is linked to the initial mechanical stability [START_REF] Javed | Role of primary stability for successful osseointegration of dental implants: Factors of influence and evaluation[END_REF] , researchers have investigated the effect of instrumentation on SIJ range of motion (RoM). In cadaveric studies, instrumentation with either two cylindrical and threaded implants, or three implants with a triangular cross-section significantly decreased the RoM by 27% to 54% [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Shih | Biomechanical evaluation of sacroiliac joint fixation with decortication[END_REF][START_REF] Lindsey | Biomechanics of unilateral and bilateral sacroiliac joint stabilization: laboratory investigation[END_REF] . However, the SIJ RoM is not significantly reduced for all specimens. Counterintuitively, the SIJ RoM is sometimes increased following fixation [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Lindsey | Biomechanics of unilateral and bilateral sacroiliac joint stabilization: laboratory investigation[END_REF] . In a clinical setting, an insufficient reduction in SIJ RoM may lead to pseudarthrosis, which does not alleviate the patient's symptoms. Increased RoM could be explained by the damage to the interosseous ligament (IOL), the strongest and largest of SIJ ligaments [START_REF] Vleeming | The sacroiliac joint: an overview of its anatomy, function and potential clinical implications[END_REF] during implant insertion. The IOL directly connects the SIJ surfaces together, so a modification to its integrity could lead to a loss of stability greater than the stability gain provided by the implants. This hypothesis could be verified by isolating the effects of drilling and tapping on SIJ stability, which has not been done before. Decoupling instrumentation steps (drilling-tapping and implant insertion) would allow a better understanding of SIJ biomechanics and SIJ fixation. SIJ initial mechanical stability also depends on certain surgical choices like the surgical approach and implant trajectory, as well as the type, size, and number of implants. For instance, the two main surgical approaches for minimally invasive SIJ fixation are the direct lateral and the oblique lateral approaches, respectively referred to as lateral and oblique in the text for simplicity. Compared to the oblique approach, the lateral approach requires considerably more dissection of the gluteal muscles (medius and maximus).

However, most of the recent clinical studies have used the lateral approach with triangular dowel implants and are industry-sponsored [START_REF] Yson | Sacroiliac Joint Fusion: Approaches and Recent Outcomes[END_REF] . Recently, two retrospective studies have compared the lateral and oblique approaches, using triangular implants and cylindrical threaded implants respectively. Majd et al. found the oblique approach to be superior for some clinical outcomes (higher rate of significant improvement on the visual analogue scale (VAS) (65% vs 45%), lower estimated blood loss (33cc vs 60cc), lower adverse event rate (6.7% vs 20%) [START_REF] Majd | Retrospective analysis of Sacroiliac Joint (SIJ) fusions comparing the percutaneous transgluteal approach to the posterior oblique approach[END_REF] . However, significance was not mentioned. Claus et al. found that both approaches led to a significant improvement of the Oswestry Disability Index (ODI) and SF-12 (Short Form-12 health survey) scores, without a significant difference between the two techniques [START_REF] Claus | Minimally Invasive Sacroiliac Joint Fusion Using Triangular Titanium versus Cylindrical Threaded Implants: A Comparison of Patient-Reported Outcomes[END_REF] . Length of stay, estimated blood loss were not statistically different between the groups but the oblique approach had a significantly longer surgery (60 min vs 41 min) [START_REF] Claus | Minimally Invasive Sacroiliac Joint Fusion Using Triangular Titanium versus Cylindrical Threaded Implants: A Comparison of Patient-Reported Outcomes[END_REF] . Revision rate was higher for the oblique approach compared to the lateral approach (6.1% vs 2.4%), but the difference was not statistically significant. Many experimental and numerical studies have been conducted on the lateral approach 11-14,19-21 compared to only one numerical study on the oblique approach [START_REF] Bruna-Rosso | Finite Element Analysis of Sacroiliac Joint Fixation under Compression Loads[END_REF] . Bruna-Rosso et al. simulated an oblique SIJ instrumentation using a finite element model of the pelvis with one to two threaded implants and compared two insertion sites and two implant orientations [START_REF] Bruna-Rosso | Finite Element Analysis of Sacroiliac Joint Fixation under Compression Loads[END_REF] . Placing the implant farther from the SIJ center of rotation (CoR) (located at the axial interosseous ligament according to Farabeuf's theory [START_REF] Kapandji | Physiologie articulaire : schémas commentés de mécanique humaine. 3, Rachis, ceinture pelvienne, rachis lombal, rachis dorsal, rachis cervical[END_REF] ) and using an orientation more parallel to the SIJ CoR led to a better stabilization of the SIJ subjected to compression loads. No cadaveric studies have been published on this approach, but such study would allow a better understanding of oblique fixation and help further reduce revision rates.

Hence, the current study aimed to experimentally measure the isolated effects of drilling and tapping as well as the effects of oblique SIJ fixation on SIJ RoM while comparing two possible insertion sites. It was hypothesized that instrumenting the SIJ with one implant would lead to significant motion reduction and that there would be a significant difference between the two tested insertion points.

Methods

Specimen preparation

The pelves (sacrum and iliac bones) of eight human specimens (age ranged from 73 to 94 years old; Table 1) embalmed with a zinc chloride solution were harvested. They were thawed at room temperature and cleaned of muscle tissue while keeping the ligaments of the SIJ intact (anterior, posterior, IOL, sacrotuberous and sacrospinous ligaments). CT-scans were taken to ensure there were no anomalies like bone bridging. Bone mineral density was measured with a calibration phantom (Model 062M Electron Density Phantom, CIRS Inc., Virginia, USA). Specimens were wrapped in saline-soaked gauze, placed in plastic bags and stored at -20 °C. The day before testing, they were thawed at room temperature and placed in neutral position (i.e. anterior superior iliac spine in line with the pubic symphysis in the vertical plane).

The inferior part of the specimens was embedded in a bloc of fast-curing resin (1:1 mixture of F18 Polyol and F18 Isocyanate, Axson Technologies, Cergy, France) up to the obturator foramina in a double-leg stance model (Fig. 1A). They were wrapped in saline-soaked gauze and put in a refrigerator (4 °C) until the next day. Right before the beginning of the tests, a random speckle pattern was produced on the anterior SIJ surfaces using a black spray paint over uniform white paint (Fig. 1A).

Test procedure

Specimens were randomly divided into two equal groups (n=4/group) and assigned one of two insertion sites. The distal point was located near the posterior superior iliac spine (PSIS) (Fig. 2). The proximal point was positioned anterosuperiorly to the distal point [START_REF] Bruna-Rosso | Finite Element Analysis of Sacroiliac Joint Fixation under Compression Loads[END_REF] . Metal bars and clamps rigidly fastened the resin bloc to a 370.02-15kN MTS servohydraulic system (MTS Systems, Créteil, France) (Fig. 1B). A custom metal piece was firmly fixed on the endplate of S1 with wood screws. The displacements between the sacrum and the ilium were measured in three states. First, the specimens were tested in the "intact state" under compression and flexion-extension (FE) loads (see next paragraph) to obtain a reference RoM and allow subsequent comparison. Next, using a posteromedial approach (Fig. 2) [START_REF] Bruna-Rosso | Finite Element Analysis of Sacroiliac Joint Fixation under Compression Loads[END_REF] , we positioned a guidewire using a template to ensure repeatability of the insertion sites.

Then, a drill and a depth-stop were used over the guidewire to drill a 12-mm diameter hole for a 50-mm long threaded, cannulated and fenestrated implant (RIALTO™ Sacroiliac Joint Fusion System, Medtronic, Memphis, TN, USA). With a surgical tap, we threaded the insertion hole and tested the specimens for the "drilled state". Finally, the implant was inserted and specimens were tested again in the "instrumented state". All implants were inserted on the right side. Implant position was confirmed with a CT-scan after testing.

Specimens were tested in compression and FE under quasi-static loads (10 N/s) preceded by 15 preconditioning cycles (0.5 Hz) of 40 N. The compression loads (i.e. vertical axis) reached 500 N and were applied with a hinge joint (Fig. 3A). The two cycles of FE (i.e. sagittal plane) ranging from -7.5 Nm to 7.5

Nm were applied with a pivot joint. The FE moments were achieved with a lever arm and a 5-kg weight, resulting in a combined compression ranging from 25 to 175N respectively (Fig. 3B). A total of six tests were performed for each specimen. On average, it took 120 minutes to perform the tests (time ranged from 80 to 185 minutes). To avoid dehydration during testing, saline-soaked gauzes were applied posteriorly on the sacrum, covering the posterior portion of the SIJs. It was not possible to apply saline-soaked gauzes on the anterior portion of the SIJs because of the speckle pattern.

Data measurement and analysis

Two 1MP cameras (FASTCAM SA3 Model 120K, Photron Europe Limited, West Wycombe, UK) were placed with a 20° to 25° angle between them (Fig. 1B). The intra-articular displacements were measured locally with the Correlated Solutions VIC-3D measurement system (Correlated Solutions Incorporated, Columbia, SC, USA). This system calculated the three-dimensional displacements on the surface nearby the joint based on the principle of digital image correlation (DIC). In-plane precision was under 0.005 mm while out-of-plane precision was 0.01 mm.

Using the VIC-3D software, we numerically selected sets of three points along the right SIJ (three on the ilium and three on the sacral ala) for a total of six points (Fig. 4). The relative vertical displacements (VD) (z-axis) of the sacrum was computed with regards to the ilium. The vertical displacement of the ilium (pt.

2) was subtracted from the vertical displacement of the sacrum (pt. 5) throughout loading, and the maximum value over time was reported. To measure the relative angular displacements (AD) in the sagittal (x-z) plane, lines connecting the top and bottom points for each set of points (1-3; 4-6) were virtually drawn. Next, the angle between the sacral ala and the ilium was computed before (θ B ) and throughout loading (θ A ) using the lines' slopes. The angle difference over time ) was measured. For the FE loads, the values reported represent the total RoM, i.e. the maximum AD in flexion added to the maximum AD in extension. Both VD and AD were computed for each loading scenarios.

Statistical analysis

Statistical analysis was made with Statistica (v13.3; TIBCO Software Inc., Palo Alto, CA, USA). A Wilcoxon signed rank test was applied to compare the "drilled state" and the "instrumented state" to the "intact state" and check for significant differences. This type of analysis takes into account the intervariability that is inherent to cadaveric testing. The two insertion sites were compared by applying a Mann-Whitney U test on the normalized data (percentage change with regards to the "intact state" of each specimen). For all statistical tests, the significance level was set at 0.05.

Results

Seven specimens completed the testing protocol (Table 1). One specimen (ID1) deteriorated at the end of the second test and was therefore not included in the analysis. The age ranged from 73 to 94 years. No bone bridging was detected from the CT-scans.

Discussion

We experimentally measured the isolated effects of drilling and tapping as well as implant insertion on SIJ stability and compared two insertion sites using image correlation methods. The VD of the intact SIJs agree with previous studies, which reported means ranging from 0.32 to 0.7 mm [START_REF] Jacob | The mobility of the sacroiliac joints in healthy volunteers between 20 and 50 years of age[END_REF][START_REF] Baria | Sacroiliac joint biomechanics and effects of fusion[END_REF][START_REF] Hammer | Physiological in vitro sacroiliac joint motion: a study on three-dimensional posterior pelvic ring kinematics[END_REF] . The measured AD are in line with rotations measured in vivo (means of 0.5° and 0.8°, respectively) [START_REF] Kibsgard | Radiosteriometric analysis of movement in the sacroiliac joint during a single-leg stance in patients with long-lasting pelvic girdle pain[END_REF][START_REF] Kibsgard | Movement of the sacroiliac joint during the Active Straight Leg Raise test in patients with long-lasting severe sacroiliac joint pain[END_REF] but are below AD reported in most ex vivo studies (means ranging from 1.3° to 4.5° for similar FE loads) [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Shih | Biomechanical evaluation of sacroiliac joint fixation with decortication[END_REF][START_REF] Lindsey | Biomechanics of unilateral and bilateral sacroiliac joint stabilization: laboratory investigation[END_REF][START_REF] Hammer | Physiological in vitro sacroiliac joint motion: a study on three-dimensional posterior pelvic ring kinematics[END_REF] . Those ex vivo studies had younger subjects and higher female to male ratios, both factors increasing SIJ mobility. Moreover, the single-leg stance model used in these studies increases the shear force [START_REF] Dall | Surgery for the Painful, Dysfunctional Sacroiliac Joint: A Clinical Guide[END_REF] during compressive loading of L5 and showed motion was present between the SIJ and the pubic symphysis [START_REF] Hammer | Physiological in vitro sacroiliac joint motion: a study on three-dimensional posterior pelvic ring kinematics[END_REF] , meaning the ilium should not be considered as a rigid body. Using a double-leg stance model, they found a negligible AD of the sacrum with regards to the ilium of 0.01°. In the present study, DIC allowed to select iliac reference points millimeters away from the articulation, which may give a better representation of the actual relative displacements of the SIJ.

The loads used in this study do not represent all possible loads present in the pelvis. Compression is the most important load of the SIJ because it is almost always present in most diurnal postures and motions (i.e. upper body weight) and contributes to the stability of the pelvic ring [START_REF] Vleeming | Form and Force Closure of the Sacroiliac Joints[END_REF] . FE is also involved in several tasks, and puts even more loads on the SIJ. In this study, it was modeled with a lever-arm that led to a combination of FE and compression. This type of loading may be more realistic than pure moments, which do not take into consideration the stability provided by the compression and force-closure mechanisms.

Lateral bending and axial rotation were not included, but could be tested in future studies to assess a wider variety of possible loadings.

Drilling and tapping for one implant unilaterally did not destabilize the SIJ. Therefore, the damage to the IOL created to insert an implant does not explain why some specimens lose stability after instrumentation.

The maximum cross-section area of IOL that was cut (≈115 mm²) remains relatively small compared to its total section of approximately 750 mm² [START_REF] Steinke | Novel insights into the sacroiliac joint ligaments[END_REF] . In a study by Dall et al., transecting the entire posterior ligament complex (including the IOL) led to a significant, but relatively small increase of motion, with AD staying under 2°2 [START_REF] Spain | Surgical Revision after Sacroiliac Joint Fixation or Fusion[END_REF] . This could be because form-closure mechanisms such as the self-locking arrangement of the pelvis and the fitting ridges and grooves of the articular surfaces provide great stability to the SIJ [START_REF] Vleeming | Form and Force Closure of the Sacroiliac Joints[END_REF] . Thus, SIJ stability relies only partially on the IOL. Another possible explanation for the lack of initial mechanical stability could be poor bone quality, but additional testing needs to be done.

Implant insertion significantly decreased VD for the compression load, with an average reduction of 17% (SD 22%), which is likely not enough to lead to an osseointegration. Instrumentation with one implant contributed relatively little to the stabilization of the SIJ, and had no significant effect on AD and for FE loads. Likewise, Jeong et al. did not find a significant decrease of AD in FE following instrumentation with three triangular implants [START_REF] Jeong | Assessment of Biomechanical Changes After Sacroiliac Joint Fusion by Application of the 3-Dimensional Motion Analysis Technique[END_REF] . Contrastingly, similar studies have reported a significant decrease of AD in FE using two or three implants [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Shih | Biomechanical evaluation of sacroiliac joint fixation with decortication[END_REF][START_REF] Lindsey | Biomechanics of unilateral and bilateral sacroiliac joint stabilization: laboratory investigation[END_REF] . However, most of them compared the RoM of the instrumented state to a "destabilized" state (posterior ligaments and/or pubic symphysis cut) [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Shih | Biomechanical evaluation of sacroiliac joint fixation with decortication[END_REF] , which may amplify the action of the implants. In the current study, the "instrumented state" consisted of only one implant and was compared to the "intact state". Because of the rotatory nature of the SIJ biomechanics, one fixation point may not be enough to successfully restrain different types of movements, especially given the proximity of the implant to the CoR of the SIJ, located near S2 [START_REF] Kapandji | Physiologie articulaire : schémas commentés de mécanique humaine. 3, Rachis, ceinture pelvienne, rachis lombal, rachis dorsal, rachis cervical[END_REF] . Adding more implants may reduce this effect and further increase stability, but additional testing is necessary.

The position of the two clinically plausible insertion sites tested did not lead to statistically different RoM reduction in the case of a one-implant scenario, as opposed to the previous numerical study of Bruna-Rosso et al [START_REF] Bruna-Rosso | Finite Element Analysis of Sacroiliac Joint Fixation under Compression Loads[END_REF] . The distance between the two tested sites was less than 15 mm, which might be too small to have an impact on the RoM. Hence, both insertion points provided a comparable SIJ stabilization.

Some mobility always remains ex vivo following instrumentation [START_REF] Lindsey | Evaluation of a minimally invasive procedure for sacroiliac joint fusionan in vitro biomechanical analysis of initial and cycled properties[END_REF][START_REF] Soriano-Baron | The effect of implant placement on sacroiliac joint range of motion: posterior versus transarticular[END_REF][START_REF] Shih | Biomechanical evaluation of sacroiliac joint fixation with decortication[END_REF][START_REF] Lindsey | Biomechanics of unilateral and bilateral sacroiliac joint stabilization: laboratory investigation[END_REF][START_REF] Jeong | Assessment of Biomechanical Changes After Sacroiliac Joint Fusion by Application of the 3-Dimensional Motion Analysis Technique[END_REF] , and it is hard to define a clinically significant RoM reduction. Muscular activity further stabilizes the SIJ in vivo, but remaining micromovements may hinder the osseointegration process. The ideal RoM restriction threshold to allow proper SIJ fusion is not known. Such threshold would be relevant to define clinical significance and assess the proper action of SIJ fusion implants and how it relates to the patient's pain.

This experimental study has some limitations. Results may have been influenced by freeze-thaw cycles, the duration of the tests and embalmment. Tan et al. studied the effect of freeze-thaw cycles, and multiple within-and between-day testing on human cadaveric lumbosacral spine [START_REF] Tan | Cumulative Multiple Freeze-Thaw Cycles and Testing Does Not Affect Subsequent Within-Day Variation in Intervertebral Flexibility of Human Cadaveric Lumbosacral Spine[END_REF] . They found that the initial four freeze-thaw cycles had no significant effect on the RoM of the segments and that cumulative testing (8 tests; up to 12 hours) within a single day did not lead to significant differences in RoM. In the present study, each specimen went through two freeze-thaw cycles and testing was done in a single day, in under 3 hours, so the impact on the results are thought to be minimal. However, because of the paint and speckle pattern, it was not possible to keep the anterior part of the SIJ moist with saline-soaked gauzes once the tests started. The anterior ligaments may have dried up and stiffened, possibly contributing to the small displacements measured. Given that the tests were performed in 120 minutes on average, we believe that the ligament of interest, the IOL, was deep enough to stay hydrated throughout testing. As for embalmment, it may also have stiffened the ligaments of the SIJ, which may have affected the results, especially regarding the effect of drilling through the IOL. However, unlike a true synovial joint, the biomechanics of the SIJ relies largely on form-closure mechanisms of the pelvis (i.e. shape of the bones) that are independent of soft tissues, thus we believe the effect of soft tissue stiffening was limited. The specimens were old with varying bone quality and this might have affected the SIJ RoM. However, the CTscans showed no bone bridging or other anomalies. In addition, the measured effect of the implants was obtained on the basis of comparison, so the conclusions drawn likely remain valid.

Conclusions

This is the first biomechanical study to investigate SIJ fusion via an oblique approach. We measured the isolated effects of drilling-tapping and instrumentation on SIJ stability and compared two different insertion sites. Drilling through the IOL did not increase the intra-articular displacements of the SIJ, and thus this hypothesis is rejected. Our main hypothesis was only partly accepted, as instrumenting the SIJ with one implant significantly decreased vertical displacements in compression but led to no motion reduction in flexion-extension and no significant difference between both insertion sites.

Acknowledgments

The authors acknowledge the support of Dr Kathia Chaumoître, MD, and the Assistance Publique-Hôpitaux de Marseille, (Hôpital Nord, Marseille, France) for their radiologic expertise. The authors would also like Medtronic for providing the implants and surgical kit for the study.

Fig. 1

 1 Fig. 1 Experimental set-up: A) Double-leg stance model and B) camera position

Fig. 2

 2 Fig. 2 Insertion points tested and implant trajectory -Posteroanterior view

Fig. 3

 3 Fig. 3 Experimental devices for A) compression and B) flexion-extension loads (combined with compression)

Fig. 4

 4 Fig. 4 Representation of the selected points for the measurement of SIJ relative A) vertical displacements (VD) and B) angular displacements (AD). C) Side view of the sacrum for the measurement of AD. For visualization purposes only.

  and thus leads to larger SIJ displacements. The rehabilitation guidelines by Dall et al. recommend to avoid single-leg stance until bony fusion has occurred, which is usually within 6 to 8 weeks 29 . Cadaveric testing aims to simulate the initial postoperative stabilization; therefore, a double-leg stance model was deemed appropriate. The distance from the SIJ to the reference point on the ilium may also influence the reported RoM. Lindsey et al., Soriano-Baron et al. and Jeong et al. placed their marker on the iliac wings, near the anterior superior iliac spine, while Shih et al. placed it near the acetabulum 11-13,21 . Hammer et al. quantified the RoM of the ilia

  to thank: the A*MIDEX foundation, MITACS Globalink, the Fonds de recherche du Québec -Nature et technologies and the Natural Sciences and Engineering Research Council of Canada (Industrial Research Chair program with Medtronic of Canadagrant number: PCIPJ-346145) for their financial support and

Table 1

 1 Specimen information

	Specimen	Sex	Age (yr)	Bone mineral density (mg/cm³)
	*ID1	H	88	90
	ID2	F	74	155
	ID3	H	73	200
	ID4	H	73	105
	ID5	H	76	90
	ID6	H	83	35
	ID7	H	94	95
	ID8	F	83	80
	*Mean		79.4	108.6
	SD		7.8	53.7

Note: *Means and SD calculated without ID1

Intra-articular displacements of adjoining sacrum and ilium of the "intact state" ranged from 0.08 mm to 2.20 mm for VD (translation) and from 0.15° to 2.83° for AD (rotation) (Table

2

). No significant difference was found in compression or in FE between the "intact state" (CI: 0.14 -1.36 (compression, VD), 0.05 -0.40 (FE,VD), CI: 0.01 -1.70 (compression, AD), 0.16 -0.75 (FE, AD)) and the "drilled state" (CI: 0.14 -1.19 (compression,VD), 0.06 -0.41 (FE,VD), CI: -0.01 -1.52 (compression, AD), 0.14 -0.79 (FE, AD), (P>0.05). In compression, insertion of the implant led to a significant decrease of VD compared to the "intact state" (CI: 0.08 -1.16, P=0.04). It had no significant effect on AD (CI: 0.001 -1.56) (P>0.05). In FE, the implant had no significant effect on VD (CI: 0.06 -0.36) or AD (CI: 0.21 -0.68) (P>0.05). There was no significant difference between the two insertion sites in compression (CI: -37.37 -2.96 (VD), CI: -23.25 -19.81(AD)) or in FE (CI: -35.50 41.33 (VD), CI: -22.41 -35.94 (AD), P>0.05) (Table

3

).

Table 2

 2 Relative SIJ displacements of the instrumented side

				Compression			Flexion-extension
	Specimen	Insertion point	Intact	Drilled	Instrumented	Intact	Drilled	Instrumented
					Vertical displacement -VD (mm)
	*ID1	1	0.21	-	-	0.04	-	-
	ID2	2	0.55	0.37	0.33	0.10	0.12	0.10
	ID3	1	0.49	0.48	0.25	0.19	0.23	0.11
	ID4	2	0.56	0.42	0.46	0.16	0.14	0.20

Note: *Means and SD calculated without ID1

Table 3

 3 Comparison of the RoM change (%) for the insertion points tested (average, and each specimen values)

	Percentage change (intact vs. instrumented) (%)

Declarations of interest: Medtronic provided the implants and surgical kit for the study. Carl-Éric Aubin is currently receiving funding from the Natural Sciences and Engineering Research Council of Canada (Industrial Research Chair program with Medtronic of Canada). The other authors have no conflict of interest to declare.


Muhammad Imran Khan

Simon N Foley

Barry O'sullivan

From k-anonymity to Differential Privacy: A Brief Introduction to Formal Privacy Models

Keywords: k-anonymity, l-diversity, t-closeness, (α, k)-anonymity, Multi-relational kanonymity, -differential Privacy, Relational Database Management Systems, Privacy Definitions, Privacy Models

A number of formal privacy definitions also known as privacy models are presented when these definitions are followed then the anonymized data manifests some formal guarantees. There are several privacy definitions proposed in the literature including k-anonymity, differential privacy l-diversity, t-closeness so on and so forth. In this paper, we review some of the well-know formal privacy definitions.

Introduction: Countless Shades of Privacy

Privacy is a challenging concept to define because of its culturally subjective basis. A classic paper [START_REF] Schoeman | Privacy: Philosophical dimensions[END_REF] considers the philosophical dimensions of privacy in three perspectives: "i. a claim, entitlement or right of an individual to determine what information about himself may be communicated to others [START_REF] Zuckerman | Privacy in colonial new england. by david h. flaherty[END_REF]3]. ii. measure of the control an individual has over: (a) information about himself; (b) intimacies of personal identity; or (c) who has sensory access to himself [START_REF] Polyvios | Search & seizure : constitutional and common law Polyvios G. Polyviou[END_REF][START_REF] Parent | Privacy, morality, and the law[END_REF][START_REF] Fried | Privacy[END_REF][START_REF] Henkin | Privacy and autonomy[END_REF].

iii. state or condition of limited access to a person [START_REF] Gavison | Privacy and the limits of law[END_REF][START_REF] Christopher | Privacy, law, and public policy. by david m. obrien[END_REF]." This right to privacy is a globally recognised right as stated in Article 12 of the UN's Universal Declaration of Human Rights that states [10],

1 "No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation. Everyone has the right to the protection of the law against such interference or attacks."

Taking the privacy concerns of the modern-day digital world, legislators have provided legal cover to the public to ensure their right to privacy. Dominant examples of such legislation include the Health Insurance Portability and Accountability Act (HIPAA, 1996) [START_REF]The Health Insurance Portability and Accountability Act of 1996[END_REF], the EU's General Data Protection Regulation [START_REF]reform of EU data protection rules[END_REF], the OECD privacy framework [START_REF]The OECD privacy framework[END_REF]. 58% of total countries in the world have data protection and privacy legislation in place while 10% have draft legislation and 21% of the countries still have no legislation in place (there is no data for the remaining 12%) [START_REF] Yang | Recommending join queries via query log analysis[END_REF].

Contemporary organizations collect large volumes of data over which analytics are routinely carried out for various purposes, including data-driven marketing and informed decision making. Organizations often delegate this task to third parties specializing in data analytics. The collection, storage, processing, and sharing of personal data raises dimensions privacy concerns.

The work of Tore Dalenius in [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF], points out the problem of publishing the data of populations without risking individual's privacy. The research in this domain started to gain momentum in the late 1970s and 1980s, especially in the context of publishing census data. Recently privacy research is no longer limited to census data, as emerging new technologies have brought privacy concerns along, for example, the privacy concerns in social networks [START_REF] Fogel | Internet social network communities: Risk taking, trust, and privacy concerns[END_REF][START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF][START_REF] Cutillo | Safebook: A privacy-preserving online social network leveraging on real-life trust[END_REF], internet of things [START_REF] Sicari | Security, privacy and trust in internet of things: The road ahead[END_REF][START_REF] Ukil | Iot-privacy: To be private or not to be private[END_REF][START_REF] Porambage | The quest for privacy in the internet of things[END_REF]] and e-commerce [START_REF] Gurung | Online privacy and security concerns of consumers[END_REF][START_REF] Milne | Consumers' protection of online privacy and identity[END_REF][START_REF] Antoniou | E-commerce: protecting purchaser privacy to enforce trust[END_REF].

The relational data model is the most widely used data model for storage and processing of data [START_REF] Codd | A relational model of data for large shared data banks[END_REF][START_REF] Watt | Database Design[END_REF]; for this reason, the relational data model in DBMS (Relational DBMS -RDBMS) is considered in this work. To ensure the privacy of individuals, the data is anonymized. The anonymized version of data is typically made available in two settings within the RDBMS framework, that are, non-interactive and interactive query setting. Interactive query setting allows dynamic queries, while in a non-interactive setting an anonymized version of the entire database is made available. In general, data is considered anonymized if it complies with a formal privacy definition. Several of the formal definitions of privacy have been proposed in the literature that are reviewed in the next Section 2. When an anonymized version of data is made available, then in that context an adversary aims to strive for identifying individuals and disclosing their sensitive attributes in the database.

Formal Privacy Definitions

Several forms of privacy have been formalized in the literature. The two mainstream definitions of privacy are k-anonymity [START_REF] Syed Rafiul Hussain | Detanom: Detecting anomalous database transactions by insiders[END_REF] and differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF]. k-anonymity serves as the foundation for several privacy definitions including l-diversity [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF], t-closeness [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF], (α, k)anonymity [START_REF] Raymond | α, k)-anonymity: An enhanced k-anonymity model for privacy preserving data publishing[END_REF]. This section reviews the well-known formal privacy definitions. The definitions are described within the framework of relational databases, and therefore, before reviewing the privacy definitions, the next section defines the key relational database terms used in this paper.

Key Relational Database Terms

In a relational model a relation instance is denoted as T = {r 1 , r 2 , . . . , r n } where r i is a tuple of attribute values that represents a record. T is a subset of some larger population U. Each tuple represents an individual from U. Let the set of attributes be denoted by Attr = {attr 1 , attr 2 , . . . , attr n }, for example, the table shown in Figure 1, Attr = {Name, City, Country}. The value of attribute attr j for a tuple r i is denoted as r i [attr j ], for example, r

k-anonymity based and Extensions

k-anonymity [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] can be considered among the first formal definitions of privacy. The following sections presents k-anonymity and its extensions.

k-anonymity

In the context of k-anonymity, attributes are classified in the following non-exclusive categories, Identifiers, Quasi-Identifiers, and Sensitive attributes. The classification is typically performed based on the risk of record re-identification using these attributes and the sensitivity of the information these attributes convey.

• Identifier: an identifier is defined as "an attribute that refers to only a particular individual in the given population U". Let the set of identifiers be denoted as I ∈ Attr. An • Quasi-Identifier (QI): quasi-identifiers by themselves do not uniquely identify individuals; however, when correlated with other available external data, an individual (or individuals) can be identified. A quasi-identifier is defined in [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF][START_REF] Sweeney | Simple demographics often identify people uniquely[END_REF] as a "set of non-sensitive attributes of a relation if linked with external data to then uniquely identify at least one individual in the population U". Let the set of quasi-identifiers be denoted as QI ∈ Attr.

An example of quasi-identifier is the set of attributes Zipcode, Date of Birth, and Gender. For instance, the set of attributes Zipcode, Date of Birth, and Gender was used to re-identify governor of Massachusetts in [START_REF] Sweeney | Simple demographics often identify people uniquely[END_REF]. The re-identification was performed by directly linking shared attributes in two datasets, i.e. voter rolls and insurance company datasets. It was reported that 87% of the US population could be identified by these three attributes [START_REF] Sweeney | Simple demographics often identify people uniquely[END_REF].

• Sensitive attribute: sensitive attributes consist of sensitive person-specific information.

This information includes salary, disability status, or disease. The set of sensitive attributes is denoted as SenAttr ∈ Attr. All possible values for the sensitive attribute is denoted as SAV = {sv 1 , sv 2 , . . . , sv n }.

k-anonymity is defined in [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] as follows, "a relation T satisfies k-anonymity if and only if each tuple r i [QI] ∈ T appears with at least k occurrence in T".

k-anonymity [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] provides a degree of anonymity if the data for each person cannot be distinguished from k-1 individuals in a released dataset with respect to a set of quasi-identifiers.

Given QI ∈ Attr then two tuples r i and r j are quasi-identifier equivalent if

r i [QI] = r j [QI].
The relation T can be divided into quasi-identifier equivalence classes. Let the set of all the equivalence classes in T be E where each equivalence class e ∈ E consists of all the rows that have the same values for each quasi-identifier.

Another way to define k-anonymity is that a relation T satisfies k-anonymity if the minimum equivalence class size is at least k in T. Tables 2 and3 show an original and a k-anonymized

(3-anonymized) version of the microdata relations, respectively, where Name is an identifier, attributes Age & Zipcode are quasi-identifiers, and the attribute Salary is a sensitive attribute.

In Table 3 the identifier Name is suppressed and is shown as * while quasi-identifiers Age & Zipcode are generalized -replacing with a semantically similar but less specific value. In Table 3, records #1, #2, and #3, form an equivalence class, similarly records #4, #5, and #6 as well as records #7, #8, and #9 also forms equivalence classes with respect to the quasiidentifiers {Age & Zipcode}. Originally, k-anonymity was proposed for a one-time release of data, meaning that the user is not enabled to query the DBMS interactively.

Though considered to be among the first privacy definitions, k-anonymity, has been widely applied in many domains to preserve privacy for examples Location-based services [START_REF] Zhao | Illia: Enablingk-anonymitybased privacy preserving against location injection attacks in continuous lbs queries[END_REF][START_REF] Ye | An improved location-based service authentication algorithm with personalized k-anonymity[END_REF][START_REF] Zhang | On designing satisfaction-ratio-aware truthful incentive mechanisms fork-anonymity location privacy[END_REF][START_REF] Wang | A differentially k-anonymity-based location privacy-preserving for mobile crowdsourcing systems[END_REF][START_REF] Zhong | Connecting Things to Things in Physical-World: Security and Privacy Issues in Vehicular Ad-hoc Networks[END_REF], ride-hailing services [START_REF] Khazbak | Preserving location privacy in ride-hailing service[END_REF], and webmail auditing [START_REF] Di Castro | Enforcing k-anonymity in web mail auditing[END_REF]. k-anonymity has been used along with cryptographic hashing to develop a protocol that provides a degree of anonymity while checking for passwords in a compromised databases [START_REF] Ali | Mechanism for the prevention of password reuse through anonymized hashes[END_REF]. 2.

#
A weakness of k-anonymity is its susceptibility to the homogeneity attack and the background knowledge attack [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF]. If all the values for one of the sensitive attributes, within an equivalence class, are same then it results in a homogeneity attack, for instance, if the adversary knows an individual who is 33 years old and lives in the zipcode 3134 and has record is in an equivalence class where all the salaries are 77k then the adversary deduces that the individual's salary is 77k, though the table is k-anonymized. In [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF], it was shown that if the adversary knows that Japanese patients are less likely to have heart-related diseases (background knowledge) enabled an adversary to predict the diagonals for an individual.

l-diversity

Another well-known definition of privacy is l-diversity which is an extension of k-anonymity.

The l-diversity principle in [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] states "an equivalence class e is l-diverse if it contains at least 'well-represented' values for the sensitive attribute ∈ SenAttr. A relation T is l-diverse if all the equivalence classes (q-block) are l-diverse". The term 'well-represented' is instantiated in three different ways as defined by the authors in [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] that are Distinct l-diversity, Entropy ldiversity, and Recursive (c-l)-diversity. The elementary form of l-diversity is distinct l-diversity.

The remaining two instantiations are stronger instantiations and take the distribution of sensitive attribute values into account.

• Distinct l-diversity definition requires l distinct values in each equivalence class e ∈ E.

• Entropy l-diversity is defined in [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] as "A table l-diverse if for every equivalence class e ∈ E the entropy of the distribution of sensitive values in each equivalence class is at least log(l)".

• Recursive (c, l)-diversity requires that the least frequent sensitive attribute values that do not appear rarely as well as most frequent sensitive attributes values do not appear too frequently in an equivalence class e.

t-closeness

The t-closeness definition is a refinement of l-diversity. The authors in [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF] define t-closeness as "An equivalence class e is said to have t-closeness if the distance between the distribution of a sensitive attribute value in this class and the distribution of the sensitive attribute value in the whole relation T is no more than a threshold t." As a distance metric, the Earth Mover's Distance can be used to measure the distance between two frequency distributions [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF].

l-diversity treats sensitive attributes of all the equivalence classes in a similar manner without taking into account the global distribution of these sensitive attribute values in the relation.

However, in the case of real-world datasets, sensitive attribute values might be skewed; therefore, it would be desirable to take into account the global distribution of sensitive attribute values.

Limitations of t-closeness are discussed in [START_REF] Domingo-Ferrer | A critique of k-anonymity and some of its enhancements[END_REF], t-closeness degrades utility, is challenging to be achieved, and under certain scenarios, it is shown to be NP-hard [START_REF] Liang | On the complexity of t-closeness anonymization and related problems[END_REF].

(α, k)-anonymity

The (α, k)-anonymity is an enhanced version of k-anonymity. The (α, k)-anonymity defines that the frequency of sensitive attribute values α remains within the user-defined threshold in equivalence classes. The authors introduced an α-deassociation requirement in [START_REF] Raymond | α, k)-anonymity: An enhanced k-anonymity model for privacy preserving data publishing[END_REF], if this requirement is satisfied along with k-anonymity, then it is said that (α, k)-anonymity is satisfied. Given a sensitive attribute value sv i , a relation T is α-deassociated if the relative frequency of sv i in every equivalence class of E, that is |(e, sv i )|/|e| , is no more than α. Where (e, sv i ) be the set of tuples in equivalence class e containing sv i and α. A limitation of (α, k)-anonymity is that it may result in a high level of distortion if the values for sensitive attributes are skewed [START_REF] Benjamin | Introduction to Privacy-Preserving Data Publishing: Concepts and Techniques[END_REF].

m-invariance

The m-invariance definition is also built upon k-anonymity. Most of the privacy definitions are This privacy definition captures dynamic republication of relations. However, the condition that values of the sensitive attribute should remain the same, as are in previous releases, is strong and limits its applicability.

(k, e)-anonymity

The (k, e)-anonymity definition is an alteration of k-anonymity tailored for numeric data and can only be applied to sensitive attributes having numeric values. (k, e)-anonymity requires that the range of the equivalence class e to be larger than a certain threshold [START_REF] Zhang | Aggregate query answering on anonymized tables[END_REF].

(k, e)-anonymity is susceptible to proximity attack [START_REF] Li | Preservation of proximity privacy in publishing numerical sensitive data[END_REF]. A proximity breach occurs when the adversary predicts a short interval for an individual's numeric sensitive attribute's value but not the exact value for the sensitive value itself.

( , m)-anonymity

The ( , m)-anonymity definition is a refinement to (k, e)-anonymity to overcome a proximity breach, and similarly, is only applicable to sensitive attributes having numerical values. The ( , m)-anonymity requires that given an equivalence class e, for every sensitive value sv i ∈ e, then at most 1/m of the tuples in e can have sensitive values 'similar' to sv i . The factor of quantifies the similarity. The authors list two ways to quantify the numerical similarity between two numerical values of sensitive attributes [START_REF] Li | Preservation of proximity privacy in publishing numerical sensitive data[END_REF]: two values are similar if their absolute difference is less than the parameter , i.e. |sv isv j | ≤ , and relative similarity where sv i is similar to

sv j if |sv i -sv j | ≤ sv j • .

Multi-relational k-anonymity

Most of the privacy definitions examined above deal with a single relation. Multi-relational kanonymity defines privacy for cases involving multiple relations by modifying k-anonymity to accommodate multiple relations settings. The multi-relational k-anonymity privacy assumes that there exists a Person-specific Relation T per with respect to a population U such that T per has identifiers (primary key attribute or set of attributes) that uniquely correspond to an individual in population U. Given a set of relations T 1 , T 2 , . . . , T n , containing foreign keys along with quasiidentifiers as well as sensitive attributes. The notion of multi-relational k-anonymity is to apply k-anonymity at owner level instead of the record level. As there can be many records, spreading over multiple relations, belonging to a single owner. Multi-relational k-anonymity requires that for each record owner r id in the join of all relations, i.e. T per T 1 T 2 . . . T n , there are k -1 other record owners with the same quasi-identifier values [START_REF] Nergiz | Multirelational k-anonymity[END_REF].

δ-disclosure privacy

The delta-disclosure privacy definition can be considered a more restrictive version of t-closeness.

Given a set of quasi-identifiers QI ∈ Attr \SenAttr then tuples r i and r j are quasi-identifier

equivalent if r i [QI] = r j [QI]
. The relation T can be divided into quasi-identifier equivalence classes as done in k-anonymity. The delta δ-disclosure privacy defines that "an equivalence class e is δ-disclosure-private with respect to the sensitive attribute in S AV if, for all sv i ∈ SAV, log p(e,sv i ) p(T,sv i ) < δ. Where p(X, sv i ) is the probability that a randomly chosen member of X has sensitive attribute value sv i ." A relation T is δ-disclosure private if for every e ∈ E is δ-disclosure private [START_REF] Brickell | The cost of privacy: destruction of data-mining utility in anonymized data publishing[END_REF]. However, the δ-disclosure privacy definition is too strong for practical reasons because an equivalence class may not be able to cover all the sensitive attribute values.

Differential privacy ( -differential Privacy)

Differential privacy requires that any given disclosure is, within a small multiplicative factor that is , just as likely regardless of whether or not the individual's record in the relation [START_REF] Dwork | Differential privacy: A survey of results[END_REF].

Intuitively, consider two datasets DS 1 and DS 2 , only differing is in one record. Res 1 and Res 2 are the result of query Q to DS 1 and DS 2 . Res 1 and Res 2 must be indistinguishable from each other in order to fulfil differential privacy requirement. This is usually achieved by the addition of noise to the query results.

Many differential private algorithms have been proposed [START_REF] Geng | The optimal mechanism in differential privacy[END_REF][START_REF] Mcsherry | Mechanism design via differential privacy[END_REF][START_REF] Li | Optimizing linear counting queries under differential privacy[END_REF][START_REF] Hardt | A simple and practical algorithm for differentially private data release[END_REF][START_REF] He | Differential private noise adding mechanism: Fundamental theory and its application[END_REF][START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. Differentially private algorithms are usually designed for interactive query settings; however, with a limitation that they answer only a limited number of queries -governed by privacy budget. The privacy budget regulates that number of queries after which the answers to the queries no longer considered free from privacy risk. Additionally, in general, differential privacy works for statistical databases. Statistical databases deal with aggregates, in contrast with microdata release. In some scenarios the amount of noise added to the output degrades the utility of the data [START_REF] Simson | Issues encountered deploying differential privacy[END_REF].

Besides the reviewed definitions the privacy literature encompasses many formal privacy definitions and models including integral privacy [START_REF] Aligon | Similarity measures for olap sessions[END_REF], (X,Y)-privacy [START_REF] Wang | Anonymizing sequential releases[END_REF], and β-likeness [START_REF] Cao | Publishing microdata with a robust privacy guarantee[END_REF].

Summary

This paper reviewed some of the definitions of anonymity. Observations from the literature are summarized as follows:

• k-anonymity as a foundation: k-anonymity being one of the first privacy definitions, provided a foundation to further privacy research. Several privacy definitions are based on k-anonymity.

• Majority of the definitions are for one-time publication: the privacy literature encompasses a large number of privacy definition, mainly for one-time publication of a single relation [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF][START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF][START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF][START_REF] Raymond | α, k)-anonymity: An enhanced k-anonymity model for privacy preserving data publishing[END_REF][START_REF] Wang | Anonymizing sequential releases[END_REF][START_REF] Xiao | M-invariance: Towards privacy preserving re-publication of dynamic datasets[END_REF][START_REF] Li | Preservation of proximity privacy in publishing numerical sensitive data[END_REF][START_REF] Mehmet Ercan Nergiz | Hiding the presence of individuals from shared databases[END_REF][START_REF] Brickell | The cost of privacy: destruction of data-mining utility in anonymized data publishing[END_REF].

• Research lacks privacy definitions supporting interactive query settings for microdata release: the privacy research lacks privacy definitions and mechanisms that work in interactive setting. While differential privacy supports interactive queries, the mechanisms are constrained in the number of queries permitted, and secondly, it allows aggregate queries instead of microdata (row-level data), in some scenarios the amount of noise added degrades the utility of the data.

• Susceptibility to attacks: privacy definitions have a level of susceptibility to attacks.

There exist vulnerabilities and scenarios where the privacy restriction laid down by the privacy definition is met, but privacy is compromised. Their weaknesses are widely studied in the literature; for instance, the paper from Josep Domingo-Ferrer and Vicenc ¸Torra have discussed the shortcomings of well-known syntactic privacy models in [START_REF] Domingo-Ferrer | A critique of k-anonymity and some of its enhancements[END_REF]. Therefore, novel ways to detect these privacy attacks are always desirable.

• Building privacy-preserving interactive query mechanism -a challenge: in the present era of big data and data analytics, approaches supporting unlimited interactive querying along with permitting the queries to return microdata while preserving privacy is desirable. Therefore, weaker notions of privacy for interactive query settings for microdata release are potential starting point. However, development interactive query settings for microdata release is a challenging task as multiple releases may give rise to inferences being made by an adversary.

Conclusions

The privacy literature encompasses a large number of privacy definitions, mainly for one-time publication of a single relation. Most of these definitions are evolved from k-anonymity. kanonymity and differential privacy can be considered the two mainstream definition of privacy.

The privacy research lack privacy definitions and mechanisms that works for interactive settings for microdata release. Privacy definitions, in various scenarios, are susceptible to attacks -where privacy definitions are met, but still the privacy is compromised. Therefore, novel ways to detect these privacy attacks are also desirable.

  The next section looks further into the formal definitions of privacy research proposed in the literature to achieve anonymization in the context of databases.Section 2 examines well-known formal privacy definitions proposed in the literature to achieve anonymization in the context of databases. Section 3 presents the key observations gathered from the literature. Conclusions are drawn in Section 4.

Figure 1 :

 1 Figure 1: The state of Data protection and privacy legislation worldwide [14].

  example of an identifier is the Personal Public Service Number (PPS Number) which can uniquely identify individuals in Ireland. Other examples include an individual's passport number, driving license number, and e-mail address.

  suitable for the scenario where the relation is to be released once only. Second or subsequent releases of the relation (with an updated record or insertion of a new record) may lead to inferences.The m-invariance definition[START_REF] Xiao | M-invariance: Towards privacy preserving re-publication of dynamic datasets[END_REF] states that "an anonymized relation T is m-unique if each equivalence class e ∈ T contains at least m set of records (or tuples) and all the records in e must have different sensitive attribute values. The sequence of published relations is said to be m-invariant if all the releases are m-unique, along with the condition that the set of sensitive attribute values for every e in T must remain same for subsequent releases of relation T."

Table 1 :

 1 1 [Country] = ('Spain'). r i [Attr] denotes the tuple (r i [attr 1 ], r i [attr 2 ], . . . , r i [attr n ]) which is the projection of r onto the attributes in Attr for example r 1 [Name, City, Country] = ('Nicolau', 'Barcelona', 'Spain'). An example relation T.

	r i	Name	City	Country
	r 1	Nicolau	Barcelona	Spain
	r 2	Jordi	Barcelona	Spain
	r 3	John	New York	USA
	r 4	Sean	Cork	Ireland
	r 5	Patrick	Dublin	Ireland
	r 6	Matías	Berlin	Germany

Table 2 :

 2

	#	Name	Age	Zipcode	Salary
	1	*	<45	313*	77k
	2	*	<45	313*	77k
	3	*	<45	313*	83k
	4	*	≥50	729*	65k
	5	*	≥50	729*	77k
	6	*	≥50	729*	83k
	7	*	4*	313*	65k
	8	*	4*	313*	65k
	9	*	4*	313*	83k

A relation with Name as an identifier, Age & Zipcode are quasi-identifiers and Salary as a sensitive attribute.

Table 3 :

 3 A 3-anonymized version of Table

Table 4

 4

	#	Name	age	Zipcode	Salary
	7	*	<50	313*	65k
	2	*	<50	313*	77k
	3	*	<50	313*	83k
	4	*	≥50	729*	65k
	5	*	≥50	729*	77k
	6	*	≥50	729*	83k
	1	*	<50	313*	77k
	8	*	<50	313*	65k
	9	*	<50	313*	83k

shows an l-diverse (3-diverse) version of Table

2

, where each equivalence class has three distinct sensitive attribute values.

Table 4 :

 4

	doesn't take the semantic-level closeness of the sensitive attribute values into account and thus
	leads to similarity attacks. For example, in a given equivalence class with the sensitive attribute
	diagnosis. Consider all the values for diagnosis in that given equivalence class are related to
	heart-related diseases. Therefore, an adversary knows someone in that given equivalence class

A l-diverse (3-diverse) version of Table

2

.

In some scenarios it is difficult to achieve l-diversity. Let us say that a relation consisting of 20, 000 records has only one sensitive attribute, Test Results, where Test Results can take either negative or positive value. If 99.75% of the Test Results are positive, while 0.25% are negative, then there can be at most 20, 000 * 0.25%= 50 equivalence classes. l-diversity is susceptible to a skewness attack and similarity attack

[START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF]

. Consider a class with 9 positive values and 1 negative value, and another class with 9 negative values and 1 positive value, both classes are 2-diverse but present different privacy risks -skewness attack. l-diversity then the adversary concludes that the individual has heart-related disease.


Dominique Lavenier
email: lavenier@irisa.fr

Ordered Index Seed Algorithm for Intensive DNA Sequence Comparison

This paper presents a seed-based algorithm for intensive DNA sequence comparison. The novelty comes from the way seeds are used to efficiently generate small ungapped alignments -or HSPs (High Scoring Pairs) -in the first stage of the search. W-nt words are first indexed and all the 4 W possible seeds are enumerated following a strict order ensuring fast generation of unique HSPs. A prototype -written in C -has been realized and tested on large DNA banks. Speed-up compared to BLASTN range from 5 to 28 with comparable sensitivity.

Introduction

Comparing DNA sequences is one of the basic tasks in computational biology, either for mining genomics database, or for filtering mass of data involved in the first steps of complex bioinformatics workflows. With the continuous increasing of genomic data, and the relative stagnation of microprocessor frequencies, faster algorithms for manipulating huge volume of data, and especially DNA banks, need to be investigated.

The first algorithm for comparing genomic sequences is due to Needleman and Wunsch in 1970 [START_REF] Needleman | A general method applicable to the search for similarities in the amino acid sequence of two proteins[END_REF]. It is based on dynamic programming techniques and allows the user to globally align two sequences. In 1981, Smith and Waterman proposed a modified version for computing local alignments between two sequences [START_REF] Smith | Identification of common molecular subsequences[END_REF]. The following year, this famous algorithm has been improved by Gotoh to include affine gap costs for better representing biological reality [START_REF] Gotoh | An improved algorithm for matching biological sequences[END_REF]. This family of algorithms is optimal: they provide the best alignments.

However, their quadratic complexity constitutes a serious barrier when dealing with large volume of data, due to the high computational power involved by dynamic programming techniques. In the late 80's, a powerful heuristic based on seeds as been introduced and rapidly adopted by the scientific community through the FASTA and BLAST software [START_REF] Pearson | Improved tools for biological sequence comparison[END_REF] [START_REF] Altschul | Basic local alignment search tool[END_REF].

Basically, this heuristic assumes that the two sequences (or part of the sequences) from which an alignment has been found share a common word of W characters. Thus, instead of scanning the whole search space (as it is done with dynamic programming), the search can only focus on these specific anchoring points. The consequence is a drastic reduction of the computation time, allowing biologists to run these algorithms on large DNA or protein banks. On another hand, this heuristic doesn't guaranty to detect the best alignments. Practically, it reports most of the alignments and satisfies common bioinformatics needs. In addition, the heuristic can be tuned by modifying the length of the seed according to a specified sensitivity.

To improve sensitivity, current research aims at selecting the best seeds: instead of considering a seed as a word of W contiguous characters, a word of W no necessarily consecutive characters may be considered. These seeds, referred as spaced-seeds, significantly increase the sensitivity. They have been implemented in software such as PatternHunter [START_REF] Li | PatternHunterII : Highly Sensitive and Fast Homology Search Bioinformatics[END_REF] or, in a more elaborate form, by Yass [START_REF] Noe | Yass: enhencing the sensitivity of DNA similarity search[END_REF]. The next step is not only to consider one seed, by a set of several seeds which can be of different length and possibly made of different spaced-seeds (multiple seeds) [START_REF] Xu | Optimizing multiple spaced seeds for homology search[END_REF]. Another seed family (subset-seeds) group different characters in the same set [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF], still providing better expressiveness.

On this domain, the research activity is dynamic and contributes to significantly increase the sensitivity and, consequently, to narrow the gap with dynamic programming approach while offering short computation time.

This paper introduces a new way of manipulating seeds, not foccusing on a better sensitivity, but targeting a faster execution time. We address the problem of intensive DNA sequence comparison, such as the comparison of two DNA banks, or comparison of full genomes. Scans of DNA banks are not considered since, in this situation, the computation time is mostly determined by I/O capabilities of the system (fast access to mass storage).

Basically, the algorithm follows the traditional scheme of seed-based algorithms: hit detection, ungapped extension and gapped extension. The difference, compared to other approaches, is that these operations are globally and sequentially performed thanks to seed indexing and seed ordering techniques.

More precisely, seeds of the two banks are first indexed, allowing an immediate anchoring of there positions. From these seed positions, and following a seed criteria ordering (lowest to highest), an ungapped extension is started. During this process, if a seed smaller than the starting one is encountered, the process immediately stops. It means that this ungapped alignment has already been detected and doesn't need to be processed again.

Compared to usual seed-based algorithms, this approach provides shorter execution times. Reasons are:

• It extensively uses cache memory of processors: all the portions of sequence having the same seed are implicitly and simultaneously moved into the cache memory to perform fast pairwise comparisons (computation of ungapped alignments -or HSPs);

• Index ordered seed technique delivers unique HSPs avoiding complex data structure to be manipulated and saving time of search functions.

Compared to NCBI BLASTN, speed-up from 5 to 28 are obtained with comparable sensitivity. These results have been measured on a standard 3Ghz Cpre 2 Duo Intel processor with 2 Gbytes of memory when processing DNA banks ranging from 5 to 130 Mbp.

The rest of the paper is organized as follows: Section 2 describes the ordered index seed algorithm. Section 3 presents results from a C prototype software, named SCORIS-N. Section 4 concludes and gives perspectives of this work.

Algorithm principles

The Ordered Index Seed algorithm (ORIS) proceeds in 4 successive steps as shown figure in 1. Step 1 indexes the two banks, step 2 performs hit extensions, step 3 computes gap alignments and step 4 displays alignments. Each step of the ORIS algorithm is now detailed in the following sections.

Step 1: Bank indexing

Bank indexing is directly performed from FASTA format input files. DNA sequences are stored together with an indexing structure to rapidly locate W character seeds. Figure 2

codeSEED(S) = i<W i=0 4 i × codeN T (S i )
where S i is the i th character of the seed S. The function codeN T provides the following 2-bit nucleotide code:

A C G T 00 01 11 10
This encoding allows the seed to be ordered in a non ambiguous way. SA will be lower than SB if codeSEED(SA) < codeSEED(SB).

C A G A A A A A T T T C C C G G G G G G C C C W 4 seed dictionary char *SEQ int *INDEX Figure 2.

structure of the bank index

To eliminate non interesting alignments made of small repeats, a low complexity filter can be activated before indexing. In that case, W character words belonging to lowcomplexity regions are discarded from the index.

Step 2: Hit extensions

The goal of this step is to find all the HSPs (ungapped alignments) between two banks. It is done by considering all possible seeds, starting from the lowest one.

For a particular seed S, all the positions where it occurs in bank1 and in bank2 are examined. If X 1 and X 2 are respectively the number of occurrences in bank1 and bank2, then there are X 1 × X 2 hit extensions to compute.

As we globally compute all the ungapped alignments before extending them with gap, we don't want multiple detections of the same ungapped alignment. As an example, consider the following ungapped alignment generated from the seed AACTGTAA: Latter on, when the seed AATTGCTC is considered, the same ungapped alignment will be generated: To avoid this situation (generating and storing many times the same alignment), the extension process compares the code of each potential seed able to produce a hit with the code of the originate seed. If a seed with a lower code is encountered the process stops and no alignment is reported. The ungapped extension algorithm (left side only) is given below: The extend_left function takes as input two char pointers (s1) and (s2) which are supposed to point to the first character of the seed on both sequences, and one integer value (length) specifying the maximum search space. The while loop computes a score and has three exiting possibilities:

1. the search space has been fully explored (l>=length);

2. the XDROP threshold has been reached (maxi-score>=XDROP);

3. the current seed code is lower than the strating seed code (line 18).

The two first conditions allow the function to return the maximun value of the score. The third condition is based on the comparison of a current seed value (codeSD(ss1)) with the code of the seed hit (codeSEED(s1)). A current seed code is valid only if a hit exists at that position: the previous SIZE_SEED characters must be identical on both sequences. This condition is tested thanks to the L variable which counts the number of identical successive characters (line 16). This variable is reset to zero when a mismatch occurs (line 23). The same type of function is applied to perform the right extension.

This simple test (comparison of the starting seed with a current potential seed) ensures that unique HSPs are generated. This is the key point of the ORIS algorithm. Without such a condition the same HSP would be produced in multiple copies, leading to add a costly procedure to suppress all the duplicates.

For large DNA banks, step 2 represents a high volume of computation. However, the way data are computed limits the execution time, mainly for two reasons:

• Even if the index structure represents hundred of mega bytes of data, the nested loops provide a very high data re-used, allowing the processor memory cache to be fully exploited. In that case, ALUs are fed with data at a very high rate, without latency due to cache misses.

• The ungapped extension procedure is fast since it is aborted as soon as the seed order condition becomes false.

Finally, step 2 stores all the HSPs overpassing a threshold value (figure 1, line 10). Actually, the storage is made by sorting the HSPs by diagonal number to optimize data access of the next step.

Step 3: Gapped alignments

From the set of HSPs computed during step 2, the goal of step 3 is to build gapped alignments. Such alignments are constructed starting from the middle of an HSP and performing an extension on both extremities by dynamic programming techniques. The extension is controlled by an XDROP value in order to stop when the score of the alignment significantly decrease. The final alignment consists in merging the right and left gapped extensions. Alignments are stored in the T ALIGN structure and also sorted by diagonal number.

As a gapped alignment may contain several HSPs, including HSPs detected during the step 2, a test is done before starting an extension (line 14, fig 1). A gapped extension will be done only if an HSP does not belong to a gapped alignment previously computed and stored in the T ALIGN structure. This test is fast since both HSPs and gapped alignments are sorted using the same criteria (diagonal number). To compute gapped alignments, HSPs are serially taken by increasing order of their diagonal number, leading to product alignments having the same increasing order, and nearly the same diagonal numbers. Thus, testing this condition does not involve time consuming search on the data structure due to the locality of the data (HSPs and gapped alignments).

At the end of this step, the T ALIGN structure contains a complete set of the gapped alignments found between two DNA banks.

Step 4: Alignment display

The last step consists in producing an output file to display the results. The alignments are first sorted on the T ALIGN structure according to a chosen criteria, for example the expected value attached to each alignment.

Experiments

The ORIS algorithm has been prototyped in C language for comparing two DNA banks ranging from short DNA sequences (such as EST) to full chromosomes of a few tens of Mbp. This section briefly presents the ORIS implementation, then compares performances with the NCBI BLAST software both on sensitivity and execution time.

ORIS Implementation

In the following, the ORIS implementation for comparing DNA sequences will be referred as SCORIS-N (Sequence Comparison using ORIS algorithm on Nucleotides). As we target intensive sequence comparison, the SCORIS-N program takes as input two DNA banks (FASTA format). A bank can either be a large set of DNA sequences or a single DNA sequence representing a full chromosome. The size of the bank which depends of the size of the available memory on the computer. The index structure required for storing a bank of size N (N is the number of nucleotides) is approximately equal to 5 × N bytes. Comparing, for example, two chromosomes of 40 MBytes will require, at least, a free memory space of 400 MBytes.

An expected value is attached to each alignment in order to sort the results according to this criterion. The SCORIS-N program considers the size of the first bank and the size of the sequence from which the alignment is found in the second bank as parameters to compute the expected value.

As intensive sequence comparison is targeted, the output format -in the current version -does not report full the alignments. It only displays the alignment features as it is done in the -m 8 option of BLASTN. Moreover, this output format is better suited for further automatic processing than the standard BLASTN output.

The program has been written in standard ANSI C, compiled with the gcc standard options and tested on a LINUX environment on a 3 GHz Core 2 duo Intel processor with 2 GBytes of memory (Dell Precision 390).

Data set

The following table gives the characteristics of the DNA banks we have used for testing SCORIS-N: EST banks are made by randomly sampling the Gen-Bank EST division.

Execution time

Execution times have been measured using the LINUX command time and by extracting the user time. To compare performance with the NCBI BLAST software (release 2.2.17, nov. 2007), blastall has been run as follows:

blastall -p blastn -d A -i B -o R -m 8 -e 0.001 -S 1 A and B are the two DNA banks. R is the output file storing the alignment features using the m8 BLAST format. The expected value has been set to 10 -3 which is a reasonable value in the context of intensive DNA sequence comparison. The -S 1 option indicates that the search is done on a single strand only. Currently, the SCORIS-N prototype doesn't perform search on the complementary strand. The priority was first to demonstrate the efficiency of the algorithm. This option will come later, in a new release.

Figure 3 shows the execution time of BLASTN and SCORIS-N, when EST banks are compared to each other. It can be seen that SCORIS-N is much faster, and that the difference grows with the size of the banks.

The two following tables give speed-up as a function of the search space determined as the product of the size of two banks (in Mbp). When comparing large sequences, speed-up is less impressive, mostly because in that situation BLASTN performs well.

Sensitivity

Both SCORIS-N and BLASTN programs generate alignments using the same output format (-m 8 option). This format provides the main characteristics of an alignment on a single text line such as its coordinates, its identity percentage, its length, its score, its expected value, etc. From this basic information, it is straightforward to compare two different output files to detect if identical alignments are generated or not.

We consider that two alignments are equivalent if they overlap of more than 80 %. Based on this metric, we define the following values:

• SC total = number of alignments found by SCORIS-N

• BL total = number of alignments found by BLASTN

• SC miss = number of alignment missed by SCORIS-N compared to BLASTN

• BL miss = number of alignment missed by BLASTN compared to SCORIS-N These values are computed as follows: SC total and BL total are the number of alignments generated respectively by the programs SCORIS-N and BLASTN. If an alignment found by BLASTN is not found by SCORIS-N, then SC miss is incremented. In the same way, if an alignment found by SCORIS-N is not found by BLASTN, then BL miss is incremented.

We can then deduced the percentage of missed alignments according to a reference program: The number of alignments generated by both programs are similar and missed alignments represent a small fraction of the total number of found alignments. A closer look to the missing alignments shows that they predominantly represent alignments with low score, with an expected value very close to the threshold value given by the user. There are probably slight differences in the computation of this information, leading to reject borderline alignments. Other causes of differences may come from:

SCORIS miss =
• the complexity filter: the SCORIS-N low complexity filter presents some difference [START_REF] Morgulis | A fast ans dymetric DUST implementation to mask low-complexity DNA sequences[END_REF] with the dust filter included in BLASTN;

• the gapped and ungapped extension procedures have been rewritten and tuned for maximal performances. Small differences exist, especially for deciding if it is worth to continue the extension.

However, there are some alignments of interest found by BLASTN and not reported by SCORIS-N. These align-ments both include a significant number of gaps near the anchoring seed and many substitution errors forbidding other 11-nt seeds to occur. In that specific cases, SCORIS-N is unable to generate valid HSPs.

To partially remedy this problem, an asymmetric indexing is done on 10-nt words. Asymmetric means that for one of the two input bank, only half words are considered. From a sensitivity point of view, this is a little bit more efficient than a 11-nt indexing. All 11-nt seeds are detected together with an average of 50% of the 10-nt seed anchoring.

The For this type of treatment, the difference between SCORIS-N and BLASTN is small. Again, the difference mainly comes from short alignments having an expected value closed to the threshold value.

Conclusion and Perspectives

A new algorithm, called ORIS (ORdered Index Seed), targetting intensive DNA sequence comparison has been presented. It requires the banks to be indexed into the main memory of the computer before enumerating all the possible seeds in a well defined order. Ungapped extensions directly benefit of this scheme avoiding unecessary computations. The locality of the computation allows an intensive use of the memory cache, fastening the data access and, consequently the whole execution time.

A program, called SCORIS-N, has been prototyped in C to evaluate performances compared to the standard NCBI BLASTN program. Speed-up from 5 to 28 has been measured for comparable sensitivity. Next step is to provide a new version to minimize the difference between BLASTN and SCORIS-N. This is important since BLASTN is today the reference when comparing DNA sequences.

The SCORIS-N algorithm still need more investigation, such as:

• Comparing SCORIS-N with other programs which have also been designed for dealing with large DNA sequences and which also handle sequence indexing into main memory (BLAT [START_REF] Kent | BLAT: The BLAST-Like Alignment Too[END_REF], FLASH [START_REF] Califano | FLASH: A Fast Look-up Algorithm for String Homology[END_REF], BLASTZ [START_REF] Schwartz | Human-Mouse Alignments with BLASTZ[END_REF]);

• Considering bigger treatments involving pairwise comparisons on larger sequences (full genomes) for monitoring the way the SCORIS-N algorithm behave. However, testing such computation will require systems having large memory;

• Testing SCORIS-N on genomes having a large number of repeat sequences. Generally, algorithm performances are not so good when dealing with these specific sequences.

The structure of the algorithm is also well suited for fine grained parallelism, especially step 2 and step 3. As a matter of fact, the outer loop of step 2 which considers all the possible 4 W seeds can be run in parallel since seed order prevents identical HSPs to be generated. The two inner loops can also be highly parallelized as the ungapped extensions refer to independent computations. There is then a very high potential of parallelism which can be exploited on the new generation of processors, especially on the multicore architectures.

Other possibilities is to deport step 2 and/or step 3 to dedicated hardware such as FPGA boards or GPU of new generations (Graphical Processing Units) which can now be programmed for general purpose computing (GP-GPU). Compared to the standard NCBI BLASTN program, the structure of SCORIS-N, composed of several distinct steps, makes it suitable for hardware accelerators: each step, and especially, step 2 and step 3, refers to very specific and highly parallel treatments.

Even if the first prototype of the SCORIS-N program provide significant speed-up on today processors, there are still plenty of room for further investigations on the new generations of processors. Particularly, we think that we can highly parallelize the ORIS algorithm with a very high scalability on various platforms ranging from multi-core architectures to stream processing paradigm (GP-GPU).

Figure 1 .

 1 Figure 1. Structure of the ORdered Index Seed (ORIS) algorithm. It proceeds in four separate steps: (1) indexing, (2) ungapped extension, (3) gapped extension, and (4) display of sorted alignments

  ... ATATGATGTGC AACTGTAA TTGCTCAGATTCTATG ... ||||||||||| |||||||| ||||||||||||| || ... ATATGATGTGC AACTGTAA TTGCTCAGGTTCTCTG ...

  ... ATATGATGTGCAACTGT AATTGCTC AGATTCTATG ... ||||||||||||||||| |||||||| ||||||| || ... ATATGATGTGCAACTGT AATTGCTC AGGTTCTCTG ...

Execution time of SCORIS-N and BLASTN on the EST banks. The X axe is the search space determined as the the product of the size of each bank (in Mbp)

		2000
			SCORIS-N
			BLASTN
		1500
	time (sec)	1000
		500
		0
		0	200	400	600	800	1000	1200
					Search Space (Mbp x Mbp)
	Figure 3. banks	SC total	BL miss	BLAST miss
	EST1 vs EST2	34412	952	2.76 %
	EST1 vs EST3	34660	1050	3.02 %
	EST1 vs EST5	52873	1625	3.07 %
	EST3 vs EST4	173605	5892	3.39 %
	EST1 vs EST7	138281	3816	2.74 %
	EST5 vs EST6	248167	11733	4.72 %
	EST5 vs EST7	438359	18124	4.13 %
								SC miss BL total	× 100
						BLAST miss =	BL miss SC total	× 100
					The two following tables report the percentage of missed
					alignments for various EST bank comparisons:
					banks	BL total	SC miss	SCORIS miss
					EST1 vs EST2	34286	1137	3.31 %
					EST1 vs EST3	34865	931	2.67 %
					EST1 vs EST5	53426	1920	3.59 %
					EST3 vs EST4	172325	4986	2.89 %
					EST1 vs EST7	134170	4129	3.07 %
					EST5 vs EST6	247533	9669	3.90 %
					EST5 vs EST7	436635	15682	3.56 %

  next tables compare sensitivity for large DNA sequences

	banks	BL total	SC miss	SCORIS miss
	BCT vs EST7	2017	16	0.79 %
	BCT vs VRL	1293	10	0.77 %
	H10 vs VRL	490107	626	0.12 %
	H19 vs VRL	530650	563	0.10 %
	H10 vs BCT	0	0	-
	H19 vs BCT	11	0	0.00 %
	banks	SC total	BL miss	BLAST miss
	BCT vs EST7	1823	26	1.42 %
	BCT vs VRL	1240	7	0.56 %
	H10 vs VRL	503550	75	0.01 %
	H19 vs VRL	543170	5	0.00 %
	H10 vs BCT	0	0	-
	H19 vs BCT	11	0	0.00 %