Erich Brendel

Matthias Ludwig

Chetan Lathia

Caroline Robert

Stanislas Ropert

Jean-Charles C Soria

Jean-Pierre P Armand

Pharmacokinetic results of a phase I trial of sorafenib in combination with dacarbazine in patients with advanced solid tumors

Keywords: Sorafenib, Dacarbazine, AIC, Pharmacokinetics, Phase I

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

Tel: +49 202 36 8794; Fax: +49 202 36 3998 e-mail address: erich.brendel@bayerhealthcare.com

Introduction

Sorafenib is a multikinase inhibitor of Raf, vascular endothelial growth factor (VEGF) receptors, and platelet-derived growth factor receptors [START_REF] Wilhelm | Preclinical overview of sorafenib, a multikinase inhibitor that targets both Raf and VEGF and PDGF receptor tyrosine kinase signaling[END_REF][START_REF] Wilhelm | BAY 43-9006 exhibits broad spectrum oral antitumor activity and targets the RAF/MEK/ERK pathway and receptor tyrosine kinases involved in tumor progression and angiogenesis[END_REF]. It has been approved as a single agent by the US Food and Drug Administration (FDA) and the European Medicines Agency (EMEA) for the treatment of advanced renal cell carcinoma and unresectable hepatocellular carcinoma. In addition, sorafenib is being tested in combination with other agents in a variety of advanced solid tumors such as melanoma, breast cancer, renal cell carcinoma, hepatic cancer, and non-small cell lung cancer [START_REF] Duran | Phase I targeted combination trial of sorafenib and erlotinib in patients with advanced solid tumors[END_REF][START_REF] Kupsch | Results of a phase I trial of sorafenib (BAY 43-9006) in combination with oxaliplatin in patients with refractory solid tumors, including colorectal cancer[END_REF][START_REF] Mross | Results from an in vitro and a clinical/pharmacological phase I study with the combination irinotecan and sorafenib[END_REF][START_REF] Richly | Results of a Phase I trial of sorafenib (BAY 43-9006) in combination with doxorubicin in patients with refractory solid tumors[END_REF][START_REF] Siu | Phase I trial of sorafenib and gemcitabine in advanced solid tumors with an expanded cohort in advanced pancreatic cancer[END_REF][START_REF] Ryan | Sorafenib with interferon alfa-2b as first-line treatment of advanced renal carcinoma: a phase II study of the Southwest Oncology Group[END_REF][START_REF] Gollob | Phase II trial of sorafenib plus interferon alfa-2b as first-or second-line therapy in patients with metastatic renal cell cancer[END_REF][START_REF] Escudier | Phase I trial of sorafenib in combination with IFN alpha -2a in patients with unresectable and/or metastatic renal cell carcinoma or malignant melanoma[END_REF][START_REF] Adjei | Phase I trial of sorafenib in combination with gefitinib in patients with refractory or recurrent non-small cell lung cancer[END_REF][START_REF] Gridelli | A randomized phase II study of sorafenib/gemcitabine or sorafe nib/erlotinib for advanced non-small-cell lung cancer in elderly patients or patients with a performance status of 2: treatment rationale and protocol dynamics[END_REF][START_REF] Agarwala | Randomized phase III study of paclitaxel plus carboplatin with or without sorafenib as second-line treatment in patients with advanced melanoma[END_REF][START_REF] Mcdermott | Double-blind randomized phase II study of the combination of sorafenib and dacarbazine in patients with advanced melanoma: a report from the 11715 Study Group[END_REF][START_REF] Azad | Combination targeted therapy with sorafenib and bevacizumab results in enhanced toxicity and antitumor activity[END_REF][START_REF] Richly | Results of a phase I trial of BAY 43 -9006 in combination with doxorubicin in patients with primary hepatic cancer[END_REF]. Dacarbazine is the most commonly used FDA-and EMEAapproved chemotherapeutic agent for the treatment of advanced melanoma.

Dacarbazine is metabolized by various cytochrome P450 (CYP) isoenzymes such as CYP1A2, CYP1A1, and CYP2E1 [START_REF] Reid | Metabolic activation of dacarbazine by human cytochromes P450: the role of CYP1A1, CYP1A2, and CYP2E1[END_REF]. Sorafenib is primarily metabolized in the liver by CYP3A4 [START_REF] Lathia | Lack of effect of ketoconazole-mediated CYP3A inhibition on sorafenib clinical pharmacokinetics[END_REF]. Therefore, concomitant sorafenib administration is not expected to affect dacarbazine metabolism, and the likelihood of a pharmacokinetic (PK) drugdrug interaction between sorafenib and dacarbazine is low.

An earlier phase I study estimated that the maximum tolerated dose of sorafenib in combination with dacarbazine 1,000 mg/m 2 was 400 mg twice daily (the standard single-agent doses for each agent) [START_REF] Eisen | Phase I trial of BAY 43-9006 (sorafenib) combined with dacarbazine (DTIC) in metastatic melanoma patients[END_REF]. The primary objective of this study was to evaluate the PK profiles of dacarbazine with and without concomitant sorafenib under steady-state conditions. A secondary objective was to determine the steady-state PK profiles of sorafenib and its metabolites BAY 67-3472 (M2), BAY 43-9007 (M4), and BAY 68-7769 (M5) in the presence of dacarbazine. This paper reports on PK and safety data. A separate manuscript (in preparation) [START_REF] Soria | Sorafenib (S) and dacarbazine (D) combination in patients (pts) with advanced malignant solid tumors: Phase I study with tumor biopsy genomic analysis and dynamic contrast enhanced ultrasonography (DCE-US)[END_REF] reports on efficacy and functional analysis using dynamic contrast-enhanced ultrasonography (DCE-US) representing the blood volume and microarray analyses of gene expression obtained in sequential tumor biopsies.

Patients and methods

Patients

Patients with metastatic, histologically confirmed solid tumors were included in this study. Eligible patients had at least one lesion that could be accurately and serially measured per Response Evaluation Criteria in Solid Tumors (RECIST) guidelines [START_REF] Therasse | New guidelines to evaluate the response to treatment in solid tumors. European Organization for Research and Treatment of Cancer, National Cancer Institute of the United States, National Cancer Institute of Canada[END_REF]; were ≥18 years of age with an Eastern Cooperative Oncology Group (ECOG) performance status of 0 or 1; had adequate bone marrow, liver, and renal functions ;

Study outcomes

The primary endpoint was determination of the PK profile of dacarbazine with and without sorafenib. Secondary endpoints included evaluation of the PK profile of sorafenib in the presence of dacarbazine, safety and efficacy of the combination treatment, novel biomarker analyses using DCE-US, and gene profile analyses. This paper reports on PK and safety data; the other results are reported in a separate manuscript (in preparation) [START_REF] Soria | Sorafenib (S) and dacarbazine (D) combination in patients (pts) with advanced malignant solid tumors: Phase I study with tumor biopsy genomic analysis and dynamic contrast enhanced ultrasonography (DCE-US)[END_REF].

Pharmacokinetic variables and sampling schedules

Dacarbazine is a prodrug from which the active alkylating moiety methane diazohydroxide is formed by metabolization. In this metabolic process, the inactive metabolite is 5-amino-imidazole-4-carboxamide (AIC) that is formed in equimolar quantities as methane diazohydroxide, which cannot be analytically measured [START_REF] Reid | Metabolic activation of dacarbazine by human cytochromes P450: the role of CYP1A1, CYP1A2, and CYP2E1[END_REF].

Therefore, in addition to the PK of dacarbazine, we also studied the PK of AIC to understand the changes in the exposure of the active alkylating moiety in the presence of sorafenib.

On day 1 of cycle 1, plasma samples were obtained prior to dacarbazine administration and at 0.5, 1.0, 1.25, 1.5, 2.0, 4.0, 8.0, 12.0, and 24.0 h following dacarbazine administration to assess the PK of dacarbazine and AIC in the absence of sorafenib. On day 1 of cycle 2, samples were collected from the same patients to assess the PK of dacarbazine in the presence of sorafenib at the same time points as above. Additional samples were collected at the same time points on day 1 of cycle 2 prior to sorafenib dosing and at 0.5, 1.0, 2.0, 4.0, 8.0, 10.0, and 12.0 h thereafter to evaluate the PK profile of sorafenib and its main metabolites, M2, M4, and M5 in the presence of dacarbazine. Samples for dacarbazine measurements were stored at or below -70°C; samples for sorafenib measurements were stored below -15°C.

Stability data indicated that all analytes were stable during analysis.

The following PK variables were determined for dacarbazine and AIC on day 1 of cycle 1 and day 1 of cycle 2: area under the plasma concentration-time curve (AUC) from zero to infinity after a single dose [AUC(0-inf)], AUC from time zero to the last data point [AUC(0-tn)], maximum concentration of drug in plasma (C max ), time to reach maximum drug concentration in plasma (t max ), and apparent terminal half-life (t 1/2 ). The following variables were determined for sorafenib, M2, M4, and M5 on day 1 of cycle 2: AUC from time zero to 12 hours after dose at steady state [AUC(0-12) ss ], AUC(0-12) ss normalized with respect to dose (in mg) per kg body weight [AUC(0-12) ss,norm ], C max at steady state (C max,ss ), C max,ss normalized with respect to dose (in mg) per kg body weight (C max,ss,norm ), and t max at steady state (t max,ss ).

Pharmacokinetic assay methods and analyses

All analytes i n plasma samples were quantified using a fully validated liquid chromatography-tandem mass spectrometry assay method with a lower limit of quantification of 40.6 µg/L for dacarbazine, 40.7 µg/L for AIC, and 0.01 mg/L for sorafenib and its metabolites. The assay for each sample set was performed once.

Mean inter-assay precision ranges as determined by analysis of quality control samples were 7.0-8.7% for dacarbazine, 2.8-9.3% for AIC, 1.5-12.4% for sorafenib, 2.6-4.5% for M2, 3.9-5.2% for M4, and 3.2-6.7% for M5. Corresponding mean interassay accuracy ranges were 97.1-104.7% for dacarbazine, 99.3-105.3% for AIC, 102.3-107.0% for sorafenib, 97.9-103.2% for M2, 98.1-100.3% for M4, and 95.5-101.0% for M5. The parameters AUC, AUC(0-tn), and C max of dacarbazine and AIC were analyzed after logarithmic transformations applying an analysis of variance assuming a log-normal distribution.

Safety

Safety was evaluated in all patients who had received at least one dose of either study treatment. Safety was assessed through observed adverse events (AEs) and results of physical examination, laboratory tests, and vital signs measurement. Safety assessment took place at baseline and weekly starting from day 1 of cycle 1. AEs were coded and graded using version 3.0 of the National Cancer Institute Common Toxicity Criteria.

Determination of sample size

As this was a descriptive PK and safety phase I study, no formal sample size estimation was performed. The planned enrolment of approximately 25 patients was based on the requirements of relevant PK data sampling in a phase I trial.

Results

The study enrolled 24 patients, one of whom developed progressive disease before study treatment. The remaining 23 patients underwent treatment and were evaluable for safety analysis. Twenty-one patients (91%) discontinued treatment owing to progressive disease and two patients (9%) discontinued owing to AEs. Complete PK data were available for 15 patients. The other 8 patients had incomplete or no PK data on sorafenib and/or dacarbazine and were not included in the PK evaluation.

The baseline characteristics of patients are reported in Table 1. Detailed dosing and drug exposure data are reported in the supplementary table.

Pharmacokinetics

The 15 patients included in the PK analysis did not undergo any dose modifications during the PK evaluation period. For 13 of the 15 patients, the PK profile of dacarbazine was determined on day 1 of cycle 1 in the absence of sorafenib and repeated on day 1 of cycle 2 following a 20-day treatment period of sorafenib, as planned. For two patients, the second dacarbazine PK sampling was done on day 1 of cycle 3 and day 1 of cycle 6. For all the PK analyses, these were combined with data obtained from other patients on day 1 of cycle 2. Sorafenib PK sampling was performed in all patients during the second dacarbazine PK sampling. Geometric mean plasma concentration-time data for dacarbazine, AIC, and sorafenib are shown in Figures 1a, 1b, and1c, respectively. While plasma concentrations of dacarbazine were slightly lower in cycle 2 at 4 hours after start of infusion and following times when compared with those in cycle 1, the corresponding mean plasma concentrations of AIC were distinctly higher in cycle 2 compared with cycle 1. The apparent t 1/2 of either dacarbazine or AIC was not altered on concomitant administration of sorafenib. Mean plasma concentrations of sorafenib ranged between 1.7 mg/L and 3.0 mg/L. Table 2 summarizes the PK results for dacarbazine and AIC. While the mean AUC and C max of dacarbazine were reduced by 23% and 16%, respectively, mean AUC and C max of AIC were increased by 41% and 45%, respectively, with individual increases of up to 106% and 136%, respectively. The apparent t 1/2 of either compound was not significantly influenced by concomitant administration of sorafenib. Table 3 reports the steady-state PK data for sorafenib and its metabolites.

Sorafenib contributes approximately 83% to the sum of AUC(0-12) ss values, while the metabolites contribute approximately 9% (M2), 4% (M4), and 3% (M5). From the values of the coefficients of variation, it is evident that the PK parameters of sorafenib and its metabolites showed a high degree of variability.

Safety

Overall, toxicities were manageable, with the vast majority of grade 3/4 AEs improving or resolving upon transient study drug dose reduction or discontinuation.

No patient died of treatment-related causes; 10 patients (43.5%) died of progressive disease, 5 within 30 days after the last dose of a study drug and 5 thereafter. Table 4 summarizes the incidence of treatment-emergent AEs related to one or both of the study drugs and affecting at least two patients. The most common grade 3/4 toxicities included amylase or lipase elevation, which was attributed to sorafenib and asymptomatic in all cases. The hematologic toxicities were attributed to both study drugs. The most common drug -related toxicities of any grade were fatigue, nausea, diarrhea, hand-foot skin reaction, and rash/desquamation, each affecting a minimum of just under half of the patients. The most common categories of toxicities of any grade were gastrointestinal (19 patients [83%]), constitutional ( 18patients [78%]), and dermatologic (15 patients [65%]).

In Table 5, we report selected PK parameters of AIC in each of the 15 patients included in the PK analysis and the associated percent changes in hematologic parameters (i.e. platelet, leukocyte, and neutrophil levels). It can be seen that four patients (reference numbers 01, 06, 11, and 14) with grade 4 platelets and grade 3/4 neutrophils showed an increase in C max and AUC(0-inf) of AIC on concomitant sorafenib administration. However, we also see an increased incidence of hematologic toxicities without an associated increase in the C max and AUC(0-inf) on concomitant administration of sorafenib (patients with reference numbers 12 and 13) as well as an increase in C max and AUC(0-inf) without an associated increase in hematologic toxicities (patient with reference number 09).

Discussion

In this paper, we report PK and safety data from the combination of sorafenib and dacarbazine in patients with advanced solid tumors. Our results indicate that while concomitant administration of sorafenib and dacarbazine decreased dacarbazine exposure, it resulted in increased AIC exposure. We also found that increased AIC exposure might be associated with an increased incidence of hematologic toxicities, likely because of the interference of methane diazohydroxide with erythropoiesis [START_REF] Ahmann | Clinical comparison of adriamycin and a combination of methyl-CCNU and imidazole carboxamide in disseminated malignant melanoma[END_REF][START_REF] Gutterman | Chemoimmunotherapy of disseminated malignant melanoma with dimethyl triazeno imidazole carboxamide and bacillus calmette--guerin[END_REF][START_REF] Costanza | Results with methyl-CCNU and DTIC in metastatic melanoma[END_REF]. However, because of the small sample size, no statistically significant correlations between increased AIC exposure and hematologic toxicities could be established. Because of the study design, we could obtain PK profiles of sorafenib and its metabolites only in the presence of dacarbazine. Similar to other studies, we found that the PK parameters of sorafenib and its metabolites showed a high degree of variability [START_REF] Strumberg | Safety, pharmacokinetics, and preliminary antitumor activity of sorafenib: a review of four phase I trials in patients with advanced refractory solid tumors[END_REF]. Our data also show that sorafenib contributes approximately 83% to the sum of AUC(0-12) ss values, while the metabolites contribute approximately 9% (M2), 4% (M4), and 3% (M5). This is comparable with data obtained from previous single-agent studies (data on file, Bayer HealthCare AG).

The combination of sorafenib and dacarbazine was associated with a clinically acceptable toxicity profile, with the vast majority of the grades 3/4 AEs improving or resolving upon transient discontinuation and/or dose reduction of the study drugs. No unexpected serious adverse reactions were reported. The sorafenib-dacarbazine combination has also been investigated in randomized [START_REF] Mcdermott | Double-blind randomized phase II study of the combination of sorafenib and dacarbazine in patients with advanced melanoma: a report from the 11715 Study Group[END_REF] and open-label [START_REF] Eisen | An open-label phase II study of sorafenib and dacarbazine as first-line therapy in patients with advanced melanoma[END_REF] phase II studies, and in another phase I study [START_REF] Eisen | Phase I trial of BAY 43-9006 (sorafenib) combined with dacarbazine (DTIC) in metastatic melanoma patients[END_REF] with similar safety results.

Currently, the combination is being investigated in a phase II trial for sarcoma (Clinicaltrials.gov identifier: NCT00837148)

In conclusion, the combined treatment with sorafenib and dacarbazine may result in an increased exposure to AIC, which may be considered an indicator for the exposure to the active alkylating agent methane diazohydroxide. IDue to the small number of patients in the present study, a statistically significant correlation between AIC exposure and observed hematologic toxicities, even if present, could not be established. Further studies may be necessary to more clearly characterize this potential drug-drug interaction.

  and had a life expectancy of at least 12 weeks. Patients were excluded if they had previous or concurrent cancer that was distinct from the tumor being evaluated in this study, unless the other cancer was curative ly treated more than 3 years prior to study entry; clinically evident congestive heart failure; cardiac arrhythmias; active coronary heart disease or ischemia; uncontrolled hypertension; active clinically serious infections; or active brain metastases. Anticancer chemotherapy, immunotherapy, or vaccine therapy was not permitted during or within 30 days prior to the start of study treatment. Prior treatment with inhibitors of Raf, VEGF, or mTOR signaling pathways or farnesyl transferase inhibitors was not permitted. Study design This phase I, single-center, open-label, uncontrolled study was conducted in France between September 2005 (date of first patient first visit) and August 2006 (data cutoff date). On day 1 of a 21-day cycle, dacarbazine 1,000 mg/m 2 was administered as a 1-h infusion. Sorafenib 400 mg was administered twice daily continuously starting on day 2 of cycle 1. Toxicity-related dose modifications of sorafenib and dacarbazine were performed in accordance with protocol-specified guidelines. Treatment continued until the occurrence of unacceptable toxicity, tumor progression, or death. Sorafenib tablets were supplied by Bayer HealthCare AG (Leverkusen, Germany); dacarbazine was supplied by Faulding Pharmaceuticals SA (Asnieres, France). The study was conducted in accordance with the Declaration of Helsinki, the International Conference on Harmonization Good Clinical Practice guidelines, the EU-Directive 2001/20/EC, and local applicable laws. All patients provided signed informed consent before starting study treatment.

Fig. 1a

 1a Fig. 1aPlasma concentrations (geometric means/geometric standard deviation) of dacarbazine after a 1-h intravenous infusion of 1,000 mg/m 2 dacarbazine without

  14 for AUC(0-12) ss and AUC(0-12) ss,norm b n = 13 for AUC(0-12) ss and AUC(0-12) ss,norm c n = 12 for AUC(0-12) ss and AUC(0-12) ss,norm d Geometric mean e Coefficient of variation

Fig 1

 1 Fig 1

Table 2

 2 PK data for dacarbazine and AIC after a 1-h intravenous infusion of 1,000 mg/m 2 dacarbazine without (day 1, cycle 1) or with

	(day 2, cycle 2) administration of concomitant multiple oral doses of 400 mg bid sorafenib (n = 15)
	Parameters	Dacarbazine		AIC
		Cycle 1	Cycle 2	Cycle 2/Cycle 1 Cycle 1	Cycle 2	Cycle 2/Cycle 1
	AUC(0-inf) (mg
	h/L)
	GM a (%CV b )	65.0 (31)	50.0 (36)	20.6 (35)	28.9 (26)
	Range	29.4-111.5	24.5-87.8	11.3-33.2	21.8-56.0
	Ratio			0.769		1.408
	(90% CI c )			(0.629-0.941)		(1.167-1.699)
	AUC(0-tn) (mg h/L)
	GM a (%CV b )	62.9 (29)	49.0 (35)	19.1 (35)	27.1 (25)
	Range	29.0-105.3	23.8-84.3	10.5-29.7	19.8-50.4
	C max (mg/L)
	GM a (%CV b )	28.9 (26)	24.4 (26)	4.96 (39)	7.16 (26)
	90% CI c	14.4-45.3	13.6-35.8	2.30-9.29	4.18-10.20

a Geometric mean b Coefficient of variation c Confidence interval

Table 3

 3 PK parameters of sorafenib and its metabolites BAY-67 3472 (M2), BAY 43-9007 (M4), and BAY 68-7769 (M5) after multiple oral doses of 400 mg bid sorafenib and following a concomitant 1-h intravenous infusion of 1,000 mg/m 2 dacarbazine on day 1 of cycle

	2
	Parameters	Sorafenib (n = 15) a	M2 (n = 15) a	M4 (n = 15) b	M5 (n = 13) c
	AUC(0-12) ss (mg h/L)
	GM d (%CV e )	28.3 (84)	3.01 (207)	1.46 (202)	1.17 (225)
	Range	6.13-85.7	0.195-17.6	0.176-14.0	0.218-9.31
	AUC(0-12) ss,norm (kg h/L)
	GM d (%CV e )	4.75 (93)	0.489 (228)	0.254 (207)	0.200 (238)
	Range	0.934-16.1	0.029-3.15	0.026-2.23	0.024-1.44
	C max,ss (mg/L)
	GM d (%CV e )	3.67 (77)	0.371 (197)	0.149 (237)	0.137 (225)
	Range	0.905-9.66	0.035-2.03	0.016-1.48	0.022-0.943
	C max,ss,norm (kg/L)
	GM d (%CV e )	0.620 (84)	0.061 (211)	0.026 (244)	0.023 (245)

Acknowledgments This study was sponsored by Bayer HealthCare AG, Leverkusen, Germany. We acknowledge the medical writing assistance provided by Meenakshi Subramanian, PhD, Evidence Scientific Solutions, which was supported by Bayer HealthCare AG and Onyx Pharmaceuticals, Inc.


Maxime Crochemore

Epifanio Chiara
email: epifanio@math.unipa.it

Roberto ⋆⋆

⋆⋆⋆ Filippo Grossi
email: grossi@di.unipi.it

Mignosi
email: mignosi@math.unipa.it

A Trie-Based Approach for Compacting Automata

Keywords: Automata and formal languages, suffix tree, factor and suffix automata, index, text compression

We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al., as it uses less nodes, still with arcs labeled by single characters.

Introduction

One of the seminal results in pattern matching is that the size of the minimal automaton accepting the suffixes of a word (DAWG) is linear [START_REF] Blumer | The Smallest Automaton Recognizing the Subwords of a Text[END_REF]. This result is surprising as the maximal number of subwords that may occur in a word is quadratic according to the length of the word. Suffix trees are linear too, but they represent strings by pointers to the text, while DAWGs work without the need of accessing it.

DAWGs can be built in linear time. This result has stimulated further work. For example, [8] gives a compact version of the DAWG and a direct algorithm to construct it. In [START_REF] Inenaga | On-Line Construction of Compact Directed Acyclic Word Graphs,T oa p p e a ri n Discrete Applied Mathematics[END_REF] and [START_REF] Inenaga | On-Line Construction of Compact Directed Acyclic Word Graphs[END_REF] it is given an algorithm for online construction of DAWGs. In [START_REF] Holub | Personal Communication[END_REF] and [START_REF] Holub | On the Implementation of Compact DAWG's,i nP r oceedings of the 7th Conference on Implementation and Application of Automata[END_REF] space-efficient implementations of compact DAWGs are designed. For comparisons and results on this subject, see also [START_REF] Crochemore | Reducing space for index implementation[END_REF].

In this paper we present a new compaction technique for shrinking automata based on antifactorial tries of words. In particular, we show how to apply our technique to factor automata and DAWGs by compacting their spanning tree obtained by a breadth-first search. The average number of nodes of the structure thus obtained can be sublinear in the number of symbols of the text, for highly compressible sources. This property seems new to us and it is reinforced by the fact the number of nodes for our automata is always smaller than that for DAWGs.

We build up our finding on "self compressing" tries of antifactorial binary sets of words. They were introduced in [7] for compressing binary strings with antidictionaries, with the aim of representing in a compact way antidictionaries to be sent to the decoder of a static compression scheme. We present an improvement scheme for this algorithm that extends its functionalities to any chosen alphabet for the antifactorial sets of words M . We employ it to represent compactly the automaton (or better the trim) A(M ) defined in [START_REF] Crochemore | Automata and forbidden words[END_REF] for recognizing the language of all the words avoiding elements of M (we recall that a word w avoids x ∈ M if x does not appear in w as a factor).

Our scheme is general enough for being applied to any index structure having a failure function. One such example is that of (generalized) suffix tries, which are the uncompacted version of well-known suffix trees. Unfortunately, their number of nodes is O(n 2 ) and this is why researchers prefer to use the O(n)node suffix tree. We obtain compact suffix tries with our scheme that have a linear number of nodes but are different from suffix trees. Although a compact suffix trie has a bit more nodes than the corresponding suffix tree, all of its arcs are labeled by single symbols rather than factors (substrings). Because of this we can completely drop the text, as searching does not need to access the text contrarily to what is required for the suffix tree. We exploit suffix links for this kind of searching. As a result, we obtain a family of automata that can be seen as an alternative to suffix trees and DAWGs.

This paper is organized as follows. Section 2 contains our generalization of some of the algorithms in [7] so as to make them work with any alphabet. Section 3 presents our data structure, the compact suffix trie and its connection to automata. Section 4 contains our new searching algorithms for detecting a pattern in the compact tries and related automata. Finally, we present some open problems and further work on this subject in Section 5.

Compressing with Antidictionaries and Compact Tries

In this section we describe a non-trivial generalization of some of the algorithms in [7] to any alphabet A, in particular with Encoder and Decoder algorithms described next. We recall that if w is a word over a finite alphabet A,t h e set of its factors is called F (w). For instance, if w = aeddebc, then F (w)= {ε, a, b,...,aeddebc}.

Let us take some words in the complement of F (w), i.e., let us take some words that are not factors of w, call these forbidden. This set of such words AD is called an antidictionary for the language F (w). Antidictionaries can be finite as well as infinite. For instance, if w = aeddebc the words aa, ddd,a n d ded are forbidden and the set {aa, ddd, ded} is an antidictionary for F (w). If w 1 = 001001001001, the infinite set of all words that have two 1's in the i-th and i + 2-th positions, for some integer i, is an antidictionary for w 1 .

We want to stress that an antidictionary can be any subset of the complement of F (w). Therefore an antidictionary can be defined by any property concerning words.

The compression algorithm in [7] treats the input word in an on-line manner. Let us suppose to have just read the word v, proper prefix of w. If there exists any word u = u ′ a, where a ∈{ 0, 1}, in the antidictionary AD such that u ′ is a suffix of v, then surely the letter following v cannot be a, i.e., the next letter is b, with b = a. In other words, we know in advance the next letter b that turns out to be "redundant" or predictable. As remarked in [7], this argument works only in the case of binary alphabets.

We show how to generalize the above argument to any alphabet A, i.e., any cardinality of A. The main idea is that of eliminating redundant letters with the compression algorithm Encoder. In what follows the word to be compressed is noted w = a 1 •••a n and its compressed version is denoted by γ(w).

Encoder (antidictionary AD,w o r dw ∈ A * ) 1. v ← ε; γ ← ε; 2. for a ← first to last letter of w 3.
if there exists a letter b ∈ A, b = a such that for every suffix u ′ of v, u ′ b ∈ AD then 4.

γ ← γ.a; 5.

v ← v.a; 6. return (|v|, γ);

As an example, let us run this algorithm on the string w = aeddebc, with AD = {aa, ab, ac, ad, aeb, ba, bb, bd, be, da, db, dc, ddd, ea, ec, ede, ee}.

The steps of the execution are described in the next array by the current values of the prefix v i = a 1 •••a i of w that has been just considered and of the output γ(v i ). In the case of a positive answer to the query to the antidictionary AD, the array indicates the value of the corresponding forbidden word u,t o o . The number of times the answer is positive in a run corresponds to the number of bits erased.

εγ (ε)=ε v1 = a γ(v1)=a v2 = ae γ(v2)=aa a , ab, ac, ad ∈ AD v3 = aed γ(v3)=ae a , ec, ee, aeb ∈ AD v4 = aedd γ(v4)=ad a , db, dc, ede ∈ AD v5 = aedde γ(v5)=ad a , db, dc, ddd ∈ AD v6 = aeddeb γ(v6)=ab v7 = aeddebc γ(v7)=ab ba, bb, bd, be ∈ AD
Remark that γ is not injective. For instance, γ(aed)=γ(ae)=a.

In order to have an injective mapping we consider the function γ ′ (w)= (|w|,γ(w)). In this case we can reconstruct the original word w from both γ ′ (w) and the antidictionary.

Remark 1. Instead of adding the length |w| of the whole word w other choices are possible, such as to add the length |w ′ | of the last encoded fragment w ′ of w. In the special case in which the last letter in w is not erased, we have that |w ′ | = 0 and it is not necessary to code this length. We will examine this case while examining the algorithm Decompact.

The decoding algorithm works as follows. The compressed word is γ(w)= b 1 •••b h and the length of w is n. The algorithm recovers the word w by predicting the letter following the current prefix v of w already decompressed. If there exists a unique letter a in the alphabet A such that for any suffix u ′ of v,t h e concatenation u ′ a does not belong to the antidictionary, then the output letter is a. Otherwise we have to read the next letter from the input γ.

Decoder (antidictionary AD,w o r dγ ∈ A * , integer n) 1. v ← ε; 2. while |v| <n 3.
if there exists a unique letter a ∈ A such that for any

u ′ suffix of v u ′ a does not belong to AD then 4. v ← v • a; 5. else 6. b ← next letter of γ; 7. v ← v • b; 8. return (v);
The antidictionary AD must be structured in order to answer, for a given word v, whether there exist

|A|-1w o r d su = u ′ b in AD, with b ∈ A and b = a, such that u ′ is a suffix of v.
In case of a positive answer the output should also include the letter a.

Languages avoiding finite sets of words are called local and automata recognizing them are ubiquitously present in Computer Science (cf [START_REF] Béal | Codage Symbolique[END_REF]).

Given an antidictionary AD, the algorithm in [START_REF] Crochemore | Automata and forbidden words[END_REF], called L-automaton, takes as input the trie T that represents AD, and gives as output an automaton recognizing the language L(AD) of all words avoiding the antidictionary. This automaton has the same states as those in trie T and the set of labeled edges of this automaton includes properly the one of the trie. The transition function of automaton A(AD) is called δ. This automaton is complete, i.e., for any letter a and for any state v, the value of δ(v, a) is defined.

If AD is the set of the minimal forbidden words of a text t, then it is proved in [START_REF] Crochemore | Automata and forbidden words[END_REF] that the trimmed version of automaton A(AD)i st h efactor automaton of t. If the last letter in t is a letter $ that does not appear elsewhere in the text, the factor automaton coincides with the DAWG, apart from the set of final states. In fact, while in the factor automaton every state is final, in the DAWG the only final state is the last one in every topological order. Therefore, if we have a technique for shrinking automata of the form A(AD), for some antidictionary (AD), this technique will automatically hold for DAWG, by appending at the end of the text a symbol $ that does not appear elsewhere. Actually the trie that we compact is the spanning tree obtained by a breadth-first search of the DAWG, as this spanning tree is the trie obtained by pruning all leaves from the trie of all minimal forbidden words of text t (cf. [START_REF] Crochemore | Automata and forbidden words[END_REF]). The appendix presents an example of this procedure.

Self-compressing tries. Let us analyze now a technique to achieve a better compression ratio than the one obtained with the simple application of algorithm ENCODER.

If AD is an antifactorial antidictionary for a text t then for any word v ∈ AD the set AD \{v} is an antidictionary for v. This last property lets us to compress v using AD \{v} or a subset of it. Hence the new technique, that is analogous to the one in [7], will consist in self-compressing the antidictionary of the text t that is not necessarily binary.

Let us go in details and consider a generic word v in AD.W ordsu in AD\{v} of length smaller than or equal to v's one will be used to compress v and to obtain its compressed version γ 1 (v). If a word u in AD, such that |u| = |v|,i su s e df o r compressing v, then u and v have the same prefix x of length |u|-1ofv. Further

γ 1 (v)=γ 1 (u)=γ 1 (x).
In this case we loose information on last letters of u and v. We have two choices. The first one is to compress a word v in AD by using as an antidictionary the subset of AD including all words having length strictly smaller than |v|.The second choice consists in adopting some strategy to let only one of the two words being compressed using the other one. We will proceed along the first choice, i.e. while compressing a given word in the antidictionary we would not use words of its same length. Definition 1. A r-uple of words (v 1 ,...,v r ),b e i n gr the cardinality of the alphabet A, is called stopping r-uple if v 1 = u 1 a 1 , ...v r = u r a r ,w h e r ea i are distinct symbols in A and u i is a suffix of u i+1 , for any i such that 1 ≤ i ≤ r -1.

Proposition 1. Let t be a text and AD be an antifactorial antidictionary of t. If there exists a stopping r-uple (v 1 ,...,v r ),w i t hv i = u i a i ,a i ∈ A, 1 ≤ i ≤ r, then u r is a suffix of t and does not appear elsewhere in t. Moreover there exists at most one such r-uple of words.

Proposition 2. Let (v 1 ,...,v r ) be the only possible stopping r-uple in the antidictionary AD of a text t. If the prefix u r-1 of length |v r-1 |-1 of the penultimate word v r-1 in the lexicographic word is a proper suffix of the prefix u r of length |v r |-1 of the last word v r , then last letter in v r is never erased.

Let us now examine another algorithm, similar to that presented in [7], apart from some details, that is very important in our case. The idea of this algorithm is to "erase" states with only one outgoing edge whose label is predictable by the previous compression algorithm that uses as antidictionary the leaves of the trie having strictly smaller depth. In other words, consider a state p that has a unique outgoing edge labeled by a such that, for any other symbol b = a,t h e longest suffix of pb stored in the trie (i.e., δ(p, b)) is a leaf. Then we erase state p together with its outgoing edge and we replace p by its unique child as described in Self-compress. This algorithm works in the case when in the antidictionary there are no stopping r-uples.

Self-compress (trie T , function δ)

1. i ← root of T ; 2. create root i ′ ; 3. add (i, i ′ ) to empty queue Q; 4. while Q = ∅ 5. extract (p, p ′ )f r o mQ; 6.

if p has more than one child then 7.

for each child qj of p 8. create q ′ j as child of p ′ ; 9.

add (qj,q ′ j )t oQ; 10.

else if q is a unique child of p and q = δ(p, a), a ∈ A then 11.

if δ(p, b)i sal e a f∀ b ∈ A, b = a then 12.

add + sign to q ′ ; 13.

add (q, p ′ )t oQ; 14.

else create q ′ as a-child of p ′ ; 15.

add (q, q ′ )t oQ; 16. return trie having root i ′ ;

In this case we do not delete the child, but the parent of a compressed edge, and we add a + sign to the remaining node. Note that with this new algorithm there is no guarantee that function δ is always defined on the nodes belonging to the compacted trie (this property was guaranteed with previous Self-compress algorithm). To avoid this drawback, δ can be recovered by the relation s(v) (usually called suffix link), the longest suffix of v that is a node in the trie, where the left-hand δ is the new version defined in terms of the old version, the right-hand δ, To deal with the case when the antidictionary contains a stopping r-uple, we have to add some more information to the output of the algorithm. This added information can be to keep a pointer to the leaf corresponding to the longest element of the stopping r-uple together with the length of the compressed ingoing edge to this leaf. Details are left to the reader.

Compact tries present some very useful and important properties. In particular we are able to check whether a pattern p is recognized by the automaton A(AD), by only "decompacting" a small part of the compact trie, output of previous algorithm, and not by "decompacting" the whole trie described in [7].

The algorithm Search that realizes this task is described in Section 4. Before that, we introduce compact suffix tries in Section 3, because we make use of their properties in the next section.

Recall that if the text ends with a symbol $ the compacted version of automaton A(AD) can be seen as a compacted version of the DAWG, that is different from the classical one, called CDAWG. Proposition 3. Every node v that is in our compacted DAWG and is not in the CDAWG is such that it has only one outgoing edge and its suffix link points to a node of the CDAWG.

Compact Suffix Tries

We want to extend our technique to suffix tries that do not represent antifactorial sets of words.

We adopt the notation defined in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], and assume that the reader is familiar with suffix trees. Given a word w = a 1 a 2 ...a n of n symbols drawn from an alphabet A, called letters, we denote by w[j...j + k -1] the factor of w of length k that appears in w at position j. The length of w is denoted by |w| = n. The empty word ǫ is a factor of any word. A factor of the form w[j, |w|]( r e s p . w [1,j]) is called a suffix (resp. prefix) of w.

The suffix trie ST (w)o faw o r dw is a trie where the set of leaves is the set of suffixes of w that do not appear previously as factors in w.

We can identify a node of the trie with the label of the unique path from the root of the trie to the given node. Sometimes we can skip this identification and, given a node v, we call σ v the label word that represents the unique path from the root to v.

In this section we define our compacted version CST (w) of the suffix trie. Basically we use the same approach of the suffix tree, but we compact a bit less, i.e., we keep all nodes of the suffix tree S(w) and we keep some more nodes of the trie. In this way we can avoid to keep the text aside.

In order to describe this new data structure, we have to define first of all its nodes, namely, 1. all the nodes of suffix tree S(w), and 2. all the nodes v of trie ST (w) such that s(v) is a node of suffix tree S(w).

Recall that in the suffix tree, for any suffix w[j, |w|]ofw there is a node v such that σ v = w[j, |w|], even if w[j, |w|] has appeared as factor in another position.

At this point one may wonder why are we keeping the nodes of type 2. What is the relation between these nodes and minimal forbidden words? The answer to the question is given by next proposition, that can be seen as a kind of converse of Proposition 3. Proposition 4. For any node v described in point 2, there exists a letter a such that σ v a is a minimal forbidden word of w.

A suffix trie is not a trie of minimal forbidden words, but if we add to the trie the minimal forbidden words, we can describe a compacting algorithm that is analogous to that presented in Section 2. The nodes that are neither of type 1, nor of type 2, and that are not leaves can be erased. More precisely, we do not need to introduce explicitly the minimal forbidden words in the trie.

Let us now define the arcs of CST (w). Since the nodes of CST (w) are all nodes of the trie ST (w), for any node v we assign the same number of outgoing arcs, each of them labeled by a different letter. Hence, for any arc of the form (v, v ′ ) with label l((v, v ′ )) = a in ST (w), we have an arc (v, x) with label l((v, x)) = a in CST (w), where the node x is

(i) v ′ itself, in the case it is still present in CST (w); (ii) the first node in CST (w) that is a descendant of v ′ in ST (w), when v ′ is not an o d eo fCST (w).
In case (ii), we consider as this arc (v, x) represents the whole path from v to x in the trie T r(w), and we say that this arc has length greater than one. We further add a + sign to node x, in order to record this information.

To complete the definition of CST (w) we keep the suffix link function over these nodes. Notice that, by definition, for any node v of CST (w), the node pointed by a suffix link, s(v), is always a node of the suffix tree S(w) and hence it also belongs to CST (w).

We now show that the number of nodes of CST (w) is still linear in the length |w| of w, independently from the alphabet size. Indeed, since the number of nodes of the suffix tree S(w) is linear, we only have to prove that the number of nodes that we add to it to obtain the nodes of CST (w) is linear in the length |w| of w. This is what we prove in the lemma.

Lemma 1. The number of nodes v of the trie ST (w) such that v does not belong to the tree S(w) and s(v) is a node of the tree S(w) is smaller than the text size.

Notice that Lemma 1 states a result that is "alphabet independent", i.e., the result does not depend on the alphabet size. By definition, since the number of nodes in the tree is smaller than 2|w|, it is straightforward to prove that the number of added nodes is smaller than this quantity multiplied by the cardinality of the alphabet.

The power of our new data structure is that it still has some nice features when compared to the suffix tree. In fact, we possibly reduce the amount of memory required by arc labels. While suffix trees arcs are labeled by substrings, compact suffix tries ones are labeled by single symbols. So they can be accessed "locally" without jumping to positions in the text, which is no more needed. Also, this property is "alphabet independent", as stated in next lemma. We remark here that, if we add terminal states to the DAWG of a word w, the structure thus obtained is the minimal automaton accepting the suffixes of w. This implies that if we reduce the size of this automaton, we consequently reduce that of the DAWG.

Searching in Compact Tries and Related Automata

In this section we show how to check whether a pattern p occurs as a factor in a text w, by just "decompacting" a small part of the compact suffix trie CST (w) associated with w (not the whole trie). Note that the arcs in CST (w) are labeled with single letters instead of substrings, so we must recover them somehow without accessing the text.

Generally speaking, with the same technique we can check whether a pattern p is recognized by an automaton A(AD). In this section we center our description around the algorithms for compact suffix tries, but they work on automata with minor modifications.

Let us begin by examining a function that returns the string associated with the path in the trie between two nodes u and v.

Decompact (Compacted trie CST , function δ, function s,a r c( u, v))

1. w ← ǫ; 2. a ← label of (u, v); 3. if v has not a + then 4. w ← a; 5. else 6.

z ← s(u); 7.

while z = s(v) 8.

w ← w concat Decompact(CST , δ, s,(z, δ(z, a))); 9.

z ← δ(z, a); 10.

if z has only one child x in CST then 11.

a ← label of (z, x); 12. return w Proposition 5. Let u be a node in the compacted trie. If v is a child of u, then the path from s(u) to s(v) in the compacted trie has no forks.

An easy variation of this algorithm can be used to check whether a pattern occurs in a text. More precisely, algorithm Search takes as input a node u and a pattern p. If there is no outgoing path in the decompacted trie from u labeled p, it returns "null." If such a path exists and v is its incoming node, it returns v. The pattern p is represented either as a static variable or as a pointer to pointers. We denote by succ(p) the operation that, received as input a pointer to a letter, points to next letter and p[0] points to the first letter of p. The proof of the correctness of this algorithm follows by induction and by Proposition 5. z ← s(u); 12.

while z = s(v) 13.

z ′ ← δ(z, p[0]); 14.

Search(CST , δ, s,z,p) 15.

z ← z ′ Notice that, since Search returns a pointer, we can use this information to detect all the occurrences in an index. The drawback of Decompact and Search is that they may require more then O(m) time to decompact m letters and this does not guarantee a searching cost that is linear in the pattern length. To circumvent this drawback, we introduce a new definition, that we use for a linear-time version of Decompact (hence, Search). Definition 2. Let s be the suffix link function of a given trie. We define supersuffix link for a given node v in the trie, the function

s * : v → s k (u),
where u is a node in the trie and k is the greatest integer such that s k (u) and s k (v) are connected by a single edge (i.e., of path length 1), while the path from s k+1 (u) to s k+1 (v) has a length strictly greater than 1.

In order to appreciate how this new definition is useful for our goal, consider the task of decompacting the edge (u, v)i nCST to reconstruct the substring originally associated with the uncompacted tries. We do this by considering repeatedly (s(u),s(v)), (s 2 (u),s 2 (v)), and so on, producing symbols only when the path from the two nodes at hand has at least one more edge. Unfortunately, we cannot guarantee that (s(u),s(v)) satisfies this property. With super-suffix links, we know that this surely happens with (s(s * (u)),s * (s(v))) by Definition 2. Now, Decompact works in linear time with the aid of super-suffix links.

Appendix

Let us examine, as an example, the text t = abaababaaba$. Minimal words of text t are: aaa, aabaa, aa$, babaabab, babab, baba$, bb, b$, $a,$ b, $$.

  n (p),a) if not, where n = min{m | δ(s m (p),a) is defined} Hence, the output of this algorithm represents a compact version of the input trie and, if we include the new function δ, the compact version of the automaton A(AD).

Lemma 2 .

 2 Let A be any alphabet and w b eaw o r do ni t .T h en u m b e ro fn o d e s of the compact suffix trie CST (w) is linear in the length n of w, whichever cardinality A has.

Fig. 1 .

 1 Fig. 1. Trie of the minimal forbidden factors.

Fig. 2 .

 2 Fig. 2. Self-Compressed trie of the minimal forbidden factors.

Fig. 3 .

 3 Fig. 3. Compacted Self-Compressed DAWG of the text t. It has 9 states. It has been obtained by adding the function δ whenever undefined (dotted arcs) to the self-compressed trie and by trimming it, i.e. by pruning the leaves and the corresponding ingoing and outgoing arcs. Suffix links and super-suffix links are not drawn.

Fig. 4 .

 4 Fig. 4. CDAWG of the text t.

  Search (Compacted trie CST , function δ, function s,n o d eu, pattern p)

	1. if p[0] = end of string then
	2.	return(u)
	3. else
	4.	if ∃v such that p[0] is label of (u, v) then
	5.	return (null)
	6.	else
	7.	let v such that (u, v) has label p[0];
	8.	if v has not a + then
	9.	Search(CST , δ, s, v, succ(p))
	10.	else
	11.

As a result of the linearity of SuperDecompact, we also have: Lemma 3. Algorithm Search for a pattern p takes O(|p|) time by using supersuffix links instead of suffix links.

Full-Text Indexing. A full-text index over a fixed text t is an abstract data type based on the set of all factors of t, denoted by Fact(t). Such data type is equipped with some operations that allow it to answer the following query: given x ∈ A * , find the list of all occurrences of x in t. If the list is empty, then x is not a factor of t.

Suffix trees and compacted DAWGs (CDAWGs) can answer to previous query in time proportional to the length of x plus the size of the list of the occurrences. By superposing the structure of CDAWGs to our compacted DAWGs we can obtain the same performance. More precisely, for any edge q of our compacted DAWG, let us define recursively final(q)

if q has more than two children or q is the only final state final(δ(q, a)) if not, and (δ(q, a)) is the only outgoing edge from q.

For any edge (p, q) we add another edge p, f inal(q) labelled by the length of the path from p to final(q) in the DAWG. These new edges allow to simulate CDAWGs.

We have examples of infinite sequences of words where our compacted DAWGs have size exponentially smaller than the text size. This is the first time to our knowledge that full-text indexes show this property.

Conclusions and Further Work

In this paper we have presented a new technique for compacting tries and their corresponding automata. They have arcs labeled with single characters; they do not need to retain the input string; also, they have less nodes than similar automata. We are currently performing some experiments for testing the effective gain in terms of final size of the automata. For highly compressible sources, our automata seem to be sublinear in space. We do not known if algorithm Search strictly needs super-suffix links to work in linear time on the average (in the worst case, they are needed). Finally, we are investigating methods for a direct construction of our automata.


Maxime Crochemore

Leszek Ga Sieniec
email: leszek@mpi-sb.mpg.de

Wojciech Rytter
email: rytter@mimuw.edu.pl

Constant-Space String-Matching in Sublinear Average Time (Extended Abstract)

Given two strings: pattern P of length m and text T of length n. The stringmatching problem is to nd all occurrences of the pattern P in the text T. We present a simple string-matching algorithms which works in average o(n) time with constant additional space for one-dimensional texts and two-dimensional arrays. This is the rst attempt to the small-space string-matching problem in which sublinear time algorithms are delivered. More precisely we show that all occurrences of one-or two-dimensional patterns can be found in O( n r ) average time with constant memory, where r is the repetition size (size of the longest repeated subword) of P.

Introduction

The string-matching problem is de ned as follows. Assume we are given two strings: pattern P of length m and text T of length n. The pattern occurs at position i in text T i P = T i::i+m 1]. We consider algorithms that determine all occurrences of the pattern P in the text T. The complexity of the string matching algorithm is measured by the number of symbol comparisons of pattern and text symbols. The algorithms solving string-matching problem in linear time and constant space are perhaps the most interesting ones among all designed for the entire problem. The rst algorithm which uses a constant amount of additional memory was proposed by Galil and Seiferas in 8]. Later Crochemore and Perrin in 4] have presented an algorithm that achieves a smaller (at most 2n) number of comparisons while preserving the small amount of memory. Then, another improvement ( 32 ) on the number of comparisons was presented by Breslauer in 2]. In the meantime, alternative algorithms were introduced by G asieniec, Plandowski and Rytter in 9] (2 + ") and 10] (1 + ").

Besides there are known algorithms which make a sublinear number of comparisons on the average. The rst such method was proposed in 11] for strings. An attempt to 2d-dimensional pattern matching fast on the average is due to Baeza-Yates and R egnier in 1]. However all known sublinear average time algorithms use a linear-size additional memory to keep a table of shifts as in the Boyer-Moore algorithm, (see e.g. 11], 7]), or for the representation of a directed subword graph or equivalent data structures (see e.g. 3] and 6]). The latter algorithms have the best possible O( n log m m ) average time complexity due to lower bound of Yao 12]. One can try to nd a trade-o between small space and good average time applying techniques from 3] to the subwords of the pattern P. This might lead to an algorithm which uses O(s) space (size of the preprocessed subwords) and has O( n log s s ) average time. Until now there was no algorithm both performing an average sublinear number of comparisons and using only constant memory space.

In this paper we present the novel idea of such an algorithm for one-dimensional strings as well as for two-dimensional arrays. The idea of the algorithms is based on the use of subword repetitions.

For the simplicity of the presentation we assume that all strings considered in the paper are built over a binary alphabet = fa, bg.

We say that the word w 2 has a period q (0 < q jwj) if w i] = w i + q] for all positions 1 i jwj q.

The shortest period of w is called the period of w. If it satis es q jwj=2, then the word w is called periodic; otherwise, w is called nonperiodic.

2 Nonperiodic one-dimensional patterns

In this section we assume that the pattern P is nonperiodic.

Let us denote by rep size(P ) the size of the length of a largest subword of P.

Example 1.

The repeated subword in an example text given below is indicated here in bold.

rep size(ababbaababaaababbaababba) = 9.

The number of logarithmic-size subwords of a text is large enough to guarantee that at least one of them repeats. This implies easily the following fact.

Lemma 1

For each pattern P of size m rep size(P) = (log m).

Denote r = rep size(P ), and let w be a longest repeated subword. Assume P p r::p 1] = P q r::q 1]; p q r and P p] 6 = P q]:

In Example 1 we have (w; r; p; q) = (babbaabab;9; 11; 23). The positions p; q are mismatches w.r.t. the repetition of the word w. In general if there are no mismatch positions based on repetition w to the right of two copies of w then we try to nd them to the left reversing the string-matching process.

In case no mismatch is found neither to the right nor to the left it means that the repetition occurs at the borders of the pattern. This case is handled similarly to the periodic case discussed in the next section. We say that a position i in T is a mismatch position i T i + p 1] 6 = T i + q 1].

We call a window any interval of positions i::i+r 1] on the T, for 1 i n r+1. Assume w.l.o.g. that we already know the 4-tuple (w; r; p; q). Denote by Leftmost Mismatch(W) the procedure that nds the rst (from the left) mismatch position in a given window W. If there is no such a mismatch position then a special value nil is returned. Lemma 2

(1). If Leftmost Mismatch(W) = nil , no position of P in T is in W, [START_REF] Baeza-Yates | Fast Algorithms for two-dimensional and Multiple Pattern Matching[END_REF]. Otherwise, no position of P in T is in W fLeftmost Mismatch(W)g.

Proof:

The mismatch is used as a constant-size deterministic sample.

2 Denote by Naive Check(i) the procedure that tests a possible occurrence of P starting at a given position i in T and that tests the equality of corresponding symbols from left to right.

In the worst case, m comparisons are done, but for random binary texts T the average time is really small. We assume that symbols of the text are uniformly distributed.

Lemma 3

On random texts each of the procedures Naive Check and Leftmost Mismatch makes on the average less than 2 comparisons.

Proof: The sum i 2 i is bounded by 2.

Lemma 4

Assume that pattern P is nonperiodic. Then, for a random text T, we can nd all the occurrences of P in T in O( n rep size(P ) ), which is O( n log m ), average time using constant additional memory. The worst-case running time of the algorithm is O(n).

Proof:

There are O(n=r) iterations in the algorithm Nonperiodic Pattern Searching below. Each iteration uses at most 4 comparisons on the average both for execution of Naive Check and Leftmost Mismatch, due to Lemma 3.

The comparisons done during di erent iterations can be dependent on each other, but the independence is not needed according to the fact that the average value of a sum of random variables is the sum of their average value. Therefore the algorithm makes altogether at most O(n=r) comparisons on the average. ALGORITHM Nonperiodic Pattern Searching; f nonperiodic pattern g; i:= 1; r:= rep size(P ); while i n m do begin W := i::i + r 1]; i 0 := Leftmost Mismatch(W ) if i 0 6 = nil then if Naive Check(i 0 ) then report match at i 0 ; i:= i + r; end Similarly to the algorithm presented in 10] we can guarantee the linear worst-case time of the algorithm Nonperiodic Pattern Searching since the shifts are based on a longest repeated subword of the pattern. This completes the proof.

3 Periodic one-dimensional

Assume now that P is periodic, so obviously its repetition size is large. Lemma 5 If P is periodic then rep size(P) m 2 . In this situation we cannot use the approach based on 4-tuples (w; r; p; q). Thus we derive a slightly di erent algorithm, which is even more e cient than the one used in nonperiodic case. Lemma 6 Assume P is periodic. Then for a random text T we can nd all occurrences of P in T in O( n m ) average time using constant additional memory. The worst-case time of the algorithm is linear.

Proof:

Assume p is the period of P, where p jPj=2. We can partition the positions in T into disjoint consecutive large windows; each window consists of m=2 consecutive positions of T (the last one can be smaller). The rst large window is 1::m=2]. The algorithm makes n m=2 iterations. We process each large window as follows. Assume that the current window is i + 1::i + m=2].

Phase 1. nd the rightmost mismatch in T according to the period p in the segment i+1::i+m]. If a mismatch is found then switch to the next window i+m=2+1::i+m] and execute Phase 1 again, otherwise Phase 2. search naively for an occurrence of P starting in the current window

The probability that we do not have a mismatch in Phase 1 is exponentially small, so the expected cost of the second phase is very small even if we search for the occurence naively. The expected time to nd a mismatch in the rst phase is O(1). There are O(n=m) iterations, so the total cost is as required. This completes the proof.

2

The algorithm for the nonperiodic case when repetition is placed on borders is handled in the same way but with windows of size O(r).

Lemma 4 and Lemma 6 imply the following result.

Theorem 7

For a random text T we can nd all occurrences of P in T in O( n rep size(P) ) average time (which is O( n log m )) using constant additional memory. The worst-case time of the algorithm is linear.

Two-dimensional pattern-matching

In this section we show that also for the 2d-pattern matching problem the e ciency of a search depends on the repetition size.

Assume the pattern P and the text T are m m and n n symbol arrays, respectively. Denote N = n 2 ; M = m 2 .

We say that the pattern occurs in T at position (i; j) i P x; y] = T i+x 1; j+ y 1] for all integers 1 x; y m. A 2-dimensional pattern P has a period a; b] if P i; j] = P i + a; j + b], for all 1 i m a and 1 j m b.

If pattern P has a period a; b] such that maxfa; bg m 2 then it is called periodic. Denote by 1rep size(P) the maximum repetition size of a row of P.

Theorem 8

Assume P and T are two-dimensional texts. For a random two-dimensional text T there is an algorithm that nds all the occurrences of P in T time O( N 1rep size(P ), which is O( N log M )), average time using constant additional memory. If P contains a periodic row then the algorithm performs only O( N m ) comparisons.

Proof:

Similarly as in 1-dimensional case we consider periodic and nonperiodic case separately. The algorithm is almost the same as for one dimension. We can construct a 2-dimensional version of the algorithm Nonperiodic Pattern Searching.

In the case where all rows of the pattern are nonperiodic, the algorithm takes the rst row of the pattern and looks for it scanning each row of T partitioned into windows of size 1rep size(P). For each window at least one position involves a test for an occurrence of the whole pattern. Instead of Naive Check(i 0 ), a version for 2 dimensions 2d-Naive Check(i 0 ; j 0 ) is used. According to lemma 1 we have altogether N=1rep size(P) windows, and in each of them the average number of comparisons is constant. Hence the total number of comparisons is O(N=1rep size(P)), which is O( N log M ) since 1rep size(P) = (log M). In the case where pattern P has at least one periodic row, the algorithm chooses one such row and then proceeds in a similar way as in 1-dimensional case. Each row of T is partitioned into large windows. There are O( N m ) such windows, and in each of them the algorithm makes a constant number of comparisons on the average. Hence the total number of comparisons is O( N m ). This completes the proof.

2

In the case of a periodic pattern P the text search can be done faster.

Theorem 9

If the pattern P is periodic the search for it in T can be done in time O( N M ).

Proof:

Since the pattern P is periodic it has two repeated subrectangles of size at least m 2 m 2 (see g. 1, and the shaded areas named A), which de nes a set of pairs of equal symbols of size (M). We consider right bottom quadrants D and E of these rectangles. The 2-dimensional sampling is using this set as follows. Assume that there is a pair of di erent symbols (x; y) in the text T whose positions di er exactly by a vector that is a short period in P. Let symbol x belong to square D and let y belong to E. Then there is no any occurrence of pattern P in the window B. Using the latter observation the text T is divided into windows of size at least m 4 m 4 = (M) (corresponding to rst quadrant of A). The search in every window starts from the test of equality of symbols in pairs between windows E and D. Since the text is random the algorithm makes only a constant number of tests on the average in every window, and this nally gives the O( N M ) desired bound.

2 We can de ne 2-dimensional repetition size of 2d-pattern P (2drep size(P), in short) as the largest repeated subsquare area of P. Similarly to 1-dimensional case we can prove that.

Theorem 10

For a random two-dimensional text T there is an algorithm that nds all the occurrences of P in T in O( N 2drep size(P) ) average time using constant additional memory.

Summary

The main result of the paper is a constant space algorithm that performs O(n= log(m)) comparisons on the average for one-dimensional as well as for two-dimensional texts.

In the case of periodic patterns the average behavior of the algorithm is even better, reaching the asymptotic bound of O( n m ). Our paper initiates a discussion about pattern matching algorithms using small space and that are fast on the average. In this paper we have done some steps towards the goal but we think that the most interesting problem is still open: what is the exact average complexity of constant-space string matching? Or respectively: what is the space bound needed by any algorithm making O( n m log(m)) comparisons on the average.

Figure 1 :

 1 Figure1: Sampling in 2-dimensions, if there is mismatch between position x and y then there is no occurrence of P starting in the indicated window.


Maxime Crochemore
email: maxime.crochemore@univ-mlv.fr.

Danny Hermelin ⋆⋆

Gad M Landau ⋆ ⋆ ⋆

Stéphane Vialette
email: vialette@lri.fr.

Approximating the 2-Interval Pattern problem

We address the problem of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, which is motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified model. For each such model, we give varying approximation quality depending on the different possible restrictions imposed on the input 2-interval set.

Introduction

In the context of RNA secondary structure prediction, Vialette [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF] proposed a geometric representation of a helix in an RNA single stranded molecule by means of a natural generalization of an interval, namely a 2-interval. A 2-interval is the union of two disjoint intervals defined over a single line. In [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF], intervals and 2-intervals represent respectively sequences of contiguous bases and possible pairings between such sequences in the RNA secondary structure. The goal is to find a maximum disjoint subset of the given set of 2-intervals, restricted to prespecified geometrical constrains, so as to serve as a valid approximation of the actual secondary structure of the given RNA.

Throughout the paper, a 2-interval is denoted by D = (I, J) where I and J are two (closed) intervals defined over a single line such that I < J, i.e., I is completely to the left of J. Two 2-intervals D 1 = (I 1 , J 1 ) and D 2 = (I 2 , J 2 ) are disjoint, if both 2-intervals share no common point, i.e., (I 1 ∪ J 1 ) ∩ (I 2 ∪ J 2 ) = ∅. For such disjoint pairs of 2-intervals, three natural binary relations are of special interest.

Definition 1 (Relations between 2-intervals). Let D 1 = (I 1 , J 1 ) and D 2 = (I 2 , J 2 ) be two disjoint 2-intervals. Then

-D 1 < D 2 (D 1 precedes D 2 ), if I 1 < J 1 < I 2 < J 2 . -D 1 ⊏ D 2 (D 1 is nested in D 2 ), if I 2 < I 1 < J 1 < J 2 . -D 1 ≬ D 2 (D 1 crosses D 2 ), if I 1 < I 2 < J 1 < J 2 .
A pair of 2-intervals D 1 and D 2 is R-comparable for some R ∈ {<, ⊏, ≬}, if either (D 1 , D 2 ) ∈ R or (D 2 , D 1 ) ∈ R. A set of 2-intervals D is R-comparable for some R ⊆ {<, ⊏, ≬}, R = ∅, if any pair of distinct 2-intervals in D is Rcomparable for some R ∈ R. The non-empty subset R is called a model. Note that any two disjoint 2-intervals are R-comparable for some R ∈ {<, ⊏, ≬}. Equivalently, any pairwise disjoint subset of D is {<, ⊏, ≬}-comparable. In [START_REF] Blin | New results for the 2-interval pattern problem[END_REF][START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF], the 2-Interval Pattern problem is defined as follows: -D is a point 2-interval set if all intervals in S(D) are pairwise disjoint (note that in this case, all intervals in S(D) may be considered as points).

D 1 D 2 D 3 (b) D 1 D 2 D 3 (a) (d) (c)
-D is a unitary 2-interval set if S(D) consists of intervals of unit length.

-D is a balanced 2-interval set if any 2-interval in D is a pair of two intervals of equal length. -D is an unlimited 2-interval set if none of the above restrictions are imposed.

The left part of Table 1 depicts the current state of the art for the 2-Interval Pattern problem in terms of exact algorithms. In [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF], the 2-Interval Pattern problem over the {⊏, ≬} and {<, ⊏, ≬} models is proved to be NP-hard even for unitary 2-interval sets. The proof for the {<, ⊏, ≬} model is obtained as a direct consequence of the APX-hardness result for the Maximum Independent Set problem for t-interval graphs given in [START_REF] Bar-Yehuda | Scheduling spit intervals[END_REF]. The results in [START_REF] Bar-Yehuda | Scheduling spit intervals[END_REF] also provide approximation algorithms for this model. In [START_REF] Blin | New results for the 2-interval pattern problem[END_REF], an NP-hardness result for the {<, ≬} model restricted to unitary 2-interval sets is given. The time complexity for this same model when the input is restricted to point 2-interval sets is still unknown [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF][START_REF] Blin | New results for the 2-interval pattern problem[END_REF]. These results imply that in practical terms, secondary structures containing pseudoknots are hard to predict in our suggested mathematical model. This is consistent with previously known NP-hardness results for RNA secondary structures prediction in other models considering arbitrary pseudoknots [START_REF] Akutsu | Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots[END_REF][START_REF] Ieong | Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs[END_REF][START_REF] Lyngsø | RNA pseudoknot prediction in energy based models[END_REF]. In this paper we focus on the three NP-hard models of the 2-Interval Pattern problem. More specifically, we design constant factor approximation algorithms for the {<, ⊏, ≬}, {⊏, ≬}, and {<, ≬} models. The approximation factors obtained by all our algorithms vary depending on the restriction imposed on the input set of 2-intervals (see Table 1). Furthermore we suggest a new restriction, namely balanced 2-interval sets. By definition, unitary 2-interval sets are also balanced but the converse is not necessarily true. Consequently, the above mentioned NP-hardness results also hold for the balanced case, and moreover, balanced 2-interval sets introduce a new combinatorial object which requires particular consideration. Furthermore, the balanced restriction is very natural in the biological setting of the problem.

Classical complexity Model Unl. Bal. Uni. Pnt. {<, ⊏, ≬} NP-C [11, 2] O(n √ n) [11] {⊏, ≬} NP-C [11] O(n 2 √ n) [3] {<, ≬} NP-C [3] ? {<, ⊏} O(n 2 ) [11] {≬} O(n 2 log n) [11] {⊏} O(n log n) [3] {<} O(n log n) [
This paper is organized as follows. In Section 2, we consider the 2-Interval Pattern problem over the general model, i.e., the {<, ⊏, ≬} model. We describe in Section 3 an approximation algorithm for the problem over the {⊏, ≬} model. Finally, in Section 4, the {<, ≬} model is considered, and different approximation algorithms are introduced for all possible restrictions imposed on the input.

2 Approximation algorithms for the {<, ⊏, ≬} model.

We begin by considering the 2-Interval Pattern problem over the general model, i.e., the {<, ⊏, ≬} model. Recall that in this case, given an input set of 2-intervals D, the problem asks to find a maximum {<, ⊏, ≬}-comparable subset of D, which is equivalent to finding a maximum pairwise disjoint subset of D.

For point 2-intervals sets, 2-Interval Pattern can be solved in polynomial time by maximum matching [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF]. For unitary 2-interval sets, the problem is already APX-hard [START_REF] Bar-Yehuda | Scheduling spit intervals[END_REF], and therefore is APX-hard also for balanced and unlimited 2-interval sets. Furthermore, the results in [START_REF] Bar-Yehuda | Scheduling spit intervals[END_REF] also yield approximation algorithms for our case which directly imply the following.

Proposition 1 ([2]

). The 2-Interval Pattern problem over the {<, ⊏, ≬} model can be approximated within a factor of 4 when restricted to unlimited 2-interval sets, and a factor of 3 when restricted to unitary interval sets.

The algorithm given in [START_REF] Bar-Yehuda | Scheduling spit intervals[END_REF] that solves the case of unitary 2-interval sets can be executed in O(n lg n) time, where n is the size of the input set of 2-intervals. However, the algorithm for unlimited 2-interval sets uses linear programming techniques, which in practice are very often too time costly. Clearly, balanced 2-interval sets lie between the two cases and are arguably the most biologically important case. In the rest of this section we describe a quadratic time 4-approximation algorithm for balanced 2-intervals sets.

Given any balanced 2-interval set D, let the smallest 2-interval in D be the 2interval with the shortest left (or right, as they are both of equal length) interval among all left intervals involved in D. The algorithm we suggest is a simple greedy strategy that repeatedly picks the smallest 2-interval in the input, adds it to the solution, and omits all other 2-intervals in the input which intersect it. A schematic description of this algorithm, which we call Bal-{<, ⊏, ≬}-Approx, is given in Figure 2. contained in the left or right interval of D 0 . Thus, there can be at most four disjoint intervals involved in D, which intersect D 0 at this given iteration. It follows that at this iteration, at most four 2-intervals in the optimal solution are omitted from D. Applying this argument for all iterations of the algorithm yields the desired approximation factor guarantee.

⊓ ⊔ Time complexity. Given an input set of 2-intervals D of size n, algorithm Bal-{<, ⊏, ≬}-Approx can be implemented straightforwardly to run in O(n 2 ) time.

3 An approximation algorithm for the {⊏, ≬} model.

We next consider the 2-Interval Pattern problem over the {⊏, ≬} model. Recall that the 2-Interval Pattern problem over this model is NP-complete even for unitary 2-interval sets [START_REF] Vialette | On the computational complexity of 2-interval pattern matching problems[END_REF]. In the following we introduce a single algorithm which achieves different constant approximation factors for unitary, balanced and unlimited 2-interval sets. More specifically, we describe an algorithm which uses the algorithms described in the previous section as sub-procedures, choosing the specific algorithm according to the restriction imposed on the input. Our algorithm is a direct generalization of the algorithm devised in [START_REF] Blin | New results for the 2-interval pattern problem[END_REF] for the 2-Interval Pattern problem over the {⊏, ≬} model, restricted to point 2-interval sets. As in [START_REF] Blin | New results for the 2-interval pattern problem[END_REF], the notion of interval graphs is used extensively throughout the section. An interval graph is an intersection graph of a finite family of intervals, all defined over a single line [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF][START_REF] Mckee | Topics in intersection graph theory[END_REF]. Given a 2-interval D = (I, J), let C(D) denote the smallest interval that covers D, i.e., C(D) = [l(I) : r(J)] where l(I) and r(J) are the left and right endpoints of I and J, respectively. Blin et al. [START_REF] Blin | New results for the 2-interval pattern problem[END_REF] called C(D) the covering interval of D. They also observed that any pair of disjoint 2-intervals are {⊏, ≬}-comparable if and only if their corresponding covering intervals intersect. Thus, given a set of 2-intervals D, and the set C(D) of all covering intervals of 2-intervals in D, any {⊏, ≬}-comparable subset D ′ ⊆ D corresponds to a pairwise intersecting subset of C ′ ⊆ C(D). However, the converse is not true as a pair of non-disjoint 2-intervals have corresponding intersecting covering intervals as well. Hence, a pairwise intersecting subset of C(D) can contain corresponding 2-intervals which are non-disjoint in D.

Let D be the input set of 2-intervals and C(D) be the set of covering intervals of all 2-intervals in D. First, we construct the interval graph Ω C(D) of C(D).

Since Ω C(D) is an interval graph, it has at most |V (Ω C(D) )| = |D| maximal (in containment order) cliques, and all these maximal cliques can be computed in polynomial time [START_REF] Gavril | Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph[END_REF]. Note that any pair of 2-intervals with covering intervals in a maximal clique, are either nesting or crossing (but not preceding), or they are non-disjoint. Now, let OP T denote a maximum cardinality {⊏, ≬}-comparable subset of D and let C(OP T ) be the set of covering intervals of OP T . The subgraph of Ω C(D) which corresponds to C(OP T ) is a clique, and is thus a subset of a maximal clique in Ω C(D) . Furthermore, any 2-interval with a covering interval in this clique and not in OP T is necessarily non-disjoint with at least one of the 2-intervals in OP T .

Observation 1. Let OP T denote the maximum {⊏, ≬}-comparable subset of D. Then OP T is a maximum pairwise disjoint subset of a set of 2-intervals D ′ , OP T ⊆ D ′ ⊆ D, such that C(D ′ ), the covering intervals of OP T , corresponds to a maximal clique in Ω C(D) .

Given the 2-intervals which corresponds to a maximal clique in Ω C(D) , one can use the algorithms in Section 2 to find an approximation of the maximum pairwise disjoint subset of these 2-intervals. A detailed schematic description of our algorithm, which is called {⊏, ≬}-Approx, is given in Figure 3. 4 Approximation algorithms for the {<, ≬} model.

We now turn to considering the 2-Interval Pattern problem over the {< , ≬} model. Recall that the problem is known to be NP-hard for unitary 2interval sets, while for point 2-interval sets the problem is not known to be in P [START_REF] Blin | New results for the 2-interval pattern problem[END_REF]. Thus, in the following section we consider all possible restrictions for the {<, ≬} model. More specifically, we design a 3-approximation algorithm for unitary 2-interval sets which is also a 2-approximation algorithm for point 2interval sets. We later slightly modify this algorithm to obtain a 5-approximation algorithm for balanced 2-interval sets. Finally, we introduce a different more complex modification which yields a 6-approximation algorithm for unlimited 2-interval sets.

Throughout the section, we will use the notion of trapezoid graph [START_REF] Dagan | Trapezoid graphs and their coloring[END_REF][START_REF] Felsner | Trapezoid graphs and generalizations: Geometry and algorithms[END_REF]. Consider two intervals, I ′ and J ′ , defined over two distinct horizontal lines. The trapezoid T = (I ′ , J ′ ) is the convex set of points bounded by I ′ and J ′ , and the two arcs connecting the right and left endpoints of I ′ and J ′ . We call I ′ and J ′ the bottom interval and top interval of T respectively. A family of trapezoids is a finite set of trapezoids which are all defined over the same two horizontal lines. The above definitions imply, that two distinct trapezoids T 1 = (I ′ 1 , J ′ 1 ) and T 2 = (I ′ 2 , J ′ 2 ) in a family of trapezoids are disjoint, i.e., they contain no common point, if and only if (I ′ 1 < I ′ 2 and J ′ 1 < J ′ 2 ) or (I ′ 2 < I ′ 1 and J ′ 2 < J ′ 1 ) holds. If T 1 and T 2 are indeed disjoint, then one trapezoid is completely to left of the other, say for instance T 1 , and this is denoted by T 1 < T 2 . Finally, a trapezoid graph is an intersection graph of a family of trapezoids.

Point and unitary 2-interval sets.

We begin the discussion in this section by first describing an approximation algorithm for point and unitary 2-interval sets. We call this initial algorithm {<, ≬}-Approx. The general outline of {<, ≬}-Approx consists of the following stages: First T (D), a family of trapezoids representing each 2-interval in D is constructed. Next, the maximum pairwise disjoint subset of T (D) is computed using the algorithm proposed in [START_REF] Felsner | Trapezoid graphs and generalizations: Geometry and algorithms[END_REF]. Finally, trapezoids in this subset which correspond to non-disjoint 2-intervals in D are omitted, and the filtered solution is outputted. Definition 4 (Corresponding trapezoid family). Let D be a set of 2intervals, and let α and β be two distinct horizontal lines such that α is below β. The corresponding trapezoid family of D, denoted T (D), is defined as the family containing a single trapezoid T = (I ′ , J ′ ) ∈ D for each 2-interval D = (I, J) ∈ D, where I ′ is defined over α, J ′ is defined over β, and I ′ = I and J = J ′ .

I' 1 I' 2 J' 2 I' 1 J' 1 I 2 I 2 J 2 I 2 J 1 J 2 J 1 I 1 I 1 J 1 J 2 I 1 J' 2 I' 2 J' 1 I' 1 I' 2 J' 1 J' 2 I' 2 I' 1 I 2 J 2 J 1 I 1 J' 2 J' 1
Fig. 4. {<, ≬}-comparable 2-intervals correspond to disjoint trapezoids but the converse is not necessarily true.

Let D be a set of 2-intervals and let T (D) be the corresponding trapezoid family of D. It is not difficult to see that {<, ≬}-comparable 2-intervals in D correspond to disjoint trapezoids in T (D), while {⊏}-comparable 2-intervals in D correspond to intersecting trapezoids in T (D) (see Figure 4). Felsner et al. [START_REF] Felsner | Trapezoid graphs and generalizations: Geometry and algorithms[END_REF] presented an O(n lg n) algorithm for finding a maximum disjoint subset in a family of n trapezoids. Unfortunately, this alone does not suffice in our case since there may be disjoint trapezoids in T (D) which correspond to non-disjoint 2-intervals in D. (see Figure 4). Definition 5 (Clashing intervals). Let I ′ = [l(I ′ ), r(I ′ )] and J ′ = [l(J ′ ), r(J ′ )] be two distinct intervals defined over two distinct horizontal lines such that l(I ′ ) ≤ l(J ′ ). The two intervals I ′ and J ′ clash, if either l(I ′ ) ≤ l(J ′ ) ≤ r(J ′ ) ≤ r(I ′ ) or l(I ′ ) ≤ l(J ′ ) ≤ r(I ′ ) ≤ r(J ′ ). Definition 6 (Clashing trapezoids). Let T 1 = (I ′ 1 , J ′ 1 ) and T 2 = (I ′ 2 , J ′ 2 ) be two distinct trapezoids in a family of trapezoids. The two trapezoids T 1 and T 2 clash, if either I ′ 1 and J ′ 2 clash or I ′ 2 and J ′ 1 clash.

Observation 3. Any pair of 2-intervals in D are {<, ≬}-comparable if and only if their corresponding trapezoids in T (D) are disjoint and do not clash.

Observation 3 is the heart of algorithm {<, ≬}-Approx. Note that the number of maximal (in containment order) pairwise disjoint subsets of T (D) can be exponential, so exhaustively searching through all such subsets for a maximum non-clashing subset is unfeasible. Let T ′ be the maximum pairwise disjoint subset of T (D). Since the optimal solution OP T ⊆ D also corresponds to a pairwise disjoint non-clashing subset of trapezoids, we must have |OP T | ≤ |T ′ |. Next we show how to obtain a a pairwise non-clashing subset of T ′ which is no more than a constant factor smaller then OP T , in case D is either a point or unitary 2-interval set. Namely, we find a subset of T ′ which is an approximation of OP T .

Consider the leftmost trapezoid T 0 of T ′ and let D 0 be its corresponding 2-interval in D. By our definition of a 2-interval and of T (D), any trapezoid in T (D), has a bottom interval which is completely to the left of its top interval. Thus, T 0 can only clash with trapezoids on its right in T ′ . Now, if D is a point 2interval set, then all 2-intervals with left intervals intersecting the right interval of D 0 have the same left interval, and as T ′ is pairwise disjoint, at most one of these has a corresponding trapezoid in T ′ . Furthermore, if D is a unitary 2-interval set, intersecting intervals involved in D must overlap. Thus, any trapezoid in T ′ clashing with T 0 corresponds to a 2-interval with a left interval which contains either endpoints, but not both, of the right interval of D 0 . Since T ′ is pairwise disjoint, there can be at most two such trapezoids in T ′ .

Algorithm {<, ≬}-Approx first computes T ′ the maximum pairwise disjoint subset of T (D), and then repeatedly adds the leftmost trapezoids in T ′ to the solution while omitting all trapezoids which clash with this trapezoid in T ′ . A schematic description of algorithm {<, ≬}-Approx is given in Figure 5. time. In addition, each iteration in step 3 of the algorithm can easily be computed by scanning T ′ a constant number of times. As there are O(n) iterations all together, it follows that step 3, and consequently algorithm {<, ≬}-Approx, can be computed in O(n 2 ) time. In fact, if we sort all the right endpoints of intervals involved in D in an O(n lg n) preprocessing stage, we can compute each iteration of step 3 in linear time with respect to the number of trapezoids omitted. As there is only a constant number of such trapezoids in each iteration, step 3 can be computed in O(n) time. This yields a total of O(n lg n) running time.

Definition 2 (

 2 The 2-Interval Pattern problem). Let D be a set of 2intervals and let R ⊆ {<, ⊏, ≬}, R = ∅, be a given model. The 2-Interval Pattern problem asks to find a maximum cardinality R-comparable subset of D. By the above definition, any solution for the 2-Interval Pattern problem over a model R corresponds to a secondary structure constrained by R. Let D be a set of 2-intervals and let S(D) = {I, J : D = (I, J) ∈ D} be the set of intervals involved in D. Several biologically motivated restrictions on D and S(D) are of interest.

3 Fig. 1 .Definition 3 .

 313 Fig. 1. Restrictions for 2-interval sets. Intervals are represented by dark lines or circles and 2-intervals are represented by a thin line connecting two intervals. (a) A point 2-interval set where D1 ≬ D2 and D1 < D3. D2 and D3 are not disjoint and thus are not comparable by any relation. (b) A unitary 2-interval set where D1 ≬ D2, D1 < D3, and D2 < D3. (c) A balanced 2-interval set where D3 ⊏ D2. The entire set is {<, ⊏}comparable. (d) An unlimited {<, ⊏, ≬}-comparable 2-interval set.

Lemma 1 .

 1 Fig. 2. A schematic description of algorithm Bal-{<, ⊏, ≬}-Approx.

Algorithm 1 . 3 .Fig. 3 .

 133 Fig. 3. A schematic description of algorithm {⊏, ≬}-Approx.

Lemma 2 .

 2 Algorithm {⊏, ≬}-Approx is a 4-approximation (3-approximation) algorithm for the 2-Interval Pattern problem for unlimited (unitary) 2interval sets. Proof. Immediate from the above discussion and from Proposition 1 and Lemma 1. ⊓ ⊔ Time complexity. The number of sub-procedure invocations in step 4(b) of {⊏ , ≬}-Approx is bounded by O(n) where n denotes the size of the input set. Also, generating all maximal cliques of Ω C(D) can be done in O(n 2 ) time. Hence, we have a super-quadratic running time of O(n 2 lg n) for unitary 2-interval sets and a O(n 3 ) running time for balanced 2-interval sets. For unlimited 2-interval sets, the running time of {⊏, ≬}-Approx is polynomial [2].

Observation 2 .

 2 Any two disjoint 2-intervals in D are {<, ≬}-comparable if and only if their corresponding trapezoids in T (D) are disjoint.

Algorithm 1 .Fig. 5 .

 15 Fig. 5. A schematic description of algorithm {<, ≬}-Approx.

Table 1 .

 1 The 2-Interval Pattern problem over it's various models and restrictions. Left part: Classical complexity results for the 2-Interval Pattern problem, where n = |D|. Right part: The approximation factors we obtain in this paper.

	Approximation factors
	Model	Unl. Bal. Uni. Pnt.
	{<, ⊏, ≬} (Section 2) 4 a 4 a {⊏, ≬} (Section 3) {<, ≬} (Section 4) 6 b	4 b 4 d 3 e 3 c 5 b 3 c 2 c --
	a Polynomial-time [2].
	11]

b O(n 2 ) time algorithm. c O(n lg n) time algorithm [2]. d O(n 3 ) time algorithm. e O(n 2 lg n) time algorithm.

Partially supported by the Israel Science Foundation grant 282/01.

Balanced 2-interval sets.

We next consider balanced 2-interval sets. We show that a slight modification to algorithm {<, ≬}-Approx yields a 5-approximation algorithm for this case. We call this new algorithm Bal-{<, ≬}-Approx. Algorithm Bal-{<, ≬}-Approx differs from {<, ≬}-Approx only by the fact that at each iteration of step 3, instead of choosing the leftmost trapezoid in T ′ , the smallest trapezoid (i.e., the trapezoid corresponding to the smallest 2-interval) amongst all trapezoids in T ′ is chosen for the solution. The rest of this section is devoted to the 2-Interval Pattern problem over the {<, ≬} model for unlimited 2-interval sets. We introduce a slightly more delicate modification of {<, ≬}-Approx to obtain a 6-approximation algorithm for the unlimited case. For this, we consider special trapezoid families which have structures that are convenient for our purposes.

Definition 7 (Proper trapezoid family). A family of trapezoids T is proper if for any two distinct trapezoids

Definition 8 (Strongly proper trapezoid family). A proper family of trapezoids T is strongly proper if for any two distinct trapezoids

, where l(J ′ 1 ), r(J ′ 1 ) and l(I ′ 2 ), r(I ′ 2 ) are the left and right endpoints of J ′ 1 and I ′ 2 respectively.

Note that by the above definition, any pairwise disjoint family of trapezoids is proper, but the converse is not true. Thus, T ′ ⊆ T computed at step 2 of {<, ≬}-Approx is a proper trapezoid family. Also, computing a strongly proper subset T ′′ ⊆ T ′ can be done easily by adjusting step 3 of {<, ≬}-Approx. Instead of omitting all trapezoids clashing with the leftmost trapezoid in this iteration, we need only to omit a small subset of these trapezoids. More specifically, let T 0 = (I ′ 0 , J ′ 0 ) be the leftmost trapezoid in T ′ . We only omit trapezoids

. It is not difficult to see that we obtain a strongly proper trapezoid family T ′′ ⊆ T ′ if we proceed in this fashion and that |T ′′ | ≥ 1 3 |T ′ |. Definition 9 (Clashing trapezoid graph). Given a family T of trapezoids, the clashing trapezoid graph of T , denoted by G T , is the graph such that each vertex in V (G T ) corresponds to a distinct trapezoid in T , and two vertices are connected by an edge if and only if their corresponding trapezoids clash. Lemma 5. Let T be a family of trapezoids. If T is strongly proper then G T is a forest.

Proof. Let T be a strongly proper family of trapezoids and let G T be its corresponding clashing trapezoid graph. Define G * T as the directed graph obtained be orientating the edges of G T according to the precedence relation of T . In other words,

Since T is strongly proper, every trapezoid in T clashes with at most one trapezoid on its left, and so the in-degree of every vertex

However, in such a case we must have T 0 < T t < T 0 by definition of G * T , which is clearly a contradiction. Hence, we conclude that G * T , and consequently G T , contain no cycles, and the above lemma holds.

⊓ ⊔

It is well known that the maximum independent set in any forest G is of size at least 1 2 |V (G)| and that this set can be found in linear time with respect to |V (G)|. Also, by definition, if T ′′ is a pairwise disjoint family of trapezoids, then any independent set of G T ′′ corresponds to a pairwise disjoint non-clashing set of trapezoids, which by Observation 3, corresponds to a {<, ≬}-comparable set of 2-intervals. A schematic description of our algorithm for unlimited 2-intervals sets, called Unl-{<, ≬}-Approx, is given in Figure 6. Lemma 6. Algorithm Unl-{<, ≬}-Approx is a 6-approximation algorithm for the 2-Interval Pattern problem over the {<, ≬} model.

Proof. Let D be the input set of 2-intervals and let T (D), T ′ and T ′′ be the trapezoid families as described in the above description of Unl-{<, ≬}-Approx. Also, denote by OP T the maximum {<, ≬}-comparable subset of D. We have

Accumulating all these inequalities together we get: Step 3 can be computed straightforwardly in O(n 2 ) time. Finally, step 4 can be computed in O(n) time since G T ′′ is a forest. Thus, the whole algorithm can be implemented to run in O(n 2 ) time.