D Loyal

A.-L Sutter

N Rascle

Screening Beyond Postpartum Depression: Occluded Anxiety Component in the EPDS (EPDS-3A) in French Mothers

Keywords: Anxiety symptoms, Depression symptoms, Edinburgh Postnatal Depression Scale, Postpartum, Pregnancy EPDS-3A IN FRANCE

Introduction.

According to many studies, anxiety in the perinatal period is widespread and has many detrimental effects. Thus, screening measures should not be limited to assessing depression symptoms. The widely used Edinburgh Postnatal Depression Scale (EPDS) might assess depression but also anxiety symptoms. This study explores whether an anxiety dimension (EPDS-3A) was found and valid in French women during pregnancy and the postpartum period.

Methods. French women were followed-up at late pregnancy and 2 and 4 months postpartum (N = 144, 138 and 129). They completed the EPDS and the Hospital Anxiety and Depression Scale (HADS-A). Exploratory factor analyses were performed. Then to test its validity, the EPDS-3A was correlated with anxiety (HADS-A) and depression (EPDS-D) scores. Finally, prevalence estimates were computed according to recommended cut off.

Results. The anxiety dimension assessed through the EPDS-3A was observed during the postpartum period but not during pregnancy. A two-factor structure (depression and anxiety) increases the variance explained at 2 and 4 months postpartum (respectively 6 and 12%). The EPDS-3A shows good internal consistency (≥.70) and was more strongly associated with anxiety scores (HADS-A) (.48-.57) than with depression scores (EPDS-D) (.30-.39). Nearly 28% of mothers had scores that exceeded the EPDS-3A cut off (≥ 4) but not the full EPDS cut off (≥ 13 or more).

Discussion: The EPDS contains an anxiety component (EPDS-3A) that can be found in French women during the postnatal period but not during pregnancy. It shows signs of internal consistency and validity. The EPDS-3A could be considered when screening for postpartum anxiety.

Introduction

Postpartum depression is a debilitating condition seen in 13-19% of women giving birth [START_REF] O'hara | Rates and risk of postpartum depression : A meta-analysis[END_REF] that may have major consequences for children such as psychopathological disorders, impaired cognitive development, and insecure attachment [START_REF] O'hara | Postpartum depression : Current status and future directions[END_REF]. This condition is linked to strong risk factors, such as a past history of depression and symptoms of anxiety and depression during pregnancy. Other risk factors have been described such as low social support, low socioeconomic status, personality traits, and perinatal complications [START_REF] Robertson | Antenatal risk factors for postpartum depression : A synthesis of recent literature[END_REF]. Furthermore, 12-18% of women are suffering from depression while pregnant [START_REF] Bennett | Prevalence of depression during pregnancy : Systematic review[END_REF]. Antenatal depression has been associated with poorer child development [START_REF] Kingston | Prenatal and Postpartum Maternal Psychological Distress and Infant Development : A Systematic Review[END_REF] and obstetric issues [START_REF] Grigoriadis | The Impact of Maternal Depression During Pregnancy on Perinatal EPDS-3A IN FRANCE 15 Outcomes : A Systematic Review and Meta-Analysis[END_REF].

Postpartum depression has been described for long as including prominent anxious features [START_REF] Pitt | Atypical » depression following childbirth[END_REF]. In new mothers and pregnant women, anxiety symptoms might even be more frequent than depression symptoms [START_REF] Farr | Postpartum anxiety and comorbid depression in a population-based sample of women[END_REF]. Anxiety in new mothers has been associated with child impaired cognitive development [START_REF] Kingston | Prenatal and Postpartum Maternal Psychological Distress and Infant Development : A Systematic Review[END_REF] and emotional and behavioral troubles [START_REF] Glasheen | A systematic review of the effects of postnatal maternal anxiety on children[END_REF]. Moreover, anxiety in pregnancy might be linked with negative obstetric issues [START_REF] Alder | Depression and anxiety during pregnancy : A risk factor for obstetric, fetal and neonatal outcome? A critical review of the literature[END_REF]. Thus, many scholars are arguing that depression symptoms should not be the only focus of attention when dealing with distressed mothers and mothers-to-be [START_REF] Rallis | The transition to motherhood : Towards a broader understanding of perinatal distress[END_REF][START_REF] Who | Mental Health Aspects of Women's Reproductive Health : A Global Review of the Literature[END_REF].

In view of this evidence, assessing anxiety in pregnant women and new mothers seems important. Moreover, depression and anxiety should be distinguished because they might have distinct prevalence rates, longitudinal course, and treatment [START_REF] Rivas-Vazquez | Current issues in anxiety and depression : Comorbid, mixed, and subthreshold disorders[END_REF]). In addition, comorbid symptoms of depression and anxiety are frequent and seem to be a sign of severity [START_REF] Farr | Postpartum anxiety and comorbid depression in a population-based sample of women[END_REF][START_REF] Rivas-Vazquez | Current issues in anxiety and depression : Comorbid, mixed, and subthreshold disorders[END_REF].

EPDS-3A IN FRANCE 4

The most widely used instrument to assess depression symptoms in mothers and in pregnant women [START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF] is the Edinburgh Postnatal Depression Scale (EPDS) [START_REF] Cox | Detection of postnatal depression : Development of the 10-item Edinburgh Postnatal Depression Scale[END_REF]. This scale contains 10 items with 4 possible responses (0-3). During pregnancy and the postpartum, cut off of 13 or more (major depression) and 10 or more (minor depression) are usually recommended [START_REF] Cox | Detection of postnatal depression : Development of the 10-item Edinburgh Postnatal Depression Scale[END_REF][START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF]. The EPDS has been validated in various languages, shows good psychometric qualities [START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF]. and is well accepted by recipients [START_REF] Brealey | Screening for postnatal depressionis it acceptable to women and healthcare professionals? A systematic review and meta-synthesis[END_REF].

The EPDS is supposed to provide a one-dimensional measure of depression symptoms.

However, some studies support a two-factor structure covering depression and anxiety. Items 3, 4 and 5 have been repeatedly found to load on an anxiety dimension [START_REF] Matthey | Using the Edinburgh postnatal depression scale to screen for anxiety disorders : Conceptual and methodological considerations[END_REF][START_REF] Reichenheim | Revisiting the dimensional structure of the Edinburgh Postnatal Depression Scale (EPDS) : Empirical evidence for a general factor[END_REF]. This dimension has been labelled EPDS-3A by [START_REF] Matthey | Using the Edinburgh postnatal depression scale to screen for anxiety disorders : Conceptual and methodological considerations[END_REF]. Some authors have suggested an EPDS-3A cut-off of 6 or more or 4 or more [START_REF] Matthey | Using the Edinburgh postnatal depression scale to screen for anxiety disorders : Conceptual and methodological considerations[END_REF].

Adding up all items of a multidimensional scale such as the EPDS could be unwarranted. Indeed, different dimensions might have various risk factors and consequences which would not be distinguishable if all items are summed up [START_REF] Reichenheim | Revisiting the dimensional structure of the Edinburgh Postnatal Depression Scale (EPDS) : Empirical evidence for a general factor[END_REF]. Thus, the structure of the EPDS should be explored, especially regarding the 3 items (items 3, 4 and 5) that might assess anxiety (EPDS-3A). Moreover, Items 6, 7 and 8 are often ill behaved [START_REF] Reichenheim | Revisiting the dimensional structure of the Edinburgh Postnatal Depression Scale (EPDS) : Empirical evidence for a general factor[END_REF]. Item 7 might be difficult to answer as women might have difficult time sleeping because of body changes and baby sleep patterns [START_REF] Brealey | Screening for postnatal depressionis it acceptable to women and healthcare professionals? A systematic review and meta-synthesis[END_REF]. Moreover, item 10 might be poorly understood as it might be read as referring to unintentional injury, deliberate self-harm or suicide [START_REF] Brealey | Screening for postnatal depressionis it acceptable to women and healthcare professionals? A systematic review and meta-synthesis[END_REF].

The present study was designed to explore the structure of the EPDS in a sample of French women during pregnancy and the postpartum period. Items 3, 4 and 5 were expected to load on an anxiety dimension (EPDS-3A). The EPDS-3A was expected to exhibit convergent validity in comparison with another scale assessing anxiety. Prevalence estimates were also computed.

Methods

Procedure and Participants

Pregnant women were recruited at the maternity ward of a local French university hospital during a mandatory information meeting about childbirth pain relief. Participants had to be fluent in French (spoken and written) and to be older than 18 years. They had to have no multiple pregnancy or medically assisted procreation because it might lead to anxiety and depression symptoms or obstetric complication [START_REF] Fisher | Maternal perinatal mental health and multiple births : Implications for practice[END_REF][START_REF] Hammarberg | Psychological and social aspects of pregnancy, childbirth and early parenting after assisted conception : A systematic review[END_REF].

During last trimester of pregnancy (T1) participants were received in an office of the maternity ward. They completed a set of self-administered questionnaires. Then, 2 months (T2) and 4 months (T3) after the birth, they were asked to answer self-administrated questionnaires online.

Informed consent was obtained during the last trimester of pregnancy (T1) from all individual participants included in the study. All participants were informed that they would be solicited three times and that they were free to stop their participation at any time. All procedures were in accordance with the ethical standards of the institutional and/or national research committee and with the 1964 Helsinki declaration and its later amendments. This study was approved by a national informatics right committee (https://www.cnil.fr/) and a regional ethic committee (http://www.cpp-soom3.u-bordeaux2.fr/).

Measures

The French version of the EPDS [START_REF] Cox | Detection of postnatal depression : Development of the 10-item Edinburgh Postnatal Depression Scale[END_REF][START_REF] Guedeney | Validation study of the French version of the Edinburgh Postnatal Depression Scale (EPDS) : New results about use and psychometric properties[END_REF] was selfadministered. As said previously, it contains 10 items proposed with 4 possible responses rated from 0 to 3. Owing to Exploratory Factor Analyses results presented thereafter, in addition to the usual full EPDS score (all items), two scores have been computed to assess anxiety symptoms (EPDS-3A including items 3, 4 and 5) and depression symptoms (EPDS-D including items 1, 2, 7, 8, 9 and 10).

Item 6 was dropped because of low loadings.

The French validation of the Hospital Anxiety and Depression Scale or HADS [START_REF] Lepine | Evaluation of anxiety and depression among patients hospitalized on an internal medicine service[END_REF][START_REF] Zigmond | The Hospital Anxiety and Depression Scale[END_REF]) was used to measure anxiety symptoms. This self administrated scale contains 14 items assessing depression symptoms (7 items) and anxiety symptoms (7 items). Each item is offered with 4 possible responses rated from 0 to 3. A two-factor structure is usually observed, but some scholars have observed other structure [START_REF] Cosco | Latent structure of the Hospital Anxiety And Depression Scale : A 10-year systematic review[END_REF]. To assess anxiety, [START_REF] Straat | Methodological artifacts in dimensionality assessment of the Hospital Anxiety and Depression Scale (HADS)[END_REF] have recommended to use 5 items (items 1, 2, 3, 5 and 7). Those 5 items have been used and this score will be referred as HADS-A. At each measurement time, the HADS-A had great internal consistencies (>.70).

Statistical analysis

Exploratory Factor Analysis (EFA) was computed. Our sample size is sufficient to perform such an analysis [START_REF] Costello | Best Practices in Exploratory Factor Analysis : Four Recommendations for Getting the Most From Your Analysis[END_REF]. Principal Factor extraction and Oblimin rotation were chosen [START_REF] Costello | Best Practices in Exploratory Factor Analysis : Four Recommendations for Getting the Most From Your Analysis[END_REF]. Cut off for loading was >.40 [START_REF] Costello | Best Practices in Exploratory Factor Analysis : Four Recommendations for Getting the Most From Your Analysis[END_REF]). An anxiety dimension comprising items 3, 4 and 5 (EPDS-3A) was expected.

Secondly, Spearman correlations were computed to assess relations between anxiety scores (EPDS-3A and HADS-A) and depression score (EPDS-D). The EPDS-3A was expected to be associated more strongly anxiety scores (HADS-A) than with depression scores (EPDS-D).

In addition, prevalence have been estimated according to recommended cut off for the full EPDS (≥ 10 or 13) and the EPDS-3A (≥ 4 or 6). Finally, percentage of women whose scores exceeded the EPDS-3A cut-off but not the full EPDS cut-off have been estimated.

Results

Descriptive Statistics

Sample description is provided in Table 1. Participants (T1, N = 144) were on average 30.9 years old (SD = 4.15). They were mostly born in France (93.8%), well educated (70.8% had ≥ 3 years of post-secondary education) and working (80.6%) at least 35 hours per week (88%) in intermediate or highly skilled job (75%). Most of them were engaged in a relationship (97.9%). The sample includes mainly first-time mothers (72.9%). Women who already had children had mostly one child (84.6%) about 3 years old (M = 37.5 months, SD = 18.86 months). For most participants the pregnancy was described as planned (84%) and happily welcomed (82.6%). Regarding major obstetric complications some participants have reported a complicated or emergency C-section (8.7%) but none reported that the baby was born prematurely (>30 days), underweighted (<2 kg) or put in an incubator (>4 weeks).

INSERT TABLE 1

Some participants (N = 15) were lost at follow up between the last trimester of pregnancy (T1, N = 144), 2 months (T2, N = 138) and 4 months postpartum (T3, N = 129). Using Fisher Exact Test, it was estimated that they were more often born abroad (20% vs. 4.7%, p<.05) and less educated (53.3% vs. 26.4% with ≤ 2 years of post-secondary education, p<.05). Many reported having an unplanned pregnancy (53.3% vs 11.6%, p<.01). Even if there is no established cut off for missing data, proportions lower than 5 or 10% are usually regarded as having few or no consequences [START_REF] Bennett | How can I deal with missing data in my study?[END_REF][START_REF] Dong | Principled missing data methods for researchers[END_REF].

Exploratory Factor Analysis

Scree plots (Figure 1) suggest that one strong factor might be extracted. However, a second factor might be extracted especially in T3 data. Extracting a third factor might not be insightful. EFA results regarding each measurement time are presented in Table 2, 3 and4. INSERT FIGURE 1 INSERT TABLE 2, 3 and 4.

Broadly speaking, a one-factor structure is satisfactory at T1, T2 and, to a lesser extent, at T3. However, choosing a two-factor structure rather than a one-factor structure increases substantially the variance explained at T1 (+8%), T2 (+6%) and especially at T3 (+12%). A three-factor structure seems unsatisfactory mainly because it produces single item "dimensions" and even a Heywood case (T1). Moreover, it adds few explained variance. At T1 (Table 2) one should note that item 10 fails to load on any dimension irrespective of the number of dimension. The two-factor structure was comprised of a depression dimension (items 1, 2, 3, 6, 7, 8 and 9) and an anxiety dimension (items 4 and 5). In sum, 43% of the variance was explained by depression (31%) and anxiety (12%). Internal consistencies were satisfactory for each dimension (>.70). However, the EPDS-3A (item 3, 4 and 5) was not observed.

At T2 (Table 3), the two-factor structure was comprised of a depression dimension (items 1, 2, 7, 8, 9 and 10) and the EPDS-3A anxiety dimension (items 3, 4 and 5). Item 6 fails to load on both dimensions. In sum, 45% of the variance was explained by depression (27%) and anxiety (18%).

Internal consistencies were satisfactory for each dimension (>.70).

At T3 (Table 4), the two-factor structure was comprised of a depression dimension (items 1, 2, 7, 8, 9 and 10) and the EPDS-3A anxiety dimension (items, 3, 4 and 5). Item 6 fails to load on both dimensions. In sum 44% of the variance was explained by depression (29%) and anxiety (15%).

Internal consistencies were satisfactory for each dimension (>.70).

Convergent and Divergent Validity

The expected anxiety dimension (EPDS-3A) was observed only in the postpartum (T2 and T3). Thus at T2 and T3, two scores were computed from the EDPS: the EPDS-D (items 1, 2, 7, 8, 9 and 10) and the EPDS-3A (items 3, 4 and 5). Item 6 was dropped because of low loadings.

Spearman correlations between each scores from the EPDS (EPDS-D and EPDS-3A) and the HADS-A were computed at T2 and T3. At T2, correlation between EPDS-3A and HADS-A (.57) was significantly higher than correlation between EPDS-3A and EPDS-D (.39) (Z = -2.05, p<.05) [START_REF] Lee | Calculation for the test of the difference between two dependent correlations with one variable in common Available from http://quantpsy[END_REF]. Similarly, at T3, correlation between EPDS-3A and HADS-A (.48) was significantly higher than correlation between EPDS-3A and EPDS-D (.30) (Z = -1.87, p<.05) [START_REF] Lee | Calculation for the test of the difference between two dependent correlations with one variable in common Available from http://quantpsy[END_REF].

EPDS-3A IN FRANCE 9

Prevalence

Regarding the full EPDS cut-off (≥ 13 or 10) depression symptoms were higher at T2 (9.7-18.1%) than at T3 (4.2-9.7%). Regarding the EPDS-3A cut-off (≥ 6 or 4) anxiety symptoms were also higher at T2 (13.2-36.1%) than at T3 (7.6-25%). There were also more women scoring high on both scales at T2 (7.3-17.5%) than at T3 (3.1-7.8%). Resultst are provided in Table 5.

INSERT TABLE 5

Moreover, many women scoring high on the EPDS-3A were not detected by the full EPDS.

When using a low EPDS-3A cut-off (≥4), many anxious women were not detected by the full EPDS cut-off at T2 (19.7-27.7% with respectively ≥13 and ≥10) and T3 (20.2-24.8% with respectively ≥13 and ≥10). When using a higher EPDS-3A cut-off (≥6), some anxious women were not detected by the full EPDS cut-off at T2 (1.5-5.8% with respectively ≥13 and ≥10) and T3 (3.1-5.4% with respectively ≥13 and ≥10). Resultst are provided in Table 6.

INSERT TABLE 6

Discussion

The expected anxiety dimension (EPDS-3A), including items, 3, 4 and 5, was only observed during the postpartum period but not during pregnancy. Thus our first hypothesis regarding the EPDS-3A was partly confirmed.

As expected, item 4 and 5 were continuously loading on an anxiety factor. However item 3, which was supposed to assess anxiety [START_REF] Matthey | Using the Edinburgh postnatal depression scale to screen for anxiety disorders : Conceptual and methodological considerations[END_REF][START_REF] Reichenheim | Revisiting the dimensional structure of the Edinburgh Postnatal Depression Scale (EPDS) : Empirical evidence for a general factor[END_REF] was loading on an anxiety factor during the postpartum but was loading on a depression factor during pregnancy. Item 3 is explicitly referring to self-blame which is a well-known component of depression [START_REF] Beck | Depression : Clinical, Experimental, and Theoretical Aspects[END_REF]. It remains unclear why such a result was obtained during pregnancy but not during the postpartum period. Maybe pregnant women and new mothers are not referring to the same "things" when they answer item 3 ("I have blamed myself unnecessarily when things went wrong"). Indeed, stressors experienced by pregnant women and new mothers might be different (DiPietro, Ghera, Costigan, & EPDS-3A IN FRANCE 10 Hawkins, 2004;[START_REF] Jevitt | Postpartum Stressors : A Content Analysis[END_REF]. Furthermore, item 6 was ill-adapted, especially during the postpartum when it fails to load on depression or anxiety dimensions. This item might be poorly adapted to cover either anxiety or depression. Items 7 and 8 which had been previously identified as ill-behaved [START_REF] Reichenheim | Revisiting the dimensional structure of the Edinburgh Postnatal Depression Scale (EPDS) : Empirical evidence for a general factor[END_REF] were quite robust in our analysis.

Those items were loading clearly on a depression dimension. Item 10 fails to load on any dimensions during pregnancy. Our guess is that this item might be poorly understood as it might be read as referring to unintentional injury, deliberate self-harm or suicide [START_REF] Brealey | Screening for postnatal depressionis it acceptable to women and healthcare professionals? A systematic review and meta-synthesis[END_REF]. This problem might be especially true in pregnant women who might fear hurting themselves and their unborn child by accident. In sum, questions were raised regarding some items: item 3 might assess depression rather than anxiety in pregnant women, item 6 might assess poorly either anxiety or depression and item 10 might be ambiguous especially for pregnant women.

As expected, it was observed that the anxiety dimension assessed through the EPDS-3A was more strongly correlated with the HADS-A than with the EPDS-D. This stronger correlation is indicative of its convergent validity. Our second hypothesis stating that the EPDS-3A would exhibit convergent validity was confirmed during the postpartum period.

In accordance with many studies [START_REF] Farr | Postpartum anxiety and comorbid depression in a population-based sample of women[END_REF][START_REF] Grant | Maternal anxiety during the transition to parenthood : A prospective study[END_REF], anxiety symptoms seem to be more prevalent than depression symptoms in new mothers. Moreover, anxiety and depression symptoms might be more prevalent at 2 months postpartum than at 4 months postpartum. This higher prevalence during the early postpartum has been observed previously regarding depression [START_REF] Moss | Depressive and anxiety symptoms through late pregnancy and the first year post birth : An examination of prospective relationships[END_REF] but not regarding anxiety which is rather found to grow stronger through the postpartum [START_REF] Moss | Depressive and anxiety symptoms through late pregnancy and the first year post birth : An examination of prospective relationships[END_REF]. Our results also highlight that when using the full EPDS score one does not screen efficiently for women with high anxiety symptoms (EPDS-3A). Many new mothers (up to 28%) are exhibiting anxiety symptoms (EPDS-3A) and are not screened by the EPDS scored as a whole.

However, one should note that the EPDS-3A items (items 3, 4 and 5) share a common formulation indicating a judgment about one's own feelings ("unnecessarily", "for no good reason" and "for no very good reason") [START_REF] Brouwers | Does the Edinburgh Postnatal Depression Scale measure anxiety[END_REF]. This formulation might produce an artificial dimension. Moreover, the EPDS-3A does not include items about somatic symptoms which are important in anxiety [START_REF] Brouwers | Does the Edinburgh Postnatal Depression Scale measure anxiety[END_REF]. Some authors argue that such symptoms should not be considered because they might be confounded with normal somatic symptoms occurring after birth [START_REF] O'hara | Postpartum depression : Current status and future directions[END_REF]. Nevertheless, depressed or anxious new mothers [START_REF] Woolhouse | Physical health after childbirth and maternal depression in the first 12 months post partum : Results of an Australian nulliparous pregnancy cohort study[END_REF] and pregnant women [START_REF] Yonkers | Typical somatic symptoms of pregnancy and their impact on a diagnosis of major depressive disorder[END_REF] are experiencing higher somatic symptoms. Thus, somatic symptoms should not be dismissed as trivial. Our guess is that scales should, in addition to emotional items, include somatic items and conduct analysis to determine appropriate cut-off for such scores. The presence of somatic symptoms only could be considered as not indicative of anxiety. Finally, the EPDS-3A performance to screen for women with perinatal anxiety disorders remains ambiguous [START_REF] Fairbrother | Screening for perinatal anxiety disorders : Room to grow[END_REF][START_REF] Matthey | Using the Edinburgh postnatal depression scale to screen for anxiety disorders : Conceptual and methodological considerations[END_REF]. Our guess is that this scale might undergo substantial improvements [START_REF] Fairbrother | Screening for perinatal anxiety disorders : Room to grow[END_REF].

The EPDS itself should be considered with caution. This scale is widely used in new mothers and, to a lesser extent, in pregnant women [START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF]. However, it does not contain item about pregnancy, childbirth, child or childcare, although studies have showed that new mothers are experiencing specific stressors and anxieties [START_REF] Phillips | Maternally focused worry[END_REF]. Some interesting scales have been designed to assess specific anxieties during pregnancy (child health, childbirth and one own physical attractiveness) [START_REF] Reymond | Validation française d'une échelle d'anxiété spécifique à la grossesse (PRAQ-R2)[END_REF] and after birth (maternal competence, infant safety, childcare and personal adjustment to motherhood) [START_REF] Fallon | The Postpartum Specific Anxiety Scale : Development and preliminary validation[END_REF].

This study has many strengths. First, to our knowledge, it is the first to explore the EPDS-3A in a sample of French women. Moreover, its longitudinal design has made it possible to search for the EPDS-3A in both the postpartum period (2 and 4 months) and the last trimester of pregnancy, which has never been done before. Finally, our sample size was adequate to conduct EFA under proper conditions [START_REF] Costello | Best Practices in Exploratory Factor Analysis : Four Recommendations for Getting the Most From Your Analysis[END_REF]. However, this study suffers some limitations. First, participants answered self-administrated scales after a face-to-face interview in late pregnancy (T1)

EPDS-3A IN FRANCE

and online after the birth (T2 and T3). This study was designed this way to ease participation and ensure a low attrition rate. Secondly, our participants were privileged women, educated and engaged in skilled jobs. However, using a recommended cut-off to assess major and minor depression episode (EPDS ≥10 ) [START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF] we get prevalence of 18.1 % at 2 months postpartum and 9.7% at 4 months postpartum. These prevalence are similar to those observed in the literature with the EPDS [START_REF] O'hara | Postpartum depression : Current status and future directions[END_REF][START_REF] O'hara | Rates and risk of postpartum depression : A meta-analysis[END_REF]. The correlation between symptoms of depression (EPDS-D) and anxiety (EPDS-3A) was found to be quite moderate in our sample (.30-.39). One can expect that this association could be stronger in a population with a higher prevalence of both troubles.

One should note that in our sample at 2 months postpartum, a sizeable number of women were exhibiting comorbid anxious and depressive symptoms (7.3-17.5%). Further research should consider using confirmatory factor analysis to establish model fit for one-dimensional and bi-dimensional models. Moreover, our guess is that future studies about the EPDS-3A should include both generic measures of anxiety and depression symptoms and specific measures assessing specific worries occurring during pregnancy and after birth.

Our results highlight that the EPDS has an occluded anxiety component (EDPS-3A).

However, the anxiety dimension assessed through the EPDS-3A was observed during the postpartum period but not during pregnancy. The EPDS-3A showed good internal consistency and convergent validity. To our knowledge it is the first French study to test the existence of an occluded anxiety component in the EPDS during pregnancy and the postpartum. The EPDS, is the most frequently used instrument, it is brief, has been extensively validated [START_REF] Gibson | A systematic review of studies validating the Edinburgh Postnatal Depression Scale in antepartum and postpartum women[END_REF] and is well accepted by recipients [START_REF] Brealey | Screening for postnatal depressionis it acceptable to women and healthcare professionals? A systematic review and meta-synthesis[END_REF]. Further research might explore more fully the clinical relevance of scoring separately the anxiety dimension (EPDS-3A) of the EPDS. Indeed, it is essential to distinguish depression and anxiety symptoms because they have a distinct pattern in terms of prevalence rates, symptom profile, longitudinal course, and response to treatment [START_REF] Rivas-Vazquez | Current issues in anxiety and depression : Comorbid, mixed, and subthreshold disorders[END_REF].

Moreover, identifying women who score high on both depression and anxiety might help screening the most vulnerable ones [START_REF] Farr | Postpartum anxiety and comorbid depression in a population-based sample of women[END_REF]. Note. Full EPDS (all items) EPDS-3A (items 3, 4 and 5).

Figure 1 .

 1 Figure 1. Scree Plots for T1, T2 and T3 regarding EPDS Data

Table 1 .

 1 Participants Characteristics during Pregnancy (T1, N = 144)

	Variable	M (SD) or %
	Age (years)	30.9 (4.15)
	Born in France	93.75 %
	Engaged in a relationship	97.9%
	First time mother	72.9%
	Previous child	27.1%
	One child	84.6 %
	Youngest child age (months)	37.51 (18.86)
	≥ 3 years post-secondary Education	70.8 %
	Skill Level
	White collar / highly qualified	41.1 %
	Intermediate professional	39 %
	Employees	19.9 %
	Employed	80.6 %
	≥ 35 hours a week	90.5 %
	Pregnancy
	Planned	84%
	Happily welcomed	82.6%
	Obstetric complication
	Complicated or urgent C-section	8.7%
	Prematurity (>30 days)	0%
	Underweight (<2kg)	0%
	Incubator (>4 weeks)

Table 2 .

 2 Factor Structure Regarding EPDS Data (T1, Late Pregnancy)

		1 Factor	2 Factors		3 Factors
		Dep	Dep	Anx	Dep	Anh	Anx
	Item 1. Able to laugh	.60	.66	-.06	.01	1.06 d	.00
	Item 2. Enjoyment to things	.60	.51	.15	.29	.29	.21
	Item 3. Blamed myself	.53	.43	.17	.60	-.16	.12
	Item 4. Been anxious	.42	-.04	.75	-.06	.01	.86
	Item 5. Felt scared	.50	.07	.70	.21	-.04	.58
	Item 6. Getting on top of me	.52	.43	.14	.37	.11	.13
	Item 7. Difficulty sleeping	.74	.79	-.04	.85	-.02	-.07
	Item 8. Felt sad	.84	.82	.06	.63	.22	.13
	Item 9. Crying	.70	.76	-.06	.72	.07	-.04
	Item 10. Harming myself	.29	.24	.08	.34	-.11	.06
	Alpha a	.83 b	.84	.71	.81	---c	.71
	VE Factor	35%	31%	12%	26%	14%	13%
	VE Total	35%	43%			53%
	Note. Suitability to factor analysis was satisfactory (KMO = .81 and Bartlett = X²(45) = 479, p<.01)
	VE = Variance Explained. Loadings above .40 are in bold

a alpha were computed with items having > .40 loadings (in bold).

b All items were included (even item 10 despite low loading).

c Alpha can't be computed for one single item. d Heywood case.

Table 3 .

 3 Factor Structure Regarding EPDS Data (T2)

		1 Factor	2 Factors		3 Factors
		Dep	Dep	Anx	Dep	Anx	Stress
	Item 1. Able to laugh	.52	.45	.09	.32	-.07	.38
	Item 2. Enjoyment to things	.59	.61	.00	.49	-.06	.25
	Item 3. Blamed myself	.57	.05	.60	.06	.46	.19
	Item 4. Been anxious	.65	.00	.76	.02	.88	-.05
	Item 5. Felt scared	.63	-.02	.75	.02	.54	.24
	Item 6. Getting on top of me	.59	.27	.37	.04	.13	.65
	Item 7. Difficulty sleeping	.56	.61	-.03	.63	.04	-.09
	Item 8. Felt sad	.84	.82	.07	.74	.07	.12
	Item 9. Crying	.80	.88	-.04	.92	.00	-.06
	Item 10. Harming myself	.38	.42	-.03	.36	-.01	.07
	Alpha a	.86 b	.80	.75	.82	.75	---c
	VE Factor	39%	27%	18%	25%	15%	10%
	VE Total	39%	45%			50%
	Note. Suitability to factor analysis was satisfactory (KMO = .87 and Bartlett = X²(45) = 493, p<.01)
	VE = Variance Explained. Loadings above .40 are in bold.

a alpha were computed with items having > .40 loadings (in bold).

b All items were included (even item 10 despite low loading).

c Alpha can't be computed for one single item.

Table 4 .

 4 Factor Structure Regarding EPDS Data (T3, 4 months postpartum) Suitability to factor analysis was satisfactory (KMO = .81 and Bartlett = X²(45) = 402, p<.01) VE = Variance Explained. Loadings above .40 are in bold. All items were included (even item 3, 4 and 6 despite low loadings) c Alpha can't be computed for one single item

		1 Factor	2 Factors		3 Factors
		Dep	Dep	Anx	Dep	Anx	Blame
	Item 1. Able to laugh	.71	.67	.08	.64	.15	-.04
	Item 2. Enjoyment to things	.53	.74	-.25	.78	-.30	.04
	Item 3. Blamed myself	.21	-.08	.48	.03	.07	.77
	Item 4. Been anxious	.39	.02	.67	.04	.55	.18
	Item 5. Felt scared	.46	.09	.68	.06	.70	.08
	Item 6. Getting on top of me	.39	.18	.36	.17	.35	.06
	Item 7. Difficulty sleeping	.72	.65	.14	.60	.29	-.15
	Item 8. Felt sad	.86	.74	.22	.76	.15	.13
	Item 9. Crying	.68	.72	-.01	.71	.00	.02
	Item 10. Harming myself	.43	.54	-.12	.47	.09	-.27
	Alpha a	.80 b	.83	.70	.83	.73	---c
	VE Factor	32%	29%	15%	28%	13%	8%
	VE Total	32%	44%			49%
	Note.

a alpha were computed with items having > .40 loadings (in bold) b

Table 5 .

 5 Descriptive Statistics and Prevalence for Full EPDS and EPDS-3A.

		T2 (2 months)	T3 (4 months)
		M (SD)	Prevalence	M (SD)	Prevalence
	Full EPDS 5.82 (4.39)	≥ 13 : 9.7% ≥ 10 : 18.1%	4.91(3.72)	≥ 13 : 4.2% ≥ 10 : 9.7%
	EPDS-3A	2.91 (2.09)	≥ 6 : 13.2% ≥ 4 : 36.1%	2.5 (1.87)	≥ 6 : 7.6 % ≥ 4 : 25 %
	Both	---	≥ 13 + ≥ 6 : 7.3% ≥ 10 + ≥ 4 : 17.5%	---	≥ 13 + ≥ 6 : 3.1% ≥ 10 + ≥ 4 : 7.8%
	Note. Full EPDS (all items) EPDS-3A (items 3, 4 and 5).

Table 6 .

 6 Percentage of participants with scores exceeding EPDS-3A cut-off but not EPDS ones.

	Prevalence

Conflict of interest: the authors declare that they have no conflict of interest.

EPDS-3A IN FRANCE


Guillaume Blin
email: gblin@univ-mlv.fr

Sylvie Hamel
email: hamelsyl@iro.umontreal.ca

Stéphane Vialette
email: vialette@univ-mlv.fr

Comparing RNA structures using a full set of biologically relevant edit operations is intractable

Keywords: RNA structures, Longest Arc-Preserving Subsequence (LAPCS), NP-Hardness, Stem-loops

).

, the authors have used a strong combinatorial restriction in order to compare two RNA stem-loops with a full set of biologically relevant edit operations; which have allowed them to design a polynomial-time and space algorithm for comparing general secondary RNA structures.

In this paper we will prove theoretically that comparing two RNA structures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.

Introduction

In computational biology, comparison of RNA molecules has recently attracted a lot of interest due to the rapidly increasing amount of known RNA molecules, especially non-coding RNAs. Very often, arc-annotated sequences, originally introduced in [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF], are used to represent RNA structures. An arc-annotated sequence is a sequence over a given alphabet together with additional structural information specified by arcs connecting pairs of positions. The arcs determine the way the sequence folds into a three-dimensional space.

The problem of computing an edit distance between two arc-annotated sequences was introduced in [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF]) with a model that used only three edit operations (deletion, insertion and substitution) either on single letters (letters in the sequence with no incident arc) or pairs of letters (letters connected by an arc). In this model, the two letters of an arc are never considered separately, and hence the problem of computing the edit distance between two arc-annotated sequences becomes equivalent (when no pair of arcs are crossing) to the tree edit distance problem, that can be solved in polynomial-time [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF].

To account for other possible RNA structural evolutionary events, new edit operations, such as creation, deletion or modification of arcs between pairs of letters, were introduced in [START_REF] Jiang | A general edit distance between RNA structures[END_REF] at the cost of computational tractability. Indeed, it has been shown in [START_REF] Blin | Extending the hardness of rna secondary structu[END_REF] that in case of non-crossing arcs, the problem of computing the edit distance between two arcannotated sequences under this model is NP-hard. Playing the game of applying constraints either on the legal edit operations or on the allowed alignments, several papers have shed new light on the borderline between tractability and intractability [START_REF] Guignon | An edit distance between rna stem-loops[END_REF][START_REF] Blin | Alignment of RNA structures[END_REF]. Of particular importance, in [START_REF] Guignon | An edit distance between rna stem-loops[END_REF], the authors introduced the notion of conservative edit distance and mapping between two RNA stem-loops in order to design a polynomial-time algorithm for comparing general secondary RNA structures using the full set of biological edit operations introduced in [START_REF] Jiang | A general edit distance between RNA structures[END_REF]. This algorithm is based on a decomposition in stem-loop-like substructures that are pairwised compared and used to compare complete RNA secondary structures. As mentionned in [START_REF] Guignon | An edit distance between rna stem-loops[END_REF], whereas in the very restrictive case of conservative distance and mapping, the computation of the general edit distance is polynomial-time solvable, it is not known if the general, i.e., not conservative, edit distance between two stem-loops can be also computed in polynomial-time.

In this paper, we will show that this strong combinatorial restriction was necessary for the problem to become polynomial since it is NP-hard in the general case. Despite the fact that this result may be considered as purely theoretical, it proves that comparing two RNA structures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.

Preliminaries

Given a finite alphabet Σ, an arc-annotated sequence is formally defined by a pair (S, P ), where S is a string of Σ * and P is a set of arcs connecting pairs of letters of S. In reference to RNA structures, letters are called bases. Bases with no incident arc are called single bases. In an arc-annotated sequence, two arcs (i 1 , j 1 ) and (i 2 , j 2 ) are crossing, if [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF] (see [START_REF] Guignon | An edit distance between rna stem-loops[END_REF] for extensions) introduced five different levels of arc structure: Unlimited -no restriction at all; Crossing -there is no base incident to more than one arc; Nested -there is no base incident to more than one arc and no two arcs are crossing; Stem -there is no base incident to more than one arc and given any two arcs, one is embedded into the other; Plain -there is no arc. There is an obvious inclusion relation between those levels: Plain ⊂ Stem ⊂ Nested ⊂ Crossing ⊂ Unlimited. An arc-annotated sequence (S 1 , P 1 ) is said to occur in another arc-annotated sequence (S 2 , P 2 ) if one can obtain the former from the latter by repeatedly deleting bases (deleting a base that is incident to an arc results in the deletion of the arc).

i 1 < i 2 < j 1 < j 2 or i 2 < i 1 < j 2 < j 1 . An arc (i 1 , j 1 ) is embedded into another arc (i 2 , j 2 ) if i 2 < i 1 < j 1 < j 2 . Evans
Among the many paradigms referring to arcannotated sequences (see [START_REF] Blin | Alignment of RNA structures[END_REF]) for more details) we focus in this article on the Longest Arc-Preserving Common Subsequence (Lapcs for short) [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF][START_REF] Jiang | The longest common subsequence problem for arc-annotated sequences[END_REF], Lin et al. 2002) and the general edit distance (Edit for short) [START_REF] Jiang | A general edit distance between RNA structures[END_REF][START_REF] Blin | Comparing rna structures: towards an intermediate model between the edit and the lapcs problems[END_REF]. Indeed, as shown in [START_REF] Blin | Alignment of RNA structures[END_REF], those two paradigms are quite related since the Lapcs problem is a special case of Edit when considering the complete set of edit operations defined in [START_REF] Jiang | A general edit distance between RNA structures[END_REF]. Therefore, the hardness results for Lapcs stands for Edit.

Formally, the Longest Arc-Preserving Common Subsequence problem is defined as follows: given two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ), find the longest -in terms of sequence length -common arc-annotated subsequence that occurs in both (S 1 , P 1 ) and (S 2 , P 2 ). It has been shown in [START_REF] Jiang | A general edit distance between RNA structures[END_REF] that the Lapcs problem is NP-hard even for Nested structures, i.e., Lapcs(Nested, Nested). Still focussing on Nested structures, Alber et al. [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF]) proved that the Lapcs(Nested, Nested) problem is solvable in O(3 k |Σ| k kn) time, where n is the maximum length of the two sequences and k is the length of the common subsequence searched for. The O(3 k |Σ| k kn) time parameterized algorithm by Alber et al. is by brute-force enumeration: (i) Generate all possible sequences of length k with all possible Nested arc annotations, and (ii) For each of these arc-annotated candidate sequences, check whether or not it occurs as a pattern in both S 1 and S 2 . At the heart of this approach is the fact that it can be decided in O(n k) time whether or not this sequence occurs as an arc-preserving common subsequence [START_REF] Garey | Computers and Intractability: a guide to the theory of NPcompleteness[END_REF]. It is easily see that the above algorithm reduces to O(2 3k-1 km) time for Lapcs(Stem, Stem). Indeed, there exist |Σ| k sequences of length k and hence, for a given sequence of length k, there exist k i different arc-annotations with i arcs. Therefore, there exist ⌊k/2⌋ i=0 k 2i = 2 k-1 arc-annotations of a given sequence of length k.

Here, we focus on the only remaining open problems concerning Lapcs and Edit over stem-loops by showing, with a unique proof, their hardness. More precisely, we prove that Lapcs(Stem, Stem) -which may be considered as a very restricted problem and thus not interesting -is NP-hard in order to infer the NP-hardness of Edit(Stem, Stem) -which is for sure, according to [START_REF] Guignon | An edit distance between rna stem-loops[END_REF], an interesting problem that can be used in a very simple way to compare complete RNA secondary structures. This results also prove that in any future work on comparing RNA structures with a full set of edit operations it will be necessary to introduce strong combinatorial restrictions in order to get an exact polynomial-time algorithm since even with the simpliest model, the general edit distance problem is still NP-complete.

Comparing RNA Stem-Loops is NPcomplete

In this section, we prove that Lapcs over stem-loops (Lapcs(Stem, Stem)) is NP-complete (in Theorem 1); therefore answering an open question of [START_REF] Guignon | An edit distance between rna stem-loops[END_REF]. This last result induces the NP-hardness of Edit over stem-loops.

Theorem 1. Lapcs(Stem, Stem) is NP-complete.

Corollary 1. Comparing RNA structures with a full set of biologically relevant edit operations cannot be done without introducing strong combinatorial restrictions.

In the following, we consider the decision version of the problem which corresponds to deciding if there exists an arc-preserving common subsequence of length greater or equal to a given parameter k ′ .

It is easy to see that the Lapcs problem is in NP. In order to prove its NPhardness, we define a reduction from the NP-complete 3SAT problem [START_REF] Garey | Computers and Intractability: a guide to the theory of NPcompleteness[END_REF] which is defined as follows: Given a collection C q = {c 1 , c 2 , . . . , c q } of q clauses, where each clause consists of a set of 3 literals (representing the disjunction of those literals) over a finite set of n boolean variables V n = {x 1 , x 2 , . . . , x n }, is there an assignment of truth values to each variable of V n s.t. at least one of the literals in each clause is true?

Let (C q , V n ) be any instance of the 3SAT problem s.t. C q = {c 1 , c 2 , . . . , c q } and V n = {x 1 , x 2 , . . . , x n }. For convenience, let L j i denote the j th literal of the i th clause (i.e. c i ) of C q . In the following, given a sequence S over an alphabet Σ, let χ(i, c, S) denote the i th occurrence of the letter c in S.

We build two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ) as follows. An illustration of a full example is given in Figures 1 and2, where n = 4 and q = 3. For readability reasons, the arc-annotated sequences resulting from the construction have been split into several parts and a schematic overview of the overall placement of each part is provided.

Let

S 1 = C 1 q W q C 1 q-1 . . . C 1 2 W 2 C 1 1 W 1 S 1 M V 1 P 1 1 V 2 P 1 2 . . . P 1 q-1 V q P 1 q and S 2 = C 2 q W q C 2 q-1 . . . C 2 2 W 2 C 2 1 W 1 S 2 M V 1 P 2 1 V 2 P 2 2 . . . P 2 q-1 V q P 2 q such that for all 1 ≤ i ≤ q, 1 ≤ k ≤ n, • C 1 i = R 3 i Q i R 2 i Q i X 1 1 X 1 2 . . . X 1 n Q i R 2 i Q i R 1 i with X 1 k = x k s j x k if x k = L j i or x k = L j i ; X 1 k = x k x k otherwise; • P 1 i = Q q+i Q q+i R 3 q+i X 1 n . . . X 1 n 2 +1 R 2 q+i X 1 n 2 . . . X 1 1 R 1 q+i Q q+i Q q+i such that X 1 k = x k x k ; • C 2 i = X 2 1 . . . X 2 n R 3 i Q i X 2 1 . . . X 2 n 2 R 2 i X 2 n 2 +1 . . . X 2 1 Q i R 1 i X 2 1 . . . X 2 n such that for 1 ≤ j ≤ 3, χ(j, X 2 k , C 2 i ) = x k x k s j (resp. s j x k x k ) if x k = L j i (resp. x k = L j i ); χ(j, X 2 k , C 2 i ) = x k x k otherwise; • P 2 i = X 2 n . . . X 2 1 R 1 q+i Q q+i X 2 n . . . X 2 n 2 +1 R 2 q+i X 2 n 2 . . . X 2 1 Q q+i R 3 q+i X 2 n . . . X 2 1 with X 2 k = x k x k . Moreover, let S 1 M = x 1 x 1 x 2 x 2 . . . x n x n and S 2 M = x 1 x 1 x 2 x 2 . . . x n x n .
Notice that, by construction, there is only one occurrence of each {s 1 , s 2 , s 3 } in C 2 i . For all 1 ≤ i ≤ q, let Q i (resp. Q q+i ) be a segment of n + 1 symbols y i (resp. y q+i ). Moreover, for all 1 ≤ i ≤ q, let W i (resp. V i ) be a segment of 20(max{q, n} 2 ) symbols w i (resp. v i ). Let us now define P 1 and P 2 .

For all 1 ≤ i ≤ q -1, (1) add an arc in 1.d and 2.b); (2) add an arc in P 2 between χ(j, x k , C 2 i ) (resp. χ(j, x k , C 2 i )) and χ((4j), x k , P 2 i ) (resp. χ((4j), x k , P 2 i )), ∀1 ≤ k ≤ n (see Figure 1.c, 2.a and 2.c); (3) add an arc in P 2 between χ(1, R j i , C 2 i ) and χ(1, R j q+i , P 2 i ), ∀1 ≤ j ≤ 3 (see Figure 1.c, 2.a and 2.c).

P 1 between χ(1, x k , C 1 i ) (resp. χ(1, x k , C 1 i )) and χ(1, x k , P 1 i+1 ) (resp. χ(1, x k , P 1 i+1 )), ∀1 ≤ k ≤ n (see Figure
Clearly, this construction can be achieved in polynomial-time, and yields to sequences (S 1 , P 1 ) and (S 2 , P 2 ) that are both of type Stem. We now give an intuitive description of the different elements of this construction.

Each clause c i ∈ C q is represented by a pair (C 1 i , C 2 i ) of sequences. The sequence C 2 i is composed of three subsequences representing a selection mechanism of one of the three literals of c i . The pair (S 1 M , S 2 M ) of sequences is a control mechanism that will guarantee that a variable x k cannot be true and false simultaneously. Finally, for each clause c i ∈ C q , the pair (P 1 i , P 2 i ) of sequences is a propagation mechanism which aim is to propagate the selection of the assignment (i.e. true or false) of any literal x k all over C q . Notice that all the previous intuitive notions will be detailed and clarified afterwards.

In the rest of this article, we will refer to any such construction as a snail-construction. In order to complete the instance of the Lapcs(Stem, Stem) problem, we define the parameter k ′ = 40q(max{q, n} 2 ) + 6qn + 8q + n which corresponds to the desired length of the solution. In the following, let (S 1 , P 1 ) and (S 2 , P 2 ) denote the arc-annotated sequences obtained by a snail-construction. We will denote S d the set of symbols deleted in a solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ) (i.e. the symbols that do not belong to the common subsequence).

We start the proof that the reduction from 3SAT to Lapcs(Stem, Stem) is correct by giving some properties about any optimal solution. Lemma 1. In any optimal solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ), at least one symbol incident to any arc would be deleted. Moreover, all the symbols of V i and W i , for 1 ≤ i ≤ q, will not be deleted.

Proof. By contradiction, let us suppose that there exist at least one arc s.t. the two symbols incident to this last are not deleted in a solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ). Then, by construction, it induces that at least one complete sequence V j or W j , for a given 1 ≤ j ≤ q, has been deleted. Since they have the same length, we will consider w.l.o.g. afterwards that V i has been deleted. Therefore, since S 1 is, by construction, smaller than S 2 the length of this optimal solution is at most

|S 1 | -|V j | = q i=1 (|C 1 i | + |P 1 i | + |V i | + |W i |) + |S 1 M | -|V j | = q i=1
((6n + 11) + (6n + 7) + (20(max{q, n} 2 )) + (20(max{q, n} 2 ))) + 2n -(20(max{q, n} 2 )) = q[12n + 18 + 40(max{q, n} 2 )] + 2n -(20(max{q, n} 2 )). Then, in order for this solution to be optimal, one should have q[12n + 18 + 40(max{q, n} 2 )] + 2n -(20(max{q, n} 2 )) ≥ 40q(max{q, n} 2 ) + 6qn + 8q + n. This can be reduced to 6qn + 10q -20(max{q, n} 2 ) + n ≥ 0. But, one can easily check that for any n ≥ 3 (which is always the case in 3SAT instances), this is not true; a contradiction.

Lemma 2. Any optimal solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ) is of length 40q(max{q, n} 2 ) + 6qn + 8q + n.

Proof. By construction, in S 1 there is (1) ∀1 ≤ i ≤ n, 2q + 1 occurrences of x i (resp.

x

i ); (2) ∀1 ≤ i ≤ q, 4 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 q+i , R 3 i , R 1 q+i , R 3 q+i , W i , V i , s 1 , s 2 , s 3 }; (4) ∀1 ≤ i ≤ q, 2 occurrences of R 2 i . Whereas, in S 2 , there is (1) ∀1 ≤ i ≤ n, 6q + 1 occurrences of x i (resp. x i ); (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3 q+i , W i , V i , s 1 , s 2 , s 3 }.
Therefore, in any optimal solution there may be only (1)

∀1 ≤ i ≤ n, 2q + 1 occurrences of x i (resp. x i ); (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3 q+i , W i , V i , s 1 , s 2 , s 3 }.
More precisely, by Lemma 1, and since, by construction, there is an arc in P 2 between χ(1, R j i , C 2 i ) and χ(1, R j q+i , P 2 i ), ∀j ∈ {1, 2, 3}, in any optimal solution, ∀1 ≤ i ≤ q, only half of the

{R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3 q+i } may be conserved. Moreover, any x i (resp. x i ) of S 1 except in C 1
q , is linked by an arc to another x i (resp. x i ), therefore by Lemma 1, in any optimal solution, ∀1 ≤ i ≤ q -1, only half of the occurrences of x i (resp. x i ) may be conserved.

Finally, in any optimal solution, only half of the occurrences of {x i , x i } and one over {s 1 , s 2 , s 3 } in C 1 q and S 1 M may be conserved. Indeed, by construction, if this is not the case in C 1 q (resp. S 1 M ), it implies that at least one complete sequence Q q (resp. V 1 or W 1 ) is totally deleted -which is not optimal since it is of length n + 1 (resp. 20(max{q, n} 2 )).

On the whole, the maximal total length of any solution is thus equal to 40q(max{q, n} 2 )+ 6qn+ 8q + n. Moreover, this solution is composed of (1) ∀1 ≤ i ≤ n, 2q +1 occurrences of either x i or x i , (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i and Q q+i , (3) ∀1 ≤ i ≤ q, 1 occurrence of each {W i , V i } and either s 1 , s 2 or s 3 and (4)

∀1 ≤ i ≤ q, R j1 i , R j2 i , R j3 q+i s.t. {j 1 , j 2 , j 3 } = {1, 2, 3}.
Lemma 3. In any optimal solution of Lapcs problem on (S 1 , P 1 ) and

(S 2 , P 2 ), if χ(1, x k , S 1 M ) (resp. χ(1, x k , S 1 M )) for a given 1 ≤ k ≤ n is deleted then, ∀1 ≤ j ≤ q, χ(1, x k , C 1 j ) (resp. χ(1, x k , C 1 j )) is deleted. Proof. By construction, ∀1 ≤ k ≤ n only one of {x k , x k } may be conserved between S 1 M and S 2 M since χ(1, x k , S 1 M ) < χ(1, x k , S 1 M ) whereas χ(1, x k , S 2 M ) < χ(1, x k , S 2
M ). By Lemma 1, at least one symbol incident to any arc is deleted. Therefore, ∀1 ≤ k ≤ n only one of {x k , x k } may be conserved between C 1 1 and C 2 1 . Let us suppose that for a given 1 ≤ k ≤ n, χ(1, x k , S 1 M ) is deleted. According to the proof of Lemma 2, in any optimal solution, ∀1 ≤ k ≤ n exactly be deleted and, according to the proof of Lemma 2, χ(3, x k , C 2 1 ) has to be conserved. Therefore, in the three cases, if for a given 1

≤ k ≤ n, χ(1, x k , S 1 M ) is conserved then so does χ(1, x k , C 1 1 ). It is easy to see that, by a similar reasoning, if for a given 1 ≤ k ≤ n, χ(1, x k , S 1 M ) is conserved then so does χ(1, x k , C 1 1
). With a similar reasoning, by reccurence, since,

∀1 ≤ i ≤ q, 1 ≤ k ≤ n, there is an arc in P 1 between χ(1, x k , C 1 i ) (resp. χ(1, x k , C 1 i )) and χ(1, x k , P 1 i+1 ) (resp. χ(1, x k , P 1 i+1 )), if χ(1, x k , C 1 i ) is conserved then χ(1, x k , P 1 i+1 ) is deleted. And therefore, with similar arguments, χ(1, x k , C 1 i+1 ) is conserved. Once more, it is easy to see that this result still holds if χ(1, x k , C 1 i ) is conserved.
Theorem 2. Given an instance of the problem 3SAT with n variables and q clauses, there exists a satisfying truth assignment iff the Lapcs of (S 1 , P 1 ) and (S 2 , P 2 ) is of length k ′ = 40q(max{q, n} 2 ) + 6qn + 8q + n.

Proof. (⇒) An optimal solution for C q = (x 1 ∨ x 2 ∨ x 3 )∧(x 1 ∨x 2 ∨x 4 )∧(x 2 ∨x 3 ∨x 4 ) -i.e. x 1 = x 3 = true and x 2 = x 4 = f alse -is illustrated in Figures 1 and2 where any symbol over a grey background have to be deleted. Suppose we have a solution of 3SAT, that is an assignment of each variable of V n satisfying C q . Let us first list all the symbols to delete in S 1 .

For all 1 ≤ k ≤ n, if x k = f alse then delete, ∀1 ≤ j ≤ q, {χ(1, x k , C 1 j ), χ(1, x k , P 1 j )} and χ(1, x k , S 1 M ); otherwise delete, ∀1 ≤ j ≤ q, {χ(1, x k , C 1 j ), χ(1, x k , P 1 j )} and χ(1, x k , S 1 M ). For each L j i satisfying c i with the biggest index j with 1 2.c); By construction, the natural order of the symbols of S 1 and S 2 allows the corresponding set of undeleted symbols to be conserved in a common arc-preserving common subsequence between (S 1 , P 1 ) and (S 2 , P 2 ). Let us now prove that the length of this last is k ′ . One can easily check that this solution is composed of ∀1 ≤ k ≤ n, (1) 2q + 1 occurrences of either x k or x k , (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i and Q q+i , (3) ∀1 ≤ i ≤ q, 1 occurrence of each {W i , V i } and either s 1 , s 2 or s 3 and (4) ∀1 ≤ i ≤ q, R j1 i , R j2 i , R j3 q+i s.t. {j 1 , j 2 , j 3 } = {1, 2, 3}. Thus, the length of the solution is 40q(max{q, n} 2 ) + 6qn + 8q + n.

≤ i ≤ q, if (1) j = 1 then delete {χ(1, R 3 i , C 1 i ), χ(1, Q i , C 1 i ), χ(1, R 2 i , C 1 i ), χ(2, Q i , C 1 i ), χ(1, s 2 , C 1 i ), χ(1, s 3 , C 1 i ), χ(1, R 2 q+i , P 1 i ), χ(1, R 1 q+i , P 1 i ), χ(3, Q q+i , P 1 i ), χ(4, Q q+i , P 1 i )} (cf Figure 1.a); if (2) j = 2 then delete {χ(1, R 2 i , C 1 i ), χ(2, Q i , C 1 i ), χ(1, s 1 , C 1 i ), χ(1, s 3 , C 1 i ), χ(3, Q i , C 1 i ), χ(2, R 2 i , C 1 i ), χ(2, Q q+i , P 1 i ), χ(1, R 3 q+i , P 1 i ), χ(1, R 1 q+i , P 1 i ), χ(3, Q q+i , P 1 i )} (cf Figure 2.a); if (3) j = 3 then delete {χ(1, s 1 , C 1 i ), χ(1, s 2 , C 1 i ), χ(3, Q i , C 1 i ), χ(2, R 2 i , C 1 i ), χ(4, Q i , C 1 i ), χ(1, R 1 i , C 1 i ), χ(1, Q q+i , P 1 i ), χ(2, Q q+i , P 1 i ), χ(1, R 3 q+i , P 1 i ), χ(1, R 2 q+i , P 1 i )} (cf Figure 2.c); Let us now list all the symbols in S 2 to be deleted. For all 1 ≤ k ≤ n, if x k = f alse then delete χ(1, x k , S 2 M ); otherwise delete χ(1, x k , S 2 M ). For each L j i satisfying c i with the biggest index j with 1 ≤ i ≤ q, if (1) j = 1 then delete ∀1 ≤ k ≤ n {χ(1, R 3 i , C 2 i ), χ(1, s 2 , C 2 i ), χ(2, x k , C 2 i ), χ(2, x k , C 2 i ), χ(1, s 3 , C 2 i ), χ(3, x k , C 2 i ), χ(3, x k , C 2 i ), χ(1, x k , P 2 i ), χ(1, x k , P 2 i ), χ(1, R 1 q+i , P 2 i ), χ(1, R 2 q+i , P 2 i ), χ(2, x k , P 2 i ), χ(2, x k , P 2 i )}. Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, {χ(1, x k , C 2 i ), χ(3, x k , P 2 i )}; otherwise delete {χ(1, x k , C 2 i ), χ(3, x k , P 2 i )} (cf Figure 1.a); if (2) j = 2 then delete ∀1 ≤ k ≤ n {χ(1, R 2 i , C 2 i ), χ(1, s 1 , C 2 i ), χ(1, x k , C 2 i ), χ(1, x k , C 2 i ), χ(1, s 3 , C 2 i ), χ(3, x k , C 2 i ), χ(3, x k , C 2 i ), χ(1, x k , P 2 i ), χ(1, x k , P 2 i ), χ(1, R 1 q+i , P 2 i ), χ(1, R 3 q+i , P 2 i ), χ(3, x k , P 2 i ), χ(3, x k , P 2 i )}. Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, {χ(2, x k , C 2 i ), χ(2, x k , P 2 i )}; otherwise delete {χ(2, x k , C 2 i ), χ(2, x k , P 2 i )} (cf Figure 2.a); if (3) j = 3 then delete ∀1 ≤ k ≤ n {χ(1, R 1 i , C 2 i ), χ(1, s 1 , C 2 i ), χ(1, x k , C 2 i ), χ(1, x k , C 2 i ), χ(1, s 2 , C 2 i ), χ(2, x k , C 2 i ), χ(2, x k , C 2 i ), χ(2, x k , P 2 i ), χ(2, x k , P 2 i ), χ(1, R 2 q+i , P 2 i ), χ(1, R 3 q+i , P 2 i ), χ(3, x k , P 2 i ), χ(3, x k , P 2 i )}. Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, {χ(3, x k , C 2 i ), χ(1, x k , P 2 i )}; otherwise delete {χ(3, x k , C 2 i ), χ(1, x k , P 2 i )} (cf Figure
(⇐) Suppose we have an optimal solution -i.e. a set of symbols S d to delete -for Lapcs of (S 1 , P 1 ) and (S 2 , P 2 ). Let us define the truth assignment of V n s.t., ∀1 ≤ i ≤ q, if χ(1, s j , C 1 i ) ∈ S d then L j i is true. Let us prove that it is a solution of 3SAT.

By construction, if L j i = x k (resp. x k ) then in C 1 i , s j appears between x k and x k whereas in C 2 j it appears after x k (resp. before x k ). Thus, if χ(1, s j , C 1 i ) is not deleted then x k (resp. x k ) in C 1 i is deleted if L j i = x k (resp. x k ). Consequently, according to the proof of Lemma 3, if χ(1, s j , C 1 i ) is not deleted then x k (resp. x k ) in all C 1 i ′ , with 1 ≤ i ′ ≤ q is deleted if L j i = x k (resp. x k ). Therefore, we can ensure that one cannot obtain L j i and L j ′ i ′ being true whereas L j i = L j ′ i ′ (that is a variable cannot be simultaneously true and false). By Lemma 2, we can ensure that for any 1 ≤ i ≤ q exactly one of {s 1 , s 2 , s 3 } is conserved in C 1 i . Therefore, for any clause c i at least one of its literal is set to true. This ensures that our solution is a solution of 3SAT.

Future work

From a computational biology point of view, especially for comparing stems, one may, however, be mostly interested in the case k (length of the common subsequence searched) might not be assumed to small compared to n. A first approach is provided in [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] where it is proved that, given two sequences of length at most n and nested arc structure, an arc-preserving common subsequence can be determined (if it exists) in O(3.31 k1+k2 n) time; obtained by deleting (together with corresponding arcs) k 1 letters from the first and k 2 letters from the second sequence. Improving the running time of the parameterization in case of stem arc structures appears to be a promising line of research.

Figure 1: Considering C q = (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 2 ∨ x 4 ) ∧ (x 2 ∨ x 3 ∨ x 4 ). For readability, all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) A schematic view of the overall arrangement of the components of the two a.a. sequences. b) Description of S 1 M , S 2 M , P 1 1 , P 2 1 and the corresponding arcs in

For readability all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) Description of C 1 2 , C 2 2 , P 1 2 , P 2 2 and the corresponding arcs in P 2 . c) Description of C 1 2 , C 2 2 , P 1 3 , P 2 3 and the corresponding arcs in P 1 . d) Description of C 1 3 , C 2 3 , P 1 3 , P 2 3 and the corresponding arcs in P 2 .

one of {x k , x k } has to be deleted. Then χ(1, x k , P 1 1 ) is deleted whereas χ(1, x k , P 1 1 ) is conserved. By construction, in P 2 1 , since according to the proof of Lemma 2, both occurrences of

Then one can check that the only solution is to conserve χ(2, R 2 1 , C 1 1 ) since otherwise at least half of the x k 's would not be conserved. Consequently, the only solution is to conserve, ∀1 ≤ k ≤ n, the first (resp. last) occurrence of any x k or x k in C 2 1 (resp. P 2 1 ) -i.e. the occurrences appearing before χ(1, Q 1 , C 2 1 ) (resp. after χ(2, Q q+1 , P 2 1 )). Since by construction, there is an arc between χ(1, x k , C 2 1 ) (resp. χ(1, x k , C 2 1 )) and χ(3, x k , P 2 1 ) (resp. χ(3, x k , P 2 1 )), in order for χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(3, x k , P 2 1 ). Thus, by Lemma 1, χ(1, x k , C 2 1 ) has to be deleted and, according to the proof of Lemma 2, χ(1, x k , C 2 1 ) has to be conserved.

Let us now consider that {R 1 1 , R 3 1 , R 2 q+1 } are conserved. By a similar reasoning, one can check that the only solution is to conserve, ∀1 ≤ k ≤ n, the second occurrence of any x k or x k in C 2 1 (resp. P 2 1 ) -i.e. the occurrences appearing between

). Since by construction, there is an arc between χ(2, x k , C 2 1 ) (resp. χ(2, x k , C 2 1 )) and χ(2, x k , P 2 1 ) (resp. χ(2, x k , P 2 1 )), in order to χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(2, x k , P 2 1 ). Thus, by Lemma 1, χ(2, x k , C 2 1 ) has to be deleted and, according to the proof of Lemma 2, χ(2, x k , C 2 1 ) has to be conserved. Finally, let us consider that {R 2 1 , R 3 1 , R 1 q+1 } are conserved. Once again, by a similar reasoning, one can check that the only solution is to conserve χ(1, R 2 1 , C 1 1 ) since otherwise at least half of the x k 's would not be conserved. Consequently, the only solution is to conserve, ∀1 ≤ k ≤ n, the last (resp. first) occurrence of any x k or x k in C 2 1 (resp. P 2 1 ) -i.e. the occurrences appearing after χ(2, Q 1 , C 2 1 ) (resp. before χ(1, Q q+1 , P 2 1 )). Since by construction, there is an arc between χ(3, x k , C 2 1 ) (resp. χ(3, x k , C 2 1 )) and χ(1, x k , P 2 1 ) (resp. χ(1, x k , P 2 1 )), in order to χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(1, x k , P 2 1 ). Thus, by Lemma 1, χ(3, x k , C 2 1 ) has to