Louis Dagneaux
email: louisdagneaux@gmail.com

Hamid Rahmatullah Bin

Abd Razak

Pierre Laumonerie

Ahmad Faizhan

Sally Liarno

Peter Wellings

Matthieu Ollivier

Christophe Jacquet

Bony asymmetry in patellofemoral morphology and risk factors of instability are mostly clinically negligible

Keywords: Side-to-side differences, Asymmetry, Femoral trochlea, Patellar height, CT-scan

Purpose Previous investigations suggested that femoral side-to-side differences were located in the upper femur anatomy. However, little is known about the asymmetry between distal femur and patella. The degree of bony asymmetry in the patellofemoral joint was evaluated using pairs of CT-scans with emphasis on morphometric measurements and risk factors relevant to patellofemoral disorders. Methods Patellofemoral morphometric parameters and anatomical risk factors were analyzed from 345 pairs of CT scans to evaluate side-to-side differences for each patient. All measurements were automatized using previously published algorithmcalculated bone landmarks. We analyzed asymmetry based on absolute differences (AD) and percentage asymmetry (AS%). Significant asymmetry was defined as AS% > 10%.

Results Patellar height was found to be highly symmetric (mean AD 0.1 for both Insall-Salvatti and Caton-Deschamps methods, AS% 8% and 9%, respectively). Patellar and femoral morphometric parameters were found highly symmetric, except for the trochlear groove depth. Substantial asymmetry was reported in two patellofemoral risk factors: the lateral trochlear inclination (mean AD 2°, AS% 16%) and the tibial tuberosity-trochlear groove distance (1 mm, 116%). Patellar and femoral morphometric asymmetries were independent of demographics, including age, gender, height, weight and ethnicity. Conclusion Patellar height was found to be highly symmetric and is, therefore, a reasonable index for contralateral templating. While very few patellofemoral morphometric parameters and anatomical risk factors were asymmetric, the mean differences were clinically negligible and independent of demographics. Level of evidence III.

Introduction

Studies evaluating bone anatomy and morphometry have focused more on inter-individual differences rather than intra-individual side-to-side differences [START_REF] Dargel | Side differences in the anatomy of human knee joints[END_REF]. An understanding of side-to-side differences is useful in the evaluation of bilateral musculoskeletal pathology. For example, differences in bone morphology and functional parameters between the knees of a patient may influence leg dominance which in turn may affect the risk of joint injury or degeneration [START_REF] Benítez-Martínez | Lower limb dominance, morphology, and sonographic abnormalities of the patellar tendon in elite basketball players: a crosssectional study[END_REF]. There are studies that have reported substantial asymmetry and side-to-side differences in the proximal and distal femur [START_REF] Ollivier | Anatomy of the proximal femur at the time of total hip arthroplasty is a matter of morphotype and etiology but not gender[END_REF][START_REF] Young | Are the left and right proximal femurs symmetric?[END_REF]. However, the literature is lacking with respect to side-to-side differences in the morphology of the femoral trochlea and patella.

The patellofemoral joint (PFJ), owing to its unique bone anatomy and the numerous capsuloligamentous structures and muscles that dynamically control the patella, is one of the most complex joints in the human body [START_REF] Zaffagnini | Patellofemoral anatomy and biomechanics: current concepts[END_REF]. Patellofemoral disorders are commonly described bilaterally in individuals. However, the effect of side-to-side differences in bone anatomy and morphology on the risk of patellofemoral disorders has yet to be elucidated. Some of these parameters include trochlear morphology, patellar tilt and patellar height [START_REF] Crema | Magnetic resonance imaging-based morphological and alignment assessment of the patellofemoral joint and its relationship to proximal patellar tendinopathy[END_REF]. To date, there has only been a single study that has reported side-to-side differences in the human knee joint [START_REF] Dargel | Side differences in the anatomy of human knee joints[END_REF]. However, patellofemoral parameters were not analyzed in that study. Despite the challenges researches face in analyzing the PFJ, data from modern computed tomography (CT) scans can be harnessed to reveal significant asymmetries [START_REF] Laumonerie | Which factors influence proximal femoral asymmetry?: A 3D CT analysis of 345 femoral pairs[END_REF][START_REF] Pangaud | Measurement of the posterior tibial slope depends on ethnicity, sex, and lower limb alignment: a computed tomography analysis of 378 healthy participants[END_REF]. The natural question that the surgeon may have is "Is contralateral screening or templating of the PFJ appropriate in regards to these asymmetries?" Indeed, the contralateral knee is often used as reference in extensor mechanism reconstruction. In addition, to quantify asymmetries in the PFJ is crucial for the understanding of patellar and trochlear development. Substantial differences would help supporting the developmental versus genetic theory for trochlear and patellar shapes.

As such, the degree of bony asymmetry in PFJ was evaluated using pairs of CT-scans with emphasis on morphometric measurements and risk factors relevant to patellofemoral disorders. We hypothesized that substantial asymmetry would be present in association with demographic factors.

Materials and methods

After IRB approval (IRB 2019-015333-13, Aix-Marseille University, France), paired CT scans of the lower limbs from 389 individuals taken from the Stryker Orthopedic Modeling and Analytics (SOMA) database (Stryker, Mahwah, New Jersey, USA) were specifically analyzed for this investigation. SOMA is a database containing over 3500 CT scans which have been segmented to provide three-dimensional models of more than 15,000 individual bones. This outstanding dataset has already been utilized to study morphometric characteristics of the proximal femur and tibia [START_REF] Laumonerie | Which factors influence proximal femoral asymmetry?: A 3D CT analysis of 345 femoral pairs[END_REF][START_REF] Pangaud | Measurement of the posterior tibial slope depends on ethnicity, sex, and lower limb alignment: a computed tomography analysis of 378 healthy participants[END_REF]. While the scans themselves are anonymized, patient data such as age, gender, height, weight, body mass index (BMI) and ethnicity were known for each scan. These scans were collected from several institutions globally and were included only if each slice was less than 1.5 mm thick with no motion artefact present.

Only patients with no clinical signs or symptoms in the knee were investigated. All participants underwent CT scans in the supine position, the knee in the fully extended with free natural rotation and complete extensor relaxation. Scans were excluded if they showed any bone and joint anomalies such as significant arthritis, posttraumatic bony deformities or any evidence of previous surgery to investigate the constitutional morphology of the patellofemoral joint from this subset of individuals. Of the 389 paired CT scans (778 knees, left and right measurements pooled together), 198 were from men (51%) and 191 were from women. The mean age of included patients was 58 ± 16 years, and the mean BMI was 25 ± 4 kg/m 2 . Demographic and functional parameters in the series can be seen in Table 1. The patients in our series had a diverse ethnicity including Caucasian (54%), Asian (39%), African-American and Middle Eastern (7%).

PFJ measurements

Anatomical measurements included patellar morphometric parameters, femoral trochlear morphometric parameters and PF anatomical risk factors usually considered of primary importance for the PFJ [START_REF] Bull | Standardisation of the description of patellofemoral motion and comparison between different techniques[END_REF][START_REF] Katchburian | Measurement of patellar tracking: assessment and analysis of the literature[END_REF]. All these measures were assessed for each pair of CT scans (Fig. 1). Automatized landmarks were used to assess bone metrics (width and thickness) and articular angulation in an index bone using algorithm-calculated technology. Then, these measurements were mapped to each bone of the database by a previously validated software (Soma TM, Stryker, Mahwah, US), resulting in reproducible patient-specific bony landmarks extraction. The most proximal and distal points of the patella were selected to define the patellar width, the most anterior and posterior point of the patella defining the patellar thickness (Fig. 1). The same method was used for the medial and lateral facets of the patella, the medial and lateral femoral condyle and the femoral trochlea, resulting in the extraction of bony width, thickness, height and length. The intraclass correlation coefficient was found > 0.99 after two independent software extractions.

The trochlear length ratio was defined as the ratio between the lateral facet and medial facet of the trochlea. The trochlear groove thickness ratio was defined as the ratio between the trochlear groove thickness (Line 1 is drawn across the posterior margins of the medial and lateral condyles. Two lines parallel to line 1 are drawn crossing the centers of the trochlear groove and the posterior femoral condylar groove, respectively. Trochlear groove thickness is the perpendicular distance between these 2 lines) and the central condylar height (line 1 is drawn across the posterior margins of the medial and lateral condyles. The central condylar height is the perpendicular distance from line 1 to the deepest part of the trochlear groove). The epicondylar width ratio was defined using the lateral or medial condylar height expressed as a percentage of the transepicondylar width. Patellar height was assessed using the Caton-Deschamps index [START_REF] Caton | Patella infera. Apropos of 128 cases[END_REF] and Insall-Salvati ratio [START_REF] Grelsamer | The modified Insall-Salvati ratio for assessment of patellar height[END_REF]. Anatomical risk factors were conventional measurements associated with patellofemoral pathology, including the alignment of the extensor mechanism (defined by the tibial tuberosity-trochlear groove (TT-TG) distance) [START_REF] Dejour | Factors of patellar instability: an anatomic radiographic study[END_REF], the patella articular angle (defined as the angulation between the two patellar facets, AFAP) [START_REF] Iranpour | Femoral articular geometry and patellofemoral stability[END_REF], the sulcus angle (defined as the angulation between the two trochlear facets, SA) [START_REF] Iriuchishima | The correlation between femoral sulcus morphology and osteoarthritic changes in the patello-femoral joint[END_REF] and the lateral trochlear inclination (defined as the angulation between the trochlear lateral facet and the femoral posterior condyles, LCI) [START_REF] Fucentese | CT changes after trochleoplasty for symptomatic trochlear dysplasia[END_REF]. Algorithmbased mesh-morphing and measurements from CT scans of human femurs have been reported to be greatly accurate [START_REF] Grassi | Evaluation of the generality and accuracy of a new mesh morphing procedure for the human femur[END_REF], and in-house accuracy and reproducibility analysis estimated that algorithms from CT scans allows automated bony measurements for the patella with the same margin of error < 2 mm and < 1°.

Assessment of asymmetry

Side-to-side absolute differences (AD) were calculated simply by subtracting right and left values for each individual and expressed by mean and range in the entire cohort (Tables 2 and3). As such, the maximum of individual AD reflected the magnitude of asymmetry.

The percentage of absolute asymmetry (AS%) was determined for each individual as the absolute difference divided by (the mean of the right and left values), and expressed by the mean of AS% in the entire cohort [START_REF] Young | Are the left and right proximal femurs symmetric?[END_REF]. As such, this value reflected the significance of asymmetry and we defined a percentage of > 10% as significant.

Statistical analysis

Mean and standard deviations (SD) were determined for each of the measurements made for the population as a whole and for various subgroups, based on gender and Fig. 1 CT scan measurements of the patellofemoral joint from axial and sagittal segmentations using automatized software ethnicity. Normal (Gaussian) distributions of the absolute and percentage asymmetry between pairs of PFJ parameters were determined. Univariate analysis was performed using Student's paired t tests to compare sideto-side mean values as well as Student's t test to compare smaller versus larger mean values. Pearson's coefficients were calculated to examine correlations among absolute differences, specimen demographic data and PFJ measurements. Multiple linear regression models were developed to establish the determinants for each of the variables that defined a difference between left and right measurements. For each model, variables with a p value < 0.1 in the univariate analysis were kept in the final model. A trained statistician (MO) performed all the statistical analyses using SPSS (Version 22; IBM Corp, Armonk, New York, USA). All calculations assumed two-tailed tests. Results were considered statistically significant at p value < 0.05. Sample size was calculated based on the estimated patellar inclination angle difference with a α of 0.05, and power (1-β) of 0.80. Using G*power, a minimum of 81 paired CT scans was calculated to detect 10% asymmetry [START_REF] Faul | Statistical power analyses using G*Power 3.1: tests for correlation and regression analyses[END_REF].

Results

Side-to-side differences in morphological parameters, percentages of asymmetry and absolute differences are summarized in Table 2. Patellar morphometric measurements including patellar width, patellar facet width and patellar thickness were found to have side-to-side differences under the 10% threshold (i.e. non-significant). As such, patellar asymmetries were found negligible. Femoral morphometric measurements were highly symmetric, including the width of the trochlear facets, transepicondylar width, condylar heights and ratio (Table 2). The only significant asymmetry was found in the trochlear groove depth (TGD, mean AD 1 mm, AS% 39%) with a maximum asymmetry of 4 mm. Patellar height was highly symmetric from one patient to another with a mean AD of 0.1 mm for both Insall-Salvatti and Caton-Deschamps methods (AS% 8% and 9%, respectively). We found significant side-to-side differences in two patellofemoral anatomical risk factors (Table 3): lateral trochlear inclination (LTI, mean AD 2°, AS% 16%) and TTTG distance (mean AD 1 mm, AS% 116%). The maximum asymmetry for LTI and TTGT were 10° and 3 mm, respectively.

While significantly asymmetric, mean absolute differences showed in this study were not clinically relevant the trochlear groove depth (mean absolute difference of 1 mm), LTI (2°) TT-GT (1 mm). The few asymmetries that we found above was independent of demographic factors, including age, gender, BMI and ethnicity (Table 4).

Discussion

The most important finding of the present study was very few patellofemoral morphometric parameters and anatomical risk factors were asymmetric. To our knowledge, this is the first study reporting side-to-side differences and asymmetry of the PFJ. Reconstruction of the extensor apparatus often required contralateral planning of the patella height or morphology, including quadriceps and patellar tendon reconstruction or sizing for allograft in chronic failure. Our main result suggests that templating patellar morphology from the contralateral side is a good option in cases that require patellar reconstruction, allograft sizing and patellar implantation [START_REF] Jacquet | Contralateral preoperative templating of lower limbs' mechanical angles is a reasonable option[END_REF]. Similarly, templating patellar height from the contralateral side can be a valuable target for the reconstruction of the extensor mechanism.

The main asymmetry in the femoral morphometric parameters was found in the trochlear groove depth (TGD, AS% 39%) with a maximum of 4 mm. This parameter is directly related to trochlear dysplasia and patellar maltracking [START_REF] Pfirrmann | Femoral trochlear dysplasia: MR findings[END_REF]. Previously reported side-to-side differences in the femur include neck-shaft angle, femoral offset, femoral neck version, femoral neck thickness, femoral shaft dimension, femoral canal flare index and coronal alignment of the distal femur [START_REF] Dargel | Side differences in the anatomy of human knee joints[END_REF][START_REF] Young | Are the left and right proximal femurs symmetric?[END_REF]. In our study, asymmetry in the distal femur was limited to the femoral trochlea, as the patella morphometric parameters were found highly symmetric.

Besides the asymmetry of the trochlear groove depth, we also found asymmetry in the lateral trochlear inclination (LTI, AS% 16%) with a maximum of 10°. While no asymmetry of the femoral condyle dimensions was found in this investigation, lateral trochlear inclination has been found to correlate with femoral neck anteversion angle, neck-shaft angle and mediolateral offset of the proximal femur [START_REF] Wright | Strong correlation between the morphology of the proximal femur and the geometry of the distal femoral trochlea[END_REF]. In light of known asymmetry of the proximal femur and the correlation between the morphology of the proximal femur and the trochlea, asymmetry of trochlear parameters was expected using modern measurement methods.

The clinical significance of these asymmetries is debatable although abnormalities in trochlear inclination, depth and orientation have been known to induce patellofemoral disorders [START_REF] Prakash | Comparison of radiological parameters between normal and patellar dislocation groups in Korean population: a rotational profile CTbased study[END_REF]. Mehl et al. reported that cartilage defects of the patella are associated with the geometry of the PFJ especially with flat and shallow trochlea [START_REF] Mehl | Association between patellar cartilage defects and patellofemoral geometry: a matched-pair MRI comparison of patients with and without isolated patellar cartilage defects[END_REF]. However, they did not perform side-to-side comparisons in their study. Deep femoral sulcus depth and increased sulcus angle have been found to correlate with the incidence of PFJ osteoarthritis [START_REF] Davies-Tuck | Femoral sulcus angle and increased patella facet cartilage volume in an osteoarthritic population[END_REF][START_REF] Iriuchishima | The correlation between femoral sulcus morphology and osteoarthritic changes in the patello-femoral joint[END_REF]. Moreover, we know that for every 1º increase in the femoral sulcus angle, there is an associated 9.1 mm 3 (95% CI 3.1-15.0) increase in medial patella cartilage volume [START_REF] Davies-Tuck | Femoral sulcus angle and increased patella facet cartilage volume in an osteoarthritic population[END_REF]. However, the asymmetries found in our cannot be strongly related to factors of early PF degeneration found by others [START_REF] Grelsamer | The pathophysiology of patellofemoral arthritis[END_REF] in regards to the small absolute differences.

In evaluating patellofemoral risk factors, we found sideto-side differences in LTI and TTTG distance. This asymmetries could explain side-dominance in the occurrence of patellofemoral pain syndrome, patellar instability and recurrent dislocation [START_REF] Demehri | Imaging characteristics of contralateral asymptomatic patellofemoral joints in patients with unilateral instability[END_REF]. As a strong predictor of patellofemoral tracking disorders, LTI correlated strongly with lateral tilt and bisect offset index with an adjusted R 2 of 0.70 and 0.46, respectively, in a study by Biyani et al. [START_REF] Biyani | Anatomical factors influencing patellar tracking in the unstable patellofemoral joint[END_REF] and was the best predictor of patellar lateral displacement and tilt at 20º, 40º and 60º of knee flexion [START_REF] Teng | Predictors of patellar alignment during weight bearing: an examination of patellar height and trochlear geometry[END_REF]. Interestingly, lateral tilt and bisect offset index are linked to other relevant parameters for the PFJ (lateral patellar displacement, patellar inclination angle and trochlear congruence angle). However, the methodology used in our study was not published to quantify asymmetries in functional measures (i.e. not anatomical).

Demographics (including age, gender, height, weight, and ethnicity) were not related to patellofemoral asymmetries from the multivariate analyses. In contrast, it has been reported that a higher risk of developing patellofemoral pain syndrome [START_REF] Huntington | Factors associated with an increased risk of recurrence after a first-time patellar dislocation: a systematic review and meta-analysis[END_REF] and patellar instability [START_REF] Boling | Gender differences in the incidence and prevalence of patellofemoral pain syndrome[END_REF][START_REF] Lewallen | First-time patellofemoral dislocation: risk factors for recurrent instability[END_REF] were found with females. This predisposition cannot be related to asymmetries found in our study, although some authors have postulated that females may have risk factors associated with asymmetry, predisposing them to patellofemoral disorders [START_REF] Lacey | Gender difference in symptomatic radiographic knee osteoarthritis in the Knee Clinical Assessment-CAS(K): a prospective study in the general population[END_REF][START_REF] Mahfouz | Patella sex determination by 3D statistical shape models and nonlinear classifiers[END_REF][START_REF] Teng | Predictors of patellar alignment during weight bearing: an examination of patellar height and trochlear geometry[END_REF].

This study does have its limitations. First, measurements of the proximal femur were not considered. The automatized measurements focused on patellofemoral landmarks with no integration of rotational abnormalities of the femur and at the ankle [START_REF] Ollivier | Anatomy of the proximal femur at the time of total hip arthroplasty is a matter of morphotype and etiology but not gender[END_REF][START_REF] Young | Are the left and right proximal femurs symmetric?[END_REF]. Next, CT-scans were utilized to investigate bony morphology in determining joint orientation, neglecting the geometry of articular cartilage. Finally, in assessing absolute side-to-side differences for individual patients, the number of paired femurs required to assess significant changes can range from 3 to 165 pairs depending on the desired effect size or sensitivity, as reported by Pierre et al. [START_REF] Pierre | Assessment of the bilateral asymmetry of human femurs based on physical, densitometric, and structural rigidity characteristics[END_REF]. A small risk of overestimation of the effect size needs to be acknowledged in regards to the high number of CT-scans included.

In regards to the magnitude of asymmetries located in the patellofemoral joint, we highlight the need for careful contralateral screening as these asymmetrical risk factors involve the occurrence of recurrent dislocations or contribute to adverse outcomes. These findings help to understand the underlying reasons for asymmetry in patellar positions, patellofemoral symptoms and adverse results. Potential sideto-side differences outcomes after isolated medial patellofemoral ligament reconstruction should be noted in the patient's information. The label of "healthy" contralateral knee should be considered with caution when addressing recurrent patellofemoral instability or patellofemoral pain syndrome.

Conclusions

Patellar height was found to be highly symmetric and is, therefore, a reasonable index for contralateral templating. While very few patellofemoral morphometric parameters and anatomical risk factors were asymmetric, the mean differences were clinically negligible and independent of demographics.

Table 1

 1 Demographic parameters in the overall series (left and right anatomical measurements are pooled together)

	Parameters	% or Mean ± SD (range)
	Demographic
	Age, years	58 ± 16 (11-92)
	Gender (female)	49%
	Height, kg	166 ± 8 (140-189)
	Weight, cm	70 ± 15 (39-110)
	Body mass index, kg/m 2	25 ± 4 (15.6-41.6)
	Ethnic background
	Caucasian	54% (211 individuals)
	Asian	39% (151)
	African American and middle eastern	7% (27)

Table 2

 2 Side to side differences in morphological parameters of the patellofemoral joint with percentage of asymmetry and absolute difference p values indicated with an absolute difference were calculated using Student's t test, upon smaller versus larger global means comparison. Substantially asymmetry is defined as a side-to-side difference %AS > 10% SD standard deviation, %AS percentage of asymmetry, AD absolute difference, n.s. non-significant

	Right side	Left side	AS% AD	p
	Mean (SD) Range	Mean (SD) Range	Mean (range)

Table 3

 3 Side to side differences in patellofemoral anatomical risk factors with the percentage of asymmetry and absolute difference p values indicated with an absolute difference were calculated using Student's t test, upon smaller versus larger global means comparison. Substantially asymmetry is defined as a side-to-side difference AS% > 10%

			Right side		Left side		AS%	AD	p
			Mean (SD) Range	Mean (SD) Range		Mean (range)
	Tibial tuberosity-trochlear	TTTG (mm)	11.3 (1)	0-16.7	11.3 (1)	0-15.3	116% 0.6 (0-3)	< 0.00001
	groove distance
	Insall-Salvati ratio	IS	1.2 (0.4)	0.7-5.4	1.2 (0.4)	0.8-6.8	8.6%	0.1 (0-1)	0.0004
	Caton-Deschamps index	CD	1 (0.4)	0.6-6.1	1 (0.5)	0.7-7.2	8%	0.1 (0-1)	0.013
	Patella articular angle	AFAP,	115.8 (8.3)	83.9-137.8 114.8 (8.6)	82.9-155.7 4.4%	4.8 (0-44)	< 0.00001
	Sulcus angle	SA, °155.2 (8.7) 126.7-179.3 155.5 (9.1) 131.8-179.3 2.6%	3.9 (0-17)	< 0.00001
	Lateral trochlear inclination LTI, °15.6 (4.2)	0-26.1	15.8 (4.3)	1.3-25.9	16%	1.9 (0-10)	< 0.00001
	SD standard deviation, %AS percentage of asymmetry, AD absolute difference
	°degrees

Table 4

 4 Multivariate analysis regarding asymmetrical factorsAll p values calculated using multiple analysis of variance testing (MANOVA) TGD trochlear groove depth, TTTG tibial tuberosity-trochlear groove distance, LCI lateral trochlear inclination, BMI body mass index, n.s non-significant

	Parameters	Gender	Age	BMI	Height	Weight	Ethnicity
	TGD	(n.s)	(n.s)	(n.s)	(n.s)	(n.s)	(n.s)
	TTTG	(n.s)	(n.s)	(n.s)	(n.s)	(n.s)	(n.s)
	LCI		(n.s)	(n.s)	(n.s)	(n.s)	(n.s)

Funding None.

Compliance with ethical standards

Author contributions LD, AF, SL, PW, MO the conception and design of the study, or acquisition of data, or analysis and interpretation of data. LD, HR, P-L, CJ drafting the article or revising it critically for important intellectual content. LD, HR, P-L, AF, SL, PW, MO, CJ final approval of the version to be submitted. AF, SL, PW, MO statistics. CJ experimentation or surgery performance.

Conflict of interest

One or more of the authors declared the following potential conflict of interest or source of funding: S.L., P.W., and A.F. are employees of Stryker. M.O. has received consulting fees from Arthrex, Newclip Technics, and Stryker. LD received a research scholarship grant from the French Society of Orthopaedic Surgery (SOFCOT) and from the University of Montpellier in 2019, that is not related to this work. PL and CJ: no conflicts of interest.

Ethical approval Each author certifies that his institution has approved the reporting of these cases, that all investigations were conducted in conformity with ethical principles of research. This manuscript contains a study with human participants, which has been approved by our institutional ethics committee (2019-A00912533).

Informed consent Not applicable.


Laurent Bulteau

Philippe Gambette

Olga Seminck

Reordering a tree according to an order on its leaves

Keywords: 2012 ACM Subject Classification Theory of computation → Parameterized complexity and exact algorithms tree, clustering, order, permutation, inversions, FPT algorithm, NP-hardness, tree drawing, OTCM, OTDE, TTDE Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

In this article, we study two problems consisting in reordering a tree to fit with an order on its leaves provided as input, which were earlier introduced in the context of phylogenetic tree comparison for bioinformatics, OTCM and OTDE. The first problem consists in finding an order which minimizes the number of inversions with an input order on the leaves, while the second one consists in removing the minimum number of leaves from the tree to make it consistent with the input order on the remaining leaves. We show that both problems are NP-complete when the maximum degree is not bounded, as well as a problem on tree alignment, answering two questions opened in 2010 by Henning Fernau, Michael Kaufmann and Mathias Poths. We provide a polynomial-time algorithm for OTDE in the case where the maximum degree is bounded by a constant and an FPT algorithm in a parameter lower than the number of leaves to delete. Our results have practical interest not only for bioinformatics but also for digital humanities to evaluate, for example, the consistency of the dendrogram obtained from a hierarchical clustering algorithm with a chronological ordering of its leaves. We explore the possibilities of practical use of our results both on trees obtained by clustering the literary works of French authors and on simulated data, using implementations of our algorithms in Python.

Introduction

The problem of optimizing the consistency between a tree and a given order on its leaves was first introduced in bioinformatics in the context of visualization of multiple phylogenetic trees in order to highlight common patterns in their subtree structure [START_REF] Dwyer | Optimal leaf ordering for two and a half dimensional phylogenetic tree visualisation[END_REF], under the name "one-layer STOP (stratified tree ordering problem)". The authors provided an O(n 2 ) time algorithm to minimize, by exchanging the left and right children of internal nodes, the number of inversions between the left-to-right order of the leaves of a binary tree and an input order on its leaves. The problem was renamed OTCM (One-Tree Crossing Minimization) in [START_REF] Fernau | Comparing trees via crossing minimization[END_REF], where an O(n log 2 n) time algorithm is provided, as well as a reduction to 3-Hitting Set of a variant of the problem where the goal is to minimize the number of leaves to delete from the tree in order to be able to perfectly match the input order on the remaining leaves, called OTDE (One-Tree Drawing by Deleting Edges). An O(n log 2 n/ log log n) time algorithm is later provided for OTCM by [START_REF] Mukul | Generalized binary tanglegrams: Algorithms and applications[END_REF], improved independently in 2010 by [START_REF] Fernau | Comparing trees via crossing minimization[END_REF] and [START_REF] Venkatachalam | Untangling tanglegrams: comparing trees by their drawings[END_REF] to obtain an O(n log n) time complexity. About OTDE, the authors of [START_REF] Fernau | Comparing trees via crossing minimization[END_REF] note that "the efficient dynamic-programming algorithm derived for the related problem OTCM [. . . ] cannot be transferred to this problem. However, we have no proof for NP-hardness for OTDE nor TTDE, either". TTDE (Two-Tree Drawing by Deleting Edges) is a variant of OTDE where two leaf-labeled trees are provided as input and the goal is to delete the minimum number of leaves such that the remaining leaves of both trees can be ordered with the same order. We give below an answer to both sentences, providing a dynamic-programming algorithm solving OTDE for trees with fixed maximum degree as well as an NP-hardness proof in the general case for OTDE and for TTDE.

Although this problem was initially introduced in the context of comparing tree embeddings, one tree having its embedding (that is the left-to-right order of all children) fixed, we can note that only the order on the leaves of the tree with fixed embedding is useful to define both problems OTCM and OTDE. Both problems therefore consist not really in comparing trees but rather in reordering the internal nodes of one tree in order to optimize its consistency with an order on its leaves provided as input. A popular problem consisting in finding an optimal order on the leaves of a tree is "seriation", often used for visualization purposes [START_REF] Earle | Advances in dendrogram seriation for application to visualization[END_REF], where the optimized criterion is computed on data used to build the tree. For example, a classical criterion, called "optimal leaf ordering", is to maximize the similarity between consecutive elements in the optimal order [START_REF] Bar-Joseph | K-ary clustering with optimal leaf ordering for gene expression data[END_REF][START_REF] Bar-Joseph | Fast optimal leaf ordering for hierarchical clustering[END_REF][START_REF] Brandes | Optimal leaf ordering of complete binary trees[END_REF]. Another possibility is to minimize a distance criterion, the "bilateral symmetric distance", computed on pairs of elements in consecutive clusters [START_REF] Chen | Improved upper bounds for vertex cover[END_REF]. Seriation algorithms have been implemented for example in the R-packages seriation [START_REF] Hahsler | Getting things in order: an introduction to the R package seriation[END_REF] and dendsort [19].

With the OTCM and OTDE problems, our goal is not to reorder a tree using only the original data from which it has been built, but using external data about some expected order on its leaves. In the context where the leaves of the tree can be ordered chronologically, for example, this would help providing an answer to the question: how much is this tree consistent with the chronological order? This issue is relevant for several fields of digital humanities, when objects associated with a publication date are classified with a hierarchical clustering algorithm, for example literature analysis [START_REF] Labbé | Existe-t-il un genre épistolaire? Hugo, Flaubert et Maupassant[END_REF], political discourse analysis [START_REF] Leblanc | Analyses lexicométriques des voeux présidentiels[END_REF] or language evolution [START_REF] Moisl | How to visualize high-dimensional data: a roadmap[END_REF], as noticed in [START_REF] Gambette | Evaluating hierarchical clustering methods for corpora with chronological order[END_REF]. In these articles, the comments about the chronological signal which can be observed in the tree obtained from the clustering algorithm are often unclear or imprecise. For example, in [START_REF] Moisl | How to visualize high-dimensional data: a roadmap[END_REF], the author observes about Figure 15 on page 17 that "the cluster tree gives a visual representation consistent with what is independently known of the chronological structure of the corpus". However, the structure of the tree L. Bulteau, P. Gambette, O. Seminck

23:3

does not perfectly reflect the chronology 2 . The algorithms solving the OTCM and OTDE problems can also prevent researchers from claiming having obtained perfect chronological trees with clustering, whereas there are still small inconsistencies that are not easy to spot with the naked eye. For example, although "Chez Jacques Chirac, l'examen des parentés [dans ses discours de voeux] ne suppose aucune rupture, la chronologie étant parfaitement représentée" 3 is claimed about Figure 2.4 in [START_REF] Leblanc | Analyses lexicométriques des voeux présidentiels[END_REF], the 1999 speech cannot be ordered between 1998 and 2000.

In this article, we first give useful definitions in Section 1.1. We answer two open problems from [START_REF] Fernau | Comparing trees via crossing minimization[END_REF], proving that OTDE and TTDE are NP-complete, as well as OTCM, in Section 2.

We then provide a dynamic programming algorithm solving OTDE in polynomial time for trees with fixed maximum degree in Section 3. This algorithm also works in the more general case where the order on the leaves is not strict. We then provide an FPT algorithm for the OTDE problem parameterized by the deletion-degree of the solution, which is lower than the number of leaves to delete, in Section 4. We also give an example of a tree and an order built to have a distinct solution for the OTCM and OTDE problems in Section 5. Finally, we illustrate the relevance of this problem, and of our implementations of algorithms solving them, for applications in digital humanities, with experiments on trees built from literary works, as well as simulated trees, in Section 6.

Definitions

Given a set X of elements, we define an X-tree T as a rooted tree whose leaves are bijectively labeled by the elements of X. The set of leaves of T is denoted by L(T ) and the set of leaves below some vertex v of T is denoted by

L(T, v) (or simply L(v) if T is clear from the context).
A set of vertices of T is independent if no vertex of T is an ancestor of another vertex of T .

We say that σ is a strict order on X if it is a bijection from X to [1..n] and that it is a weak order on X if it is a surjection from X to [1..m], where |X| ≥ m. Given any (strict or weak) order σ, we denote by a ≤ σ b the fact that σ(a) ≤ σ(b) and by a < σ b the fact that σ(a) < σ(b). Considering the elements x 1 , . . . , x n of X such that for each i ∈ [1..n -1], σ(x i ) ≤ σ(x i+1 ), we denote by (x 1 x 2 . . . x n ) the (weak or strict) order σ.

Given an X-tree T and a (weak or strict) order σ on X, we say that an independent pair {u, v} of vertices of T is a conflict wrt. σ if there exist leaves a, c ∈ L(u) and b ∈ L(v)

such that a < σ b < σ c. Conversely, if {u, v} is not a conflict, then either a ≤ σ b for all a ∈ L(u), b ∈ L(v)
, or b ≤ σ a; we then write u ⪯ σ v or v ⪯ σ u, respectively. We say that σ is suitable on T if T has no conflict with respect to σ.

Given two (strict or weak) orders σ 1 and σ 2 on X and two elements a ̸ = b of X, we say that {a, b} is an inversion for σ 1 and σ 2 if a ≤ σ1 b and b < σ2 a, or b ≤ σ1 a and a < σ2 b.

Given an X-tree T , a subset X ′ of X and an order σ on X, we denote by σ[X ′ ] the order σ restricted to X ′ , and by T [X ′ ] the tree T restricted to X ′ , that is the X ′ -tree obtained from T by removing leaves labeled by X \ X ′ and contracting any arc to a non-labeled leaf, any arc from an out-degree-1 vertex. We define the deletion-degree of X ′ as the maximum degree of the tree induced by the deleted leaves, i.e., T [X \ X ′ ]. Intuitively, the deletion-degree measures how deletions in different branches converge on a few nodes or if they merge 2 For example 1380Gawain.txt cannot be ordered between 1375AllitMorteArthur.txt and 1400YorksPlays.txt. 3 "For Jacques Chirac, the examination of the genealogy [of his new year addresses] shows no discontinuity, the chronology being perfectly represented" C V I T 2 0 1 6

23:4

Reordering a tree according to an order on its leaves progressively. Note that by definition, the deletion-degree of X ′ is upper-bounded both by the maximum degree of T and by the size of X \ X ′ . A,D,B,E,C,F) is suitable for T and yields three inversions with σ.

We now define the two main problems addressed in this paper (see Figure 1 for an illustration). As explained in the introduction, we differ from previous definitions which considered two trees, one with a fixed order on the leaves, as input, as only the leaf order of the second tree is useful to define the problem and not the tree itself.

We therefore define the OTCM (One-Tree Crossing Minimization) problem as follows:

Input: An X-tree T , an order σ on X and an integer k.

Output: Yes if there exists an order σ ′ on X suitable on T such that the number of inversions for σ ′ and σ is at most k, no otherwise.

We also define the OTDE (One-Tree Drawing by Deleting Edges) problem as follows:

Input: An X-tree T , an order σ on X and an integer k.

Output: Yes if there exists a subset X ′ of X of size at least |X| -k such that σ[X ′ ] is suitable on T [X ′ ], no otherwise.

We finally define the TTDE (Two-Tree Drawing by Deleting Edges) problem in the following way: Input: Two X-trees T 1 and T 2 and an integer k.

Output: Yes if there exists a subset X ′ of X of size at least |X| -k and an order σ ′ on Proof. First note that OTDE is in NP, since, given an X-tree T , an order σ and a set L of leaves to remove, we can check in linear time, by a recursive search of the tree, saving on each node the minimum and the maximum leaf in σ[X -L] appearing below, whether L. Bulteau, P. Gambette, O. Seminck 23:5

X ′ that is suitable on T 1 [X ′ ] and on T 2 [X ′ ], no otherwise.
σ[X -L] is suitable on T [X -L].
Regarding NP-hardness, we now give a reduction from Independent Set, which is NP-hard on cubic graphs [START_REF] Mohar | Face covers and the genus problem for apex graphs[END_REF], to OTDE when the input trees have unbounded degree.

We consider an instance of the Independent Set problem, that is a cubic graph

G = (V = {v 1 , . . . , v n }, E) such that |E| = m = 3n/2 and an integer k. For each vertex v i ,
we write e 1 i , e 2 i and e 3 i for the three edges incident with v i (ordered arbitrarily).

We now define an instance of the OTDE problem. The set of leaf labels consists of vertex labels denoted v i and v ′ i for each i ∈ [1.

.n], one edge label for each edge (also denoted e j i for the jth edge incident on vertex v i ), and a set of n 2 separating labels

B i = {b 1 i , b 2 i , . . . b n 2 i } for each i ∈ [1..n -1].
First, we define the strict order

σ(G) = (v 1 e 1 1 e 2 1 e 3 1 v ′ 1 b 1 1 b 2 1 . . . b n 2 1 v 2 e 1 2 e 2 2 e 3 2 v ′ 2 b 2 1 b 2 2 . . . b n 2 n-1 v n e 1 n e 2 n e 3 n v ′ n ).
Then, let T vi be the tree with leaves v i and v ′ i attached below the root, T e be the tree with leaves e i ′ i and e j ′ j attached below the root for each edge e

= {v i , v j } of G (with i ′ , j ′ ∈ [1..3]
), and T Bi be the tree with leaves b

1 i , . . . , b n 2 i attached below the root for each i ∈ [1..n-1].
We finally define T (G) as the tree such that T v1 , T v2 , . . . , T vn , T e1 , T e2 , . . . T em , T B1 , T B2 , . . . and T Bn-1 are attached below the root.

We claim that G has an independent set of size at least k ⇔ the instance (T (G), σ(G))

of the OTDE problem has a solution with a set L of at most m + n -k leaves to remove.

⇒: Suppose that there exists a size-k independent set S = {s 1 , . . . , s k } of G. We then remove the following leaves (also contracting along the way the edge from their parent to the root of T (G)) in order to get a new tree T ′ :

for each edge e = {v i , v j } = e i ′ i = e j ′ j with i < j, we remove e i ′ i and call T e j ′ j = T e if v i ∈ S or if neither v i nor v j belong to S;
and we remove e j ′ j and call

T e i ′ i = T e if v j ∈ S
(as S is an independent set we cannot have both v i and v j in S);

for each vertex v i not in S we remove v ′ i .
By ordering the children of the root of T (G) such as in Figure 2(1), that is by putting, for each

v i with i ∈ [1.
.n], T vi , then T e 1 i , T e 2 i and T e 3 i for each of the e i ′ i which were not removed and then T Bi (except for i = n), the order σ(G) restricted to the remaining m

+ n + k + n 2 (n -1)
leaves is suitable on T ′ .

⇐: Suppose that there exists a set

L of at most m + n -k leaves such that σ(G)[X -L] is suitable on T (G)[X -L].
For each parent p Bi of the leaves of B i and any other vertex v of T such that {p Bi , v} is a conflict wrt. σ(G), we can delete this conflict either by deleting no leaf of B i or all leaves of B i . As each B i has size n 2 > m + n -k, its leaves cannot belong to the set L of leaves to be deleted.

We now consider the trees T ei for each i ∈ [1..m]: by construction of σ(G), as both leaves of each such tree are separated by some B i ′ , therefore by n 2 > m + n -k leaves, one of these two leaves has to be removed, so it has to belong to L. We call L ′ the set of such leaves of L, therefore there exists a set L -L ′ of at most n -k other leaves to delete. So there exists a subset S L of [1.

.n] of size at least k such that for any element i ∈ S L , neither v i , nor v ′ i , nor any of the leaves e j i for j ∈ {1, 2, 3} belong to L -L ′ . Note that for such i ∈ S L , all vertices v i and v ′ i are not in L and all e j i are in L ′ . We claim that the vertices of G corresponding to S L are an independent set of G. Suppose for contradiction that it is not the case, then there exists an edge e = e i ′ i = e j ′ j between two vertices v i and v j of G. By construction of L ′ , exactly one of the leaves labeled by e i ′ i and e j ′ j is in L ′ so the second one is in L -L ′ : contradiction. ◀ ▶ Corollary 2. The TTDE problem is NP-complete.

C V I T 2 0 1 6

23:6

Reordering a tree according to an order on its leaves as well as the order σ(G). By removing all leaves connected with dotted lines to the corresponding element in σ(G), the resulting subtree of T (G) is suitable for the order (since the remaining arcs are non-crossing). ( 2) Reduction from an OTDE instance (T, σ) (top) to a TTDE instance (T1, T2) (bottom). A large set of leaves labelled Y can be seen as a fixed-point, around which T1 must be ordered according to σ, and T2 according to the input tree T .

(1) (2)
Proof. TTDE is clearly in NP. We prove hardness by reduction from OTDE (see Figure 2(2) for an illustration). Consider an instance (T, σ) of OTDE with σ a strict order on n labels X. Introduce a set Y of n new labels. Build T 1 as a caterpillar with n + 1 internal nodes forming a path r 1 , . . . , r n+1 (with root r 1 ) and 2n leaves where each r i with i ≤ n has one leaf attached with label σ -1 (i) ∈ X (in the same order), and r n+1 has n leaves attached labelled with Y . Build T 2 as a tree, where the root has two children y, t, where y has n children which are leaves labelled with Y , and t is the root of a subtree equal to T .

We now show our main claim: given 0 ≤ k < n, OTDE(T, σ) admits a solution with at most k deletions ⇔ TTDE(T 1 , T 2 ) admits a solution with at most k deletions.

⇒ Let X ′ be a size-(n -k) subset of X such that σ[X ′ ] is suitable on T [X]. Then let γ be any order on Y : the concatenation σ[X ′ ]γ is suitable both on T 1 [X ′ ∪ Y ] and T 2 [X ′ ∪ Y ],
L. Bulteau, P. Gambette, O. Seminck 23:7 so it is a valid solution for TTDE(T 1 , T 2 ) of size 2n -k, i.e., with k deletions.

⇐ Let X ′ , Y ′ be subsets of X, Y , respectively, and σ ′ be an order on

X ′ ∪ Y ′ such that σ ′ is suitable on both T 1 [X ′ ∪ Y ′ ] and T 2 [X ′ ∪ Y ′ ], and such that |X ′ ∪ Y ′ | ≥ 2n -k > n
(in particular, Y ′ contains at least one element denoted y, and

|X ′ | ≥ n -k). From T 2 , it
follows that σ ′ is the concatenation (in any order) of an order σ x of X ′ suitable for T [X ′ ] and an order σ y of Y ′ . Assume first that σ x appears before σ y . Then consider each internal node r i of the caterpillar T 1 with i ≤ n and a child c labelled with an element X ′ . Then this child must be ordered before all leaves below r i+1 since the corresponding subtree contains all leaves labelled with Y . Thus, the nodes in X ′ are ordered according to σ[X ′ ], hence

σ x = σ[X ′ ], and T [X ′ ] is suitable with σ[X ′ ].
For the other case, where σ y is ordered before σ x , then for each r i with a child in X ′ , this child must be after the subtree with root r i+1 (containing Y ), and the nodes in X ′ are ordered according to the reverse of σ[X ′ ] (i.e.,

σ x = σ[X ′ ]). Thus, the reverse of σ[X ′ ] is suitable for T [X ′ ],
and σ[X ′ ] as well (this is obtained by reversing the permutation of all children of internal nodes of T ). In both cases,

X ′ is a solution for OTDE(T, σ) with |X ′ | ≥ n -k. ◀

OTCM is NP-complete for trees with unbounded degree

▶ Theorem 3. The OTCM problem is NP-complete for strict orders and therefore for weak orders.

Proof. First note that OTCM is in NP, since, given an X-tree T with its leaves ordered according to an order σ ′ on X suitable on T , an order σ and a set L of leaves, the number of inversions between σ ′ and σ can be counted in O(|L| 2 ). Regarding NP-hardness, we now give a reduction from Feedback Arc Set, which is NP-hard [START_REF] Richard | Reducibility among combinatorial problems[END_REF], to OTCM.

We consider an instance of the Feedback Arc Set problem, that is a directed graph G = (V = {v 1 , . . . , v n }, A) such that |A| = m and an integer f .

We now define an instance of the OTCM problem, illustrated in Figure 3. The set X of leaf labels is

{v j i | i ∈ [1..n], j ∈ [1.
.2m]}. We define the order σ(G) in the following way.

For each arc (v i , v j ) of G, whose rank in the lexicographic order is k, we add to σ(G) a k th supplementary ordered sequence (which we will later call a "block" corresponding to this arc)

v 2k-1 i v 2k-1 j X 2k-1 i,j X 2k i,j v 2k i v 2k j , where X k ′ i,j
is the ordered sequence of v k ′ i ′ where i ′ ranges from 1 to n, excluding i and j, and

X k ′ i,j is the reverse of X k ′ i,j (i.e., the ordered sequence of v k ′ i ′
where i ′ ranges from n down to 1, excluding i and j). The tree T (G) is made of a root with Given an ordering σ ′ suitable for T , and an inversion (v k i , v k ′ i ′ ) forming an inversion between σ(G) and σ ′ , we say that this pair is short-ranged if k = k ′ , and long-ranged

n children v 1 to v n , each v i having 2m children, the leaves labeled by v k ′ i for k ′ ∈ [1..2m].
C V I T 2 0 1 6

23:8

Reordering a tree according to an order on its leaves otherwise. Furthermore, we say that σ ′ is vertex-consistent if, for every i and k < k ′ , we have

σ ′ (v k i ) < σ(v k ′ i ).
Finally, given σ ′ , we write σ ′′ for the permutation of the [1.

.n] corresponding to the children of the root.

We first claim that for any σ ′ suitable for T , there are at least 2 n 2 2m 2

long-range inversions between σ ′ and σ(G), and this bound is reached if σ ′ is vertex-consistent. Indeed,

pick any pair (v k i , v k ′ i ′ ) with i ̸ = i ′ and k ̸ = k ′ . Then v k i < σ(G) v k ′ i ′ iff k < k ′ (since they are in
blocks k and k ′ of σ(G)), respectively, and pairs creating an inversion (which is long-range by definition). For the case

v k i < σ ′ v k ′ i ′ iff σ ′′ (i) < σ ′′ (i ′ ) (since
i = i ′ , note that pairs (v k i , v k ′ i ) do not create any inversion iff σ ′ is vertex-consistent, which
completes the proof of the claim.

Towards counting the number of short-ranged inversions, we say that an arc

(v i , v j ) of G is satisfied by σ ′′ if σ ′′ (i) < σ ′′ (j). Let i, j ∈ [1.
.n] and k ∈ [1.

.m], and consider the two

pairs (v 2k-1 i , v 2k-1 j
) and (v 2k i , v 2k j ). Then these two pairs are, by construction of T , in the same order in σ ′ (as defined by σ ′′ ). If the k th arc of G is (v i , v j ), then these two pairs are also in the same order in σ, i.e., together they account for either 0 or 2 (short-ranged)

inversions. More precisely they yield 0 short-ranged inversions if (v i , v j ) is satisfied by σ ′′ , and 2 inversions otherwise. If the k th arc of G is any other arc, then exactly one of

(v 2k-1 i , v 2k-1 j
), (v 2k i , v 2k j ) forms a short-ranged inversion. Overall a pair {i, j} such that one of (v i , v j ), (v j , v i ) is a satisfied arc yields m -1 short-ranged inversions, a pair {i, j} such that one of (v i , v j ), (v j , v i ) is an unsatisfied arc yields m + 1 short-range inversions, and any other pair {i, j} with i ̸ = j yields m short-ranged inversions. Overall, if there are f unsatisfied arcs, σ ′ yields n 2 m -m + 2f inversions.

We can now complete the proof with our main claim: G has a feedback arc set of size at most f ⇔ the OTCM problem has a solution with at most 2 n

2 2m 2 + n 2 m -m + 2f
inversions.

⇒: If G has a feedback arc set F of size f , as G[A -F ] is acyclic, we consider an order σ ′′ over n such that for all arcs (v i , v j ) in A -F , σ ′′ (i) < σ ′′ (j) (i.e., σ ′′ is the topological order of the vertices in G[A -F ]). We now order the children v i of the root of T (G) according to this order σ ′′ and call σ ′ the induced order on the leaves of T (G) (also sorting all leaves v j i below each v i by increasing values of j). Note that σ ′ is vertex-consistent, and that an arc

(v i , v j ) is satisfied by σ ′′ iff (v i , v j ) / ∈ F . Thus, σ ′ yields 2 n 2 2m 2 + n 2 m -m + 2f inversions.
⇐: Consider an order σ ′ suitable for T with at most 2 n

A polynomial-time algorithm for fixed-degree trees

We start by presenting a dynamic programming algorithm for fixed-degree trees, which is easy to implement and leads to an algorithm in O(n 4 ) time for binary trees. The FPT algorithm presented in the next section has a better complexity but is more complex and reuses the dynamic programming machinery presented in this section, which explains why we start with this simpler algorithm.

▶ Theorem 4. The OTDE problem can be solved in time O(d!n d+2

) for trees with fixed maximum degree d and for strict or weak orders.

L. Bulteau, P. Gambette, O. Seminck

23:9

Proof. Given a vertex v of a rooted tree T , a (strict or weak) order σ : L(T ) → [1.

.m] and two integers l ≤ r ∈ [1..m]. We denote by X (v, l, r) a subset of L(T, v) of maximum size such that σ[X (v, l, r)] is suitable with T [X (v, l, r)] and ∀ℓ ∈ X (v, l, r), σ(ℓ) ∈ [l, r]. Note that X (v, l, r) also depends on T and σ but we simplify the notation by not mentioning them as they can clearly be identified from the context.

Denoting by c 1 , . . . , c k the children of v in T , we claim that the following formula allows to recursively compute X (v, l, r) in polynomial time:

|X (v, l, r)| = max permutation π of [1..k] x 1 =l≤x 2 ≤...≤x k ≤x k+1 =r k i=1 X (c π(i) , x i , x i+1 ) if v is an internal node of T ; for any leaf ℓ of T , |X (ℓ, l, r)| = 1 if σ(ℓ) ∈ [l, r], 0 otherwise.

Correctness: We prove by induction on the size of

L(v) that X (v, l, r) is indeed a subset of L(T, v) of maximum size such that σ[X (v, l, r)] is suitable with T [X (v, l, r)] and ∀ℓ ∈ X (v, l, r), σ(ℓ) ∈ [l, r].
This is obvious for any leaf, so let us consider a vertex v of T with a set {c 1 , . . . c k } of children. Suppose for contradiction that there exists a set of integers l ≤ r and a subset

X ′ of L(v) of size strictly greater than X (v, l, r) such that σ[X ′ ] is suitable with T [X ′ ] and ∀ℓ ∈ X ′ , σ(ℓ) ∈ [l,
m i = min ℓ∈X ′ i {σ(ℓ)}, m 1 = l and m k+1 = r.
Using the induction hypothesis we know that

for each i ∈ [1..k], |X ′ i | ≤ X (v, min ℓ∈X ′ i {σ(ℓ)}, max ℓ∈X ′ i {σ(ℓ)}) , so |X ′ i | ≤ |X (v, m i , m i+1 )| because min ℓ∈X ′ i {σ(ℓ)}, max ℓ∈X ′ i {σ(ℓ)} ⊆ [m i , m i+1 ]. Therefore, |X ′ | = k i=1 |X ′ i | ≤ k i=1 |X (v, m i , m i+1 )| so by definition of σ[X (v, l, r)], |X ′ | ≤ σ[X (v, l, r)]: contradiction!
We therefore obtain a correct solution of OT DE(T, σ) by computing X (root(T ), 0, m). ). So the computation of each X (v, l, r) is done in time

Running

O(d!n d-1 ), therefore the total computation of all X (v, l, r) is done in time O(n × n 2 × d!n d-1 ), that is in O(d!n d+2 ). ◀

An FPT algorithm for the deletion-degree parameter for OTDE

We recall that with a reduction of OTDE to 3-Hitting Set [START_REF] Fernau | Comparing trees via crossing minimization[END_REF], using the best algorithm known so far to solve this problem 4 , we can obtain an algorithm to solve OTDE O * (2.08 k ) [START_REF] Wahlström | Algorithms, measures and upper bounds for satisfiability and related problems[END_REF],

where k is the number of leaves to delete and the O * notation ignores the polynomial factor.

In this section we obtain an FPT algorithm in time O(n 4 d∂2 ∂ ), where d is the maximum degree of the tree and ∂ is the deletion-degree of the solution.

▶ Theorem 5. The OTDE problem parameterized by the deletion-degree ∂ of the solution is

FPT and can be solved in time O(n 4 d∂2 ∂ ) for strict or weak orders.

We adapt the dynamic programming algorithm from Theorem 4, using a vertex cover subroutine to have a good estimation of the permutation of the children of each node. We first introduce some definitions (see Figure 4 for a illustration of these definitions and the algorithm in general). Given any vertex v of T , let C v be the (independent) set of children of v, and let G v be the conflict graph with vertex set C v and with one edge per conflict. Let K be a vertex cover of G v . Then the vertices of C v \ K have a canonical order (w 1 , . . . , w k ′ ), with k ′ = |C v \ K| and w i ⪯ σ w j for all i ≤ j (ties may happen when two children contain a single leaf each which are equal, such ties are broken arbitrarily). We say that P ⊆ C v is a prefix of C v wrt. K if P \ K is a prefix of this order (i.e., for some i ≤ k ′ , P \ K = {w 1 , . . . , w i }). In other words, ignoring all subtrees below vertices of K, all leaves below vertices of a prefix P are necessarily ordered before leaves below vertices outside of P . ▶ Lemma 6. If X ′ is a solution of OTDE with deletion-degree ∂, then for any vertex v of T , the conflict graph G v admits a vertex cover of size at most ∂.

Proof. Given a subset X ′ of X, we say that a node v of T has a deletion if some L(v) ̸ ⊆ X ′ , i.e., if v has a leaf in X \ X ′ . Let {u, v} be any conflict (edge) of the conflict graph G v , then at least one of u, v has a deletion for X ′ (indeed, the conflict involves three leaves a, b, c, of which at least one must be deleted). Thus, the vertices with a deletion in G v form a vertex cover of this graph. The lemma follows from the fact that at most ∂ vertices have a deletion in each conflict graph. ◀

The first step of our algorithm consists in computing, for each node v of the graph, the set C of children of v, its conflict graph G v , and a minimum vertex cover

K v of G C . Since each K v has size at most ∂ (by Lemma 6), K v can be computed in time O(1.3 ∂ + ∂n) [5],
and overall this first step takes O(1.3 ∂ n + ∂n 2 ).

We proceed with the dynamic programming part of our algorithm. To this end, we generalize the table X to sets of nodes (instead of only v) as follows: X (P, l, r) corresponds to the largest set X of leaves in u∈P L(u) such that σ X is suitable for T

[X]. Note that for a node v with children set C, X (v, l, r) = X ({v}, l, r) = X (C, l, r).
We first compute X ({v}, l, r) for each leaf v:

clearly X ({v}, l, r) = {u} if l ≤ σ(v) ≤ r,
and X ({v}, l, r) = ∅ otherwise. For each internal vertex v (visiting the tree bottom-up), we obtain X ({v}, l, r) by first computing X (P, l, r) for each prefix P of C v by increasing order of size, using the following formulas:

|X (P, l, r)| = ∅ if P = ∅ = max x∈[l..r], u∈P P \{u} prefix of Cv |X (P \ {u}, l, x)| + |X ({u}, x, r)| |X ({v}, l, r)| = |X (C v , l, r)|
Each vertex v has at most d2 ∂ prefixes, so the dynamic programming table X has at most n 3 d2 ∂ cells to fill. For each prefix P , there exist at most ∂ + 1 vertices u ∈ P such that P \ {u} is a prefix (u can be any vertex in P ∩ K v , or the maximum vertex for

⪯ σ in P \ K v ).
Overall, the max is taken over O(n∂) elements, and X can be filled in time O(n 4 d∂2 ∂ ).

Before proving the correctness of the above formula, we need a final definition: given a set of leaves X ′ ⊆ X and a vertex v of T , we write span X ′ (v) for the smallest interval containing σ(u) for each leaf u ∈ L(u) ∩ X ′ (note that span X ′ (v) may be empty, if all its leaves are deleted in X ′ ).

▶ Lemma 7. Let X ′ be a solution of OTDE(T, σ), v ∈ T and 1 ≤ l ≤ r ≤ m such that span X ′ (v) ⊆ [l, r].
Then there exists a permutation (c 1 . . . c k ) of the children of v and

integers x 0 = l ≤ x 1 ≤ . . . ≤ x k = r such that, for each i ≤ k, (a) span X ′ (c i ) ⊆ [x i-1 , x i ], and (b) P i = {c 1 , . . . , c i } is a prefix of the children of v wrt. σ.
Proof. Recall that we write C v and K v , respectively, for the set of chidren of v and the vertex cover in the conflict graph induced by these children. For each element c of C v with a non-empty span, let x(c) = max(span(c)). For each element w i of C v \ K v with an empty span (taking i for the rank according to the canonical order), let x(w i ) = x(w i-1 ) (and x(w 1 ) = l for i = 1). For the remaining vertices (in K v with an empty span), set x(c) = l.

Finally, order vertices c 1 , . . . , c k by increasing values of x(c i ) (breaking ties according to the canonical order when applicable, or arbitrarily otherwise), and set x i = x(c i ).

Condition (a) follows from the fact that X ′ is a solution for OTDE(T, σ), so that the span covered by the leaves under siblings do not overlap. For condition (b) we refer to the definition of prefix: each

P i \ K c is indeed a prefix in the canonical ordering of C v \ K v . ◀
The dynamic programming formula follows from the above remark: one can build the solution by incrementing prefixes one vertex at a time (rather than trying all possible permutations of children, as in Theorem 4).

5

Optimizing OTCM and OTDE are two different things

In order to ensure that finding the smallest k such that OTCM or OTDE outputs a positive answer actually consists in optimizing different criteria, we provide in Figure 5 an example of X-tree and an order of its leaves where the order reaching the best k for a positive answer of the OTCM problem does not provide the optimal value for the number of leaves to delete in a positive answer of OTDE and where the best k for a positive answer of the OTDE problem does not provide an optimal value for the number of inversions for a positive answer of the OTCM problem.

We checked the optimality for both criteria by implementing the "naive" dynamic programming O(n 2 ) algorithm described in Section 2.1 of [START_REF] Fernau | Comparing trees via crossing minimization[END_REF] to solve the OTCM problem and the O(n 4 ) algorithm described in Section 3 to solve the OTDE problem on binary trees.

C V I T 2 0 1 6 23:12 Reordering a tree according to an order on its leaves

Both implementations are available in Python, under the GPLv3 licence, at https://github. com/oseminck/tree_order_evaluation, as well as the file inputCounterExample1b.txt containing the Newick encoding for the tree of Figure 5.

T σ1 σ σ σ2 T Figure 5
Two planar embeddings of a rooted tree T : the one on the left is optimal for the OTDE problem (deleting the 3 gray leaves makes the order σ suitable on T restricted to the remaining leaves, but the order σ1 suitable on T has 11 inversions, shown with empty circles, with σ); the other one is optimal for the OTCM problem with the order σ2 suitable on T having 10 inversions with σ but not for the OTDE problem (4 leaves, for example the 4 gray ones, need to be deleted to make the order σ suitable on T restricted to the remaining leaves).

Experiments and discussion

In this section, we investigate the potential for use of OTCM and OTDE in applications where the tree of elements is obtained from a clustering algorithm taking as input distances between those elements, and where we want to test whether this clustering reflects some intrinsic order on the elements, for example the chronological order. We both test the running time of OTCM and OTDE on real data, and the performance of OTDE on simulated data to detect possibly misplaced leaves in the order.

The first experiment deals with text data: the CIDRE corpus [START_REF] Seminck | The corpus for idiolectal research (CIDRE)[END_REF] that contains the works of 11 French 19 th century fiction writers dated by year (every file contains a book that is annotated with its year of writing). We apply apply hierarchical clustering on the different corpora using the AgglomerativeClustering class from the package sklearn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. Distance matrices on which the clustering is based are obtained by using the relative frequencies of the 500 most frequent tokens 5 in each corpus. Distance matrices were generated using the R package stylo [START_REF] Eder | Stylometry with R: a package for computational text analysis[END_REF], with the canberra distance metric. We obtain the results given in Table 1, which provides the running time in milliseconds of the algorithms we implemented to solve OTCM and OTDE. They show that both algorithms on binary trees are quick enough to handle typical instances of the OTCM and the OTDE problems relevant for digital humanities, a few milliseconds for the first one and a few seconds for the second one, for 5 A token is (a part of) a word form or a punctuation marker. The last sentence would yield the following tokens: ["A", "token", "is", "(", "a", "part", "of", ")", "a", "word", "form", "or", "a", "punctuation", "marker", "."] Deliberately, we do not use the term "word", because the word can be seen as a linguistic unit of form and meaning, and henceforward "punctuation marker" would be one word and the period in the end of the sentence would not be one. instances of about 50 elements in the tree and in the order.

Investigating precisely whether the numbers of inversions or deleted leaves shown in Table 1 are sufficiently small to reflect consistency with a chronological signal is beyond the scope of this paper. However, we also provide p OT CM and p OT DE , the percentage of cases when the best order on the leaves of the tree has the same number of inversions, or less than the chronological order, among 10000 randomly generated orders for OTCM and 100 randomly generated orders for OTDE, respectively 6 . These numbers illustrate that in all cases, it is unlikely that the observed optimal numbers of inversions or deleted leaves are due to chance, as we get equal or smaller values of inversions or deleted leaves on less than 3% of random orders (for Ponson du Terrail the number of inversions is 167 or less for 2.23% of random orders; for one of the 10 000 simulated random orders, it reached as little as 124 inversions). These preliminary results obtained thanks to reasonably small running times open new perspectives in investigating further the practical use of these algorithms, and comparing their results with other methods to search for signals of chronological evolution in textual data [START_REF] Seminck | The evolution of the idiolect over the lifetime: A quantitative and qualitative study on French 19 th century literature[END_REF].

Our second experiment involves simulated data, to check whether, in the case the tree is built to be consistent with the input order, our algorithm finding the minimum of leaves in the tree to remove inconsistencies with the order is able to detect errors that we intentionally add to the order. We produced 100 instances of the OTDE problem, for each chosen value of n, the number of leaves, and e < n, the number of errors, in the following manner:

1. we randomly pick n distinct integers from the interval [0, 999], which will be our set X of leaves;

2. we build a distance matrix in which the distance between two elements from X is simply the absolute difference between both; we add some noise to this matrix by adding or subtracting in each cell a random quantity equal to at most 10% of the cell value, obtaining a noisy matrix, from which we build an X-tree T using the AgglomerativeClustering class from the package sklearn; 2 Results of the attempts to perfectly detect the set Le of randomly relabeled leaves in simulated trees (when L = Le); the situation when |L -Le| = 1 corresponds to finding only e -1 leaves among the e randomly relabeled leaves).

randomly chosen from the interval [0, 999], distinct from other leaf labels; σ is the set of leaves ordered by increasing value taking into account these new values; 4. by solving the OTDE problem on T and σ, we compute the minimum set L of leaves to remove to make σ[X -L] suitable on T [X -L], and check whether L = L e . This experiment simulates the situation where we would have dating errors on the elements we clustered in a tree. Note that like in the case of dating errors, the error in our simulation may not change the overall order on the leaves. Table 2 provides, for each chosen values of n and e, the proportion of simulated instances of OT DE where L = L e , that is when our algorithm removed exactly the e leaves whose label had been randomly modified. We can observe that this happens in a majority of cases only when the number of modified leaves is small compared with the total number of leaves (up to 2 for 20 leaves, up to 4 for 50 leaves).

Solving OTDE still allows to identify e -1 among the e modified leaves in a majority of cases in all our experiments.

Conclusion and perspectives

In this article, we addressed two problems initially introduced with motivations from bioinformatics, OTCM and OTDE. We stated them in a more simple framework with a tree and an order as input, instead of two trees as was the case when they were introduced, opening perspectives for new practical uses in digital humanities and proving that they are not equivalent. We proved that both problems, as well as a problem on two trees, TTDE, are NP-complete in the general case. We gave a polynomial-time algorithm for OTDE on trees with fixed maximum degree and an FPT algorithm in a parameter possibly smaller than the size of the solution for arbitrary trees.

We also investigated their potential for practical use, checking that the algorithms we implemented with open source code in Python to solve them are well suited for applications in digital humanities in terms of running time. We also observed on simulated data that it is possible to identify a small number of leaves for which there would be an ordering error if the tree is built from distance data derived from an order on its leaves. Future research includes the search for FPT algorithms, with relevant parameters, for OTCM and TTDE.

Figure 1

 1 Figure 1 Example for the OTDE and OTCM problem. Left: a tree T on leaves {A, . . . , F}, the reference permutation is σ = (A, B, C, D, E, F) (more precisely, σ(A) = 1, . . . , σ(F) = 6). Middle: a solution for OTDE with cost 2. The subtree T [X ′ ] for X ′ = {A, D, E, F} is ordered to show the absence of conflicts with σ[X ′ ]. Right: a solution for OTCM with cost 3. The order σ ′ = (A, D, B, E, C, F) is suitable for T and yields three inversions with σ.

▶ Theorem 1 .

 1 The OTDE problem is NP-complete for strict orders and therefore for weak orders.

Figure 2

 2 Figure 2 Illustration of the reductions of Independent Set to OTDE and of OTDE to TTDE. (1, left) A graph G with independent set S = {v1, v4} of size 2. (1, right) The corresponding tree T (G)as well as the order σ(G). By removing all leaves connected with dotted lines to the corresponding element in σ(G), the resulting subtree of T (G) is suitable for the order (since the remaining arcs are non-crossing). (2) Reduction from an OTDE instance (T, σ) (top) to a TTDE instance (T1, T2) (bottom). A large set of leaves labelled Y can be seen as a fixed-point, around which T1 must be ordered according to σ, and T2 according to the input tree T .

Figure 3

 3 Figure 3 Illustration of the reduction of Feedback Arc Set to OTCM: a graph G with feedback arc set S = {(v4, v1)} of size 1 and the corresponding tree T (G) as well as the order σ(G).

  they are in L(T, v i ) and L(T, v i ′ ), respectively). Overall, among 4 n

2 2m 2 + n 2 m 2 2m 2 long-range inversions, it has at most n 2 m

 222222 -m + 2f inversions. Let σ ′′ be the corresponding order on the leaves of the root, and let F be the set of arcs unsatisfied by σ ′′ . Since σ ′ has at least 2 n -m + 2f short-range inversions, and |F | ≤ f . Finally, since all arcs in A -F are satisfied by σ ′′ , G[A -F ] is acyclic and F is a feedback arc set. ◀

  -time: For each v, we compute the table of the O(n 2 ) values of X (v, l, r) for all intervals [l, r]. Each of these values can be computed by generating the k! permutations of children of v to consider any possible order among the children and splitting the interval [l, r] into any possible configurations of d consecutive intervals with integer bounds partitioning [l, r], which can be done in time O(n d-1

Figure 4

 4 Figure 4 An instance (T, σ) of OTDE (top-left), with a vertex v having children set Cv = {a, b, c, d, e}. The conflict graph of Cv (right) has a size-2 vertex cover K = {b, d}. Based on the span of each vertex (bottom-right), the dynamic programming algorithm tests permutations of Cv such that (a, c, e) appear in this order, interleaved in any possible way with b and d. In particular, the final solution corresponds to the permutation (a c d b e) of Cv. Note that since σ may be a weak order (two leaves are labelled 3 in the example), the conflict graph does not correspond exactly to the intersection graph of the span intervals, e.g. vertices a and c are not in conflict, even though their spans overlap.

3 .

 3 we randomly pick a set L e of e leaves in X and replace their value by another integer, n = # leaves e = # errors proportion of cases when L = Le when |L -Le| = 1 20 1 0

Table 1

 1 Results of our implementations for problems OTCM and OTDE on binary trees generated from corpora of French novels of the 19 th century. Time durations are given in milliseconds.

	tree	# leaves	OTCM time	# inversions pOT CM	OTDE time	# deleted leaves	pOT DE
	Ségur	22	1	40	0.24	200	9	1
	Féval	23	2	47	0.38	268	8	0
	Aimard	24	1	35	0	401	8	0
	Lesueur	31	1	48	0	676	13	0
	Zévaco	29	1	42	0	727	11	0
	Zola	35	2	60	0	1203	9	0
	Gréville	36	2	105	0	2211	18	1
	Ponson	42	3	167	2.23	3447	18	0
	Balzac	59	4	248	0	8292	34	0
	Verne	58	3	183	0	13446	27	0
	Sand	62	4	283	0	17557	39	1

http://fpt.wikidot.com/fpt-races C V I T 2 0 1 6

We chose to generate less random orders for OTDE in our simulations, as our algorithm is slower to solve this problem than OTCM.C V I T 2 0 1 6

Funding Philippe Gambette: "Investissements d'avenir" program, reference ANR-16-IDEX-0003 (I-Site Future, programme "Cité des dames, créatrices dans la cité").

Olga Seminck: "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute)

//github.com/oseminck/tree_order_evaluation