Computing the Inversion-Indel Distance
Eyla Willing Jens Stoye Marília D. V. Braga


 

2mm



1.5
   




⟶
 




   














1.0

   




 











#1

#1













OT1pzc
OT1pzcmit<-> s * [1.200] pzcmi7t
OT1pzcmit

definitionDefinition
theoremTheorem
lemmaLemma
propositionProposition
corollaryCorollary
observationObservation
reductionReduction Bound










































































     







































#1(0,0)
  ( 16,-24)(8,-12)(0,0)
      (-16,-24)(-8,-12)(0,0)
      (-16,-24)(0,-24)(16,-24)
  (00,-15)(0,0)#1




































(0,0)
  (0,0)(0,0)▪


#1(0,0)
  (0,0)(0,0).55


black

black

#1(0,0)
  (0,0)(0,0).55


black

black













#1(0,0)
  (0,0)(0,0).55


black

black







#1(0,0)
  (0,-13)(0,0)#1


#1(0,0)
  (0,13)(0,0)#1


#1(0,0)
  (11,7)(0,0)#1


#1(0,0)
  (13,0)(0,0)#1


#1(0,0)
  (-13,0)(0,0)#1


(0,0)
  (0,0)*14
  (0,0)14


(0,0)
  (0,0)*14


(0,0)
  (0,0)
  
  
  (0,0)(0,0)7pt6pt


(0,0)
  (0,0)
  (0,0)
  


(0,0)
  (0,0)
  (0,0)


(0,0)
  (0,0)
  (0,0)


(0,0)
  (0,0)
  (0,0)
  


(0,0)
  (0,0)
  (0,0)


(0,0)
  (0,0)
  (0,0)


#1(0,0)
              (0,0)#1
            

#1#2(0,0)
  (0,0)(0,-1)20
  (0,0)#1
  (0,-20)#2


#1#2(0,0)
  (0,0)(-1,0)20
  (0,0)#1
  (-20,0)#2


#1#2(0,0)
  (0,0)(1,0)20
  (0,0)#1
  (20,0)#2


#1#2(0,0)
  (-15,0)(1,0)30
  
  (-15,0)#1
  (15,0)#2


#1#2(0,0)
  (-25,0)(1,0)50
  
  (-25,0)#1
  (25,0)#2


#1#2(0,0)
  (-40,0)(1,0)80
  
  (-40,0)#1
  (40,0)#2


#1#2(0,0)
  (-50,0)(1,0)100
  
  (-50,0)#1
  (50,0)#2


#1#2#3(0,0)
  (-100,0)(1,0)70
  (-40,0)(1,0)130
  
  (-100,0)#1
  (-40,0)#2
  ( 90,0)#3


#1#2#3(0,0)
  (-50,0)(1,0)50
  (0,0)(1,0)50
  
  (-50,0)#1
  (0,0)#2
  (50,0)#3


#1#2#3#4#5#6(0,0)
(0,0)(-3,-1)50
  (0,0)(-5,-3)30
  (0,0)(0,-1)20
  (0,0)(5,-3)30
(0,0)(3,-1)50
  (0,0)#1
  (-50,-20)#2
  (-25,-20)#3
  (0,-20)#4
  (25,-20)#5
  (50,-20)#6


#1#2#3#4#5(0,0)
  ( 0,0)(-30,-10)(-60,-20)
  ( 0,0)(-10,-10)(-20,-20)
  ( 0,0)(10,-10)(20,-20)
  ( 0,0)(30,-10)(60,-20)
    (0,0)#1
  (-60,-20)#2
  (-20,-20)#3
  (20,-20)#4
  (60,-20)#5


#1#2#3#4#5(0,0)
(0,0)(-3,-2)30
  (0,0)(-1,-2)10
  (0,0)(1,-2)10
  (0,0)(3,-2)30
    (0,0)#1
  (-30,-20)#2
  (-10,-20)#3
  (10,-20)#4
  (30,-20)#5


#1#2#3#4#5(0,0)
(0,0)(-3,-1)50
(0,0)(-3,-2)30
  (0,0)(-1,-2)10
  (0,0)(1,-2)10
    (0,0)#1
  (-50,-20)#2
  (-30,-20)#3
  (-10,-20)#4
  (10,-20)#5


#1#2#3#4#5(0,0)
(0,0)(-3,-2)30
  (0,0)(-1,-2)10
  (0,0)(1,-2)10
  (0,0)(3,-1)50
    (0,0)#1
  (-10,-20)#2
  (10,-20)#3
  (30,-20)#4
  (50,-20)#5


#1#2#3#4(0,0)
  (0,0)(-4,-3)20
  (0,0)(4,-3)20
  (0,0)(0,-1)20
  (0,0)#1
  (-20,-20)#2
  (0,-20)#3
  (20,-20)#4


#1#2#3#4(0,0)
  (0,0)(-2,-1)30
  (0,0)(2,-1)30
  (0,0)(0,-1)20
  (0,0)#1
  (-30,-20)#2
  (0,-20)#3
  (30,-20)#4


#1#2#3#4(0,0)
  (0,0)(-5,-2)40
  (0,0)(-4,-3)20
  (0,0)(0,-1)20
  (0,0)#1
  (-40,-20)#2
  (-20,-20)#3
  (0,-20)#4


#1#2#3#4(0,0)
  (0,0)(0,-1)20
  (0,0)(4,-3)20
  (0,0)(5,-2)40
  (0,0)#1
  (0,-20)#2
  (20,-20)#3
  (40,-20)#4


#1#2#3#4(0,0)
  (0,0)(-3,-1)50
  (0,0)(3,-1)50
  (0,0)(0,-1)20
  (0,0)#1
  (-50,-20)#2
  (0,-20)#3
  (50,-20)#4


#1#2#3(0,0)
  (0,0)(-1,-1)20
  (0,0)(1,-1)20
  (0,0)#1
  (-20,-20)#2
  (20,-20)#3


#1#2#3(0,0)
  (0,0)(-4,-3)20
  (0,0)(0,-1)20
  (0,0)#1
  (-20,-20)#2
  (0,-20)#3


#1#2#3(0,0)
  (0,0)(0,-1)20
  (0,0)(4,-3)20
  (0,0)#1
  (0,-20)#2
  (20,-20)#3


#1#2#3(0,0)
  (0,0)(-1,-2)10
  (0,0)(1,-2)10
  (0,0)#1
  (-10,-20)#2
  (10,-20)#3


#1#2#3(0,0)
  (0,0)(-3,-2)30
  (0,0)(3,-2)30
  (0,0)#1
  (-30,-20)#2
  (30,-20)#3


#1#2#3(0,0)
  (0,0)(-5,-2)40
  (0,0)(5,-2)40
  (0,0)#1
  (-40,-20)#2
  (40,-20)#3


#1#2#3(0,0)
  (0,0)(-3,-1)50
  (0,0)(3,-1)50
  (0,0)#1
  (-50,-20)#2
  (50,-20)#3











Computing the Inversion-Indel Distance
    Eyla Willing, Jens Stoye and Marília D. V. Braga
E. Willing, J. Stoye and M. D. V. Braga are with the Genome Informatics group, Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Germany
    December 30, 2023
===============================================================================================================================================================================================================================




The inversion distance, that is the distance between two unichromosomal genomes with the same content allowing only inversions of DNA segments, can be exactly computed

thanks to a pioneering approach of Hannenhalli and Pevzner from 1995.
In 2000, El-Mabrouk extended the inversion model to perform the comparison of unichromosomal genomes with unequal contents, combining inversions with insertions and deletions (indels) of DNA segments, giving rise to the inversion-indel distance.
However, only a heuristic was provided for its computation.
In 2005, Yancopoulos, Attie and Friedberg started a new branch of research by introducing the generic double cut and join (DCJ) operation, that can represent several genome rearrangements (including inversions).
In 2006, Bergeron, Mixtacki and Stoye showed that the DCJ distance can be computed in linear time with a very simple procedure.
As a consequence, in 2010 we gave a linear-time algorithm to compute the DCJ-indel distance.
This result allowed the inversion-indel model to be revisited from another angle.
In 2013, 
we could show that, when the diagram that represents the relation between the two compared genomes has no bad components, the inversion-indel distance is equal to the DCJ-indel distance.
In the present work we complete the study of the inversion-indel distance by giving the first algorithm to compute it exactly even in the presence of bad components.



Computational biology, genome rearrangements, genomic distance, inversions, reversals, insertions, deletions, indels.

 



§ INTRODUCTION


Genome rearrangement is a branch of comparative genomics that analyses the arrangement of two or more genomes on an abstract level, in which a genome is represented as one (unichromosomal) or more (multichromosomal) ordered sequences of oriented DNA fragments (markers).
The structural rearrangements of chromosomal segments, such as inversions, translocations and transpositions, besides fusions and fissions of chromosomes, can change the location (with respect to the chromosome), the order and the orientation of markers.
A natural measure of comparison is then the distance, that counts the minimum number of rearrangements required to transform one given genome into another one.
	
One of the first proposed 
models aimed to compare unichromosomal genomes (e.g. of bacteria), considering only inversions of contiguous markers.
Hannenhalli and Pevzner <cit.> devised a polynomial time algorithm to compute the inversion distance when each marker occurs exactly once in each genome, based on a diagram that represents the relation between the two given genomes and is composed of cycles only.
While for most of the instances based on real data the inversion distance can be obtained by simply counting the number of cycles in this diagram, the complete analysis of the problem requires the computation of other parameters – called bad components –
that can be derived from the 
relational diagram by a procedure that is considerably technical.
	
The inversion model was then extended to a 
multichromosomal model including, besides inversions, also fusions and
fissions of chromosomes, and translocations, still allowing, with a
technically even more complex procedure, the exact computation of the distance
in polynomial time 
when each marker occurs exactly once in each genome <cit.>.

A relaxation on the genome content allows markers that occur
in one genome but not in the other, and vice-versa. 
A marker of this type
can be added to or removed from a genome by content-modifying operations
called insertions and deletions (indels collectively).
Combining structural rearrangements and indels is non-trivial if 
contiguous markers can be inserted or deleted in a single event.
Almost 20 years ago, El-Mabrouk <cit.> studied the
inversion model with this relaxation to include indels. 
However, specially due to its technical complexity, the author could give only a heuristic to compute the inversion-indel distance.
     
The field of genome rearrangement received a new boost when
Yancopoulos, Attie and Friedberg <cit.> presented a generic
model, based on the double cut-and-join (DCJ) operation, that
allows inversions, translocations, fissions and fusions, and also
excisions and integrations of circular chromosomes. It was shown that the
DCJ distance can be computed with the help of a surprisingly
simple, linear time procedure when each maker occurs exactly once in each
genome <cit.>.
The relaxation of the genomes to include indels, besides DCJ operations,
increased the technical aspects of the model, but
immediately resulted in a linear time exact
algorithm to compute the DCJ-indel
distance <cit.>.
    
The potential of using the DCJ model to revisit the inversion model in a
more efficient way was first demonstrated
in <cit.>.
More recently, the DCJ-indel model was used to give the first exact
algorithm to compute the inversion-indel distance in the absence of
bad components <cit.>.
In the present work, we complete the study of the inversion-indel model by
giving a quadratic time algorithm to exactly compute the respective
distance even in the presence of bad components. 
Observe that, since inversions are intrachromosomal rearrangements, the
inversion-indel model is restricted to unichromosomal genomes.
Our approach is developed considering circular chromosomes, but can be easily generalized to linear chromosomes[Linear chromosomes can be artificially “circularized” by the well known technique of capping its two extremities. Fixing the capping of one chromosome, there are only two possible ways of capping the other chromosome. The choice that gives the smaller inversion-indel distance gives the overall result.].


This paper is organized as follows. In Section <ref>, we show how the relational 
diagram, with its good and bad components, allows the study of the inversion-indel model and gives a lower bound to the inversion-indel distance. In Section <ref> we introduce the tagged component tree, a structure that helps us to handle

bad components. In Section <ref> we present our main results, effectively showing how to use the tagged component tree to compute the inversion-indel distance. This requires a lengthy, but
finite analysis of cases of bad component cutting and merging. 
In our approach we first safely reduce the tagged component tree to a residual tree with 2 to 10 leaves.

Then we enumerate the optimal covers of all possible residual trees. Each possible residual tree corresponds to a topology with a certain leaf composition. Our enumeration includes 56 leaf compositions, each one corresponding to an average of 3 topologies.
We present some key examples of the case analysis, 
explaining the properties that need to be considered. The full
enumeration is then given in the appendix.
Section <ref> concludes with a short summary. 




§ PRELIMINARIES


Each marker in a chromosome is an oriented DNA fragment.
The representation of a marker g in a chromosome  can be
the symbol g, if it is read in direct orientation in , or the
symbol g, if it is read in reverse orientation.
In the present work, duplicated markers are not allowed. 

We represent a circular chromosome  by a string s, obtained by the concatenation of all symbols
in , read in any of the two directions (since  is circular, we can start to read it at any marker).

Given two circular chromosomes  and , possibly with
unequal contents, let ≫, å and 
be three disjoint sets, such that ≫ is the set of common markers that
occur once in  and once in , å is the set of markers that occur only
in , and  is the set of markers that occur only in . The markers in
sets å and  are also called unique markers.
For example, if we have =(abx̅c̅yd) and =(asbuvcd),
then ≫={a,b,c,d}, å={x,y} and ={s,u,v}.












































































































 §.§ The inversion-indel model



An inversion is the operation
that cuts a circular chromosome at two different positions, creating two linear
segments with four open ends, and joins these open ends such that in the new
circular chromosome the relative orientation of the linear
segments is inverted.
Consider, for example, an inversion applied to chromosome =(abx̅c̅yd), that cuts before and after x̅c̅, creating the
segments ∙ ydab∙ and
∙x̅c̅∙, where the symbol ∙ represents
the open ends. If we then join the first with the third and the second with the fourth
open end, we obtain
'=(abcxyd), in which the orientation
of x̅c̅ is inverted with respect to the longer segment.


Since the chromosomes can have unequal marker sets, we also need to consider insertions and
deletions of blocks of contiguous markers <cit.>.
We refer to insertions and deletions collectively as indels.
Indels have two restrictions <cit.>: (i) markers of ≫ cannot be deleted; and (ii)
an insertion cannot produce duplicated
markers.
We illustrate an indel
with the following example: the deletion of markers xy from chromosome '=(abcxyd) results
in ”=(abcd).


Given two circular chromosomes  and , one can transform or
sort  into  with inversions and indels.
We are particularly interested in
computing the inversion-indel distance, that is denoted by (,)
and corresponds to the minimum number of inversions and indels required to sort
 into .
Observe that, if |≫| ≤ 1, the problem of sorting  into 
becomes trivial: we simply delete at once the unique content of the chromosome
of  and insert at once, in the proper orientation, the unique content of the
chromosome of . Due to this fact, we assume in this work that |≫| ≥ 2.



 §.§ Relational diagram


Given two circular chromosomes  and , their relational
diagram <cit.>, denoted by R(,), is a particular view of the master graph <cit.> and shows the elements of chromosome 
in an upper horizontal line and the elements of chromosome  in a lower
horizontal line.
We denote the two extremities of each marker g ∈≫ by g (tail) and g (head).
For each extremity of g the diagram R(,) has a vertex in the upper line and a vertex in the lower line.
Clearly, each line (that corresponds to one of the two chromosomes) has 2|≫| vertices,
and its vertices are distributed following the same order of the corresponding chromosome.
Since the chromosomes are circular, we have to choose one marker a ∈≫ from which we start to read
both chromosomes, s.t. in both lines the leftmost vertex is a^h and the rightmost is a^t.
Then, for each marker g ∈≫, we connect the upper and the lower vertices
that represent g by a dotted edge.
Similarly, we connect the upper and the lower vertices that represent g
by a dotted edge.

Moreover, for each integer i from 1 to |≫|, let _i^1 and _i^2 be
the upper vertices (analogously lower vertices) at positions 2i-1 and 2i of
the corresponding line of the diagram.
We connect the upper vertices (analogously lower vertices) _i^1 and _i^2
by an -edge (analogously -edge) labeled by ℓ,
which is the substring composed of the markers of chromosome  (analogously chromosome )
that are between the extremities represented by _i^1 and _i^2.
We say that _i^1 and _i^2 are ≫-adjacent, that is, they represent extremities of
occurrences of markers from ≫ in chromosome  (analogously ), so that in-between only markers
from å (analogously ) can appear. In other words, the label ℓ contains no marker of ≫.
When the label of an -edge (or a -edge) is empty, the edge is
said to be clean, otherwise it is said to be labeled.

Each vertex is now connected to one dotted edge and either to one -edge
(for the upper vertices) or to one -edge (for the lower vertices), thus the
degree of each vertex is two and the diagram is simply a collection of cycles.
Each cycle alternates a pair (-edge, dotted edge) with a pair 
(-edge, dotted edge), consequently the length of each cycle is a multiple
of 4.
A cycle that contains at least one labeled edge is said to be labeled, otherwise
the cycle is said to be clean.
The cycles of R(,) containing only
two dotted edges (and one -edge and one -edge)
are called 2-cycles and are said to be inversion-sorted.
Longer cycles are inversion-unsorted and have to be reduced, by applying
inversions, to 2-cycles. This
procedure is called inversion-sorting of  into : when the relational diagram of  and  is composed exclusively of 2-cycles, the markers from ≫ appear exactly in the same relative order and relative orientations in   and  <cit.>.

By walking through each cycle of the relational diagram, arbitrarily in one of
the two possible directions, we assign an orientation to each -edge and to each
-edge. 
We represent the labels according to the assigned direction instead of taking a simple left-to-right orientation
for each edge, in order to avoid any ambiguity.
Figure <ref> shows a relational diagram of two chromosomes  and .













  §.§.§ Bad and good cycles, bad and good components




The relative orientations of -edges and -edges within one cycle
are useful for classifying different types of inversions.
In the following, without loss of
generality, we will refer to operations applied to -edges of R(,), but
a symmetric analysis could be done using -edges.
Given an inversion ρ, the inversion cost of ρ, denoted by
ρ, depends on the effect of ρ on the number of cycles in R(,) as
follows <cit.>:

  
  * a split inversion ρ has ρ=0: it is  applied to two -edges that are in the same cycle and have opposite relative orientations, splitting the original cycle into two (increasing the number of cycles in R(,) by one);
  
  
  * a neutral inversion ρ has ρ=1: it is applied to two 
-edges that are in the same cycle with the same relative orientation,
changing the internal organization of the original cycle without splitting it;
 
  
  * a joint inversion ρ has ρ=2: it is applied to -edges from two distinct
  cycles C_1 and C_2, joining C_1 and C_2 into one cycle
  (decreasing the number of cycles in R(,) by one).
  


If a cycle C does not have a pair of -edges with opposite orientations, it cannot be split by any inversion applied to its -edges and is
called a bad cycle. Otherwise the cycle C is said to be good.
Two distinct cycles C and C' are said to be interleaving when in the relational
diagram there is at least one -edge of C between two -edges of C'
and at least one -edge of C' between two -edges of C.
An interleaving path connecting two cycles C and C' is
defined as a sequence of cycles C_1,C_2,…,C_k such that C_1=C,
C_k=C' and C_i and C_i+1 are interleaving for all i, 1≤ i<k.
An interleaving component or simply component is then
a maximal set of cycles  where each C ∈ is connected
by an interleaving path to any other C' ∈.

Components can be of three types. The first type is a 2-cycle, that can never interleave with any other
cycle and is called a trivial component. The other two types are
components of inversion-unsorted cycles. 
A non-trivial component that contains at least one good cycle can be sorted with split inversions and is called a good component, otherwise it is called a bad component <cit.>.
The relational diagram represented in Figure <ref> has six
components:
one good (the cycle C_2), two trivial (the cycles C_4 and C_7) and three bad
(each of the cycles C_1 and C_3 and interleaving cycles C_5 and C_6).
Let (,) be the minimum number of inversions required to transform
R(,) into a collection of inversion-sorted 2-cycles.  
It is well known that when R(,) has no bad components, this transformation can be done by applying
split inversions only <cit.>. Since the maximum number of cycles in R(,) is equal
to |≫|, we have:

 For two
circular chromosomes  and , such that R(,) has no bad
component, (,)=|≫|-c, where c is the number of cycles in R(,).




  §.§.§ Runs, indel-potential and inversion-indel distance lower bound


Given two
chromosomes  and  and a cycle C of R(,), a run is a
maximal subpath of C, in which the first and the last edges are
labeled and all labeled edges belong to the same
chromosome <cit.>. A run with labels in chromosome  is also called
an å-run, and a run with labels in chromosome  is called a -run. Observe that, since we start counting runs in any border between an å- and a -run, a cycle can have either 0, or 1, or an
even number of runs. We
denote by (C) the number of runs in cycle C. 
As an example, note that the cycle C_1 represented in Figure <ref> has 2 runs
({atj,ji,iuk} is an å-run, while {ky̅j,jb, b wa} is a -run).
While doing the inversion-sorting of good components with split inversions
only, an entire run can be accumulated into a single edge of the relational
diagram <cit.>. The number (C) is then an upper bound for the contribution of cycle C in the final number of indels obtained while doing the inversion-sorting of R(,) with split inversions only. The exact value of this contribution is the indel-potential of a cycle C, that is denoted by (C) and can be directly derived from (C) as follows:


Given two circular chromosomes  and , the
indel-potential of a cycle C of R(,) is given by


    (C) = 
    (C) ,     , 
    (C)/2+1 ,     .
 


Let _0 and _1 be,
respectively, the sum of the indel-potentials for the components of the
relational diagram before and after an inversion ρ.
The indel-cost of ρ is then Δ(ρ) = _1
- _0, and the inversion-indel cost of ρ is defined as
Δ d(ρ) = ρ + Δ(ρ).
If R(,) has good cycles, it is always possible to find a split
inversion ρ such that ρ does not increase the overall
indel-potential of R(,), that is, Δ(ρ)=0 and, consequently, Δ
d(ρ)=0 <cit.>.
Moreover, it has been shown that using neutral or joint inversions one can never achieve Δ d < 0. Therefore, we have the following result:
 

Given two circular
chromosomes  and , such that R(,) has c cycles and no bad component, we
have 
    (,) = |≫| - c + ∑_C ∈ R(,)(C).





§ HANDLING BAD COMPONENTS WITH THE TAGGED COMPONENT TREE


When R(,) has bad components, it requires additional neutral and joint inversions to be sorted. Therefore, in this case the formula given in Theorem <ref> is only a lower bound for the inversion-indel distance.
Denoting by (,) the extra cost
of optimally combining neutral and joint inversions to sort the bad components of
R(,) and given that c is the number of cycles in R(,), we can express the complete formula for the inversion-indel distance as:


    (,) = |≫| - c +
    ∑_C ∈ R(,)(C) + (,).
 



 §.§ Neutral and joint inversions sort bad components

For computing (,) it is necessary to examine the possible values
of the inversion-indel cost Δ d for neutral and joint inversions.
In the remainder of this section we will recall results
from <cit.>, explaining the approach of
sorting bad components with neutral and joint inversions that minimize indels.
Before that, we need to introduce the following notation.
A cycle with no run is represented by .
A cycle with exactly one
å-run (respectively one -run) is represented by _ (respectively _).
Similarly, a cycle with 2i runs is represented by _^ i.

For simplicity, we
denote _^ 1 by _.



  §.§.§ Neutral inversions cut bad components


Let  be a bad component and let C be any (bad) cycle in .
A neutral inversion, applied to C, turns  into a good
component <cit.>.
This type of inversion is said to be a cut of the bad component.
If R(,) has a bad cycle of type _^ i with i≥ 2, it is always 
possible to apply a neutral inversion ρ such that we obtain a good cycle of
type _^ i-1. In other words, two å-runs and two
-runs are merged by ρ, implying Δ(ρ)=-1
and, consequently, Δ d(ρ)=0.
For all other types of bad cycles, it is not possible to decrease
the overall indel-potential with neutral inversions <cit.>.


Since it is always possible to apply a costless neutral
inversion on a cycle of type _^ i with i ≥ 2,
we can assume that R(,) has no cycle of this type, that is, we can assume that any cycle in
R(,) has at most 2 runs. In this setting, the most efficient way to cut a
bad component is by applying a neutral inversion ρ with Δ d(ρ)= 1.




  §.§.§ Joint inversions merge bad components


Let ρ be a joint inversion applied to two distinct cycles C_1 and C_2,
resulting in a single cycle C. Observe that the cycle C is always good, even
when both C_1 and C_2 are bad. 
Moreover, if C_1 and C_2 belong to two distinct components _1 and
_2, these components are merged
into a single good component  that contains the good cycle C <cit.>.
Actually, an inversion ρ has the potential of merging even more than two components at
once, as we will describe in the following.
Without loss of generality, let us assume that, if R(,) has at least two components,
the first and the last -edges of R(,) belong to two distinct
components.






Let _1, _2 and _3 be three distinct components in R(,) such that
if we take the rightmost -edge of _1 and look at the following
-edges one by one, we find an edge of _3 before finding an edge
of _2.
In the same way, if we take the rightmost -edge of _2 and look at the
following -edges one by one, we find an edge of _3 before
finding an edge of _1.
The component _3 is then said to separate _1 and _2.
(In Figure <ref> the good component {C_1} separates the good component {C_2}, the bad component {C_3} and the trivial component {C_4} from the bad component {C_5,C_6} and the trivial component {C_7}.
Similarly, the bad component {C_5,C_6} separates {C_7} from {C_1}, {C_2}, {C_3} and {C_4}.)
By joining with an inversion ρ two cycles C_1 and C_2, that belong
to two distinct components _1 and _2 respectively, we merge not only
the components _1 and _2, but also all components that separate _1 and _2, into a single component .
Even when all merged components are bad, the new component  is always
good <cit.>.
A joint inversion can then be used to merge two or more bad components.
Recall that any joint inversion ρ has ρ=2, therefore Δ d(ρ) = 2
+ Δ(ρ).
Table <ref> enumerates the inversion-indel costs of the
different types of joint inversions.




Since it is always possible to apply a costless joint
inversion on two cycles of type _^ i, we assume that
R(,) has at most one cycle of this type and that any joint inversion
ρ merging components of R(,) has Δ d(ρ) ∈{1,2}.


Observations <ref>
and <ref> imply that we can assume that
R(,) has at most one cycle of type
_å and no cycle of type _å^ i with i ≥ 2. This assures that a cut of a
bad component costs always 1 and that merging bad components costs either 1 or 2.



 §.§ Tagged component tree


The component separation described above can be identified by an alternative structure, that represents the chaining and nesting relationships of the components and helps us to find the best way of cutting and merging bad components of
R(,). 



  §.§.§ Chained tagged component tree


Let a chain be a sequence of components _1, _2, ..., _n for which the rightmost -edge of _i is succeeded by the leftmost -edge of _i+1, for 1 ≤ i < n. A chain is maximal when it cannot be extended to the left nor to the right.
A maximal chain  is nested in a component  when the leftmost -edge of  is preceded by an -edge of  and the rightmost -edge of  is succeeded by an -edge of .

We can then build the chained tagged component tree (,) as follows <cit.>:



  * Each component  from R(,) is represented by a round node v. If  is a bad component, then v is a bad node, drawn
in white. Otherwise v is a good node, drawn in black. A
good node can represent a trivial or a good component. Each round node v has a tag set (v), initially empty, that can receive at most two tags:
(i) the tag 

is added to (v) if at least one cycle of the component  has an
å-run; and (ii) the tag 

is added to (v) if at least one cycle of  has a -run.


  * Each maximal chain is represented
  by a square node whose children are the round nodes
  that represent the components of this chain. A square node is either the root
  or a child of the 
  component in which this chain is nested.



The chained tagged component tree (,) is the same component tree as introduced in <cit.>, except that here we add the tag sets. This tree has the following important property.
Let P be a path connecting two distinct round nodes u_1 and u_2 in (,). The round nodes in P \{u_1, u_2} correspond exactly to the components that separate u_1 and u_2 in R(,).



  §.§.§ Max-flower contraction


Let a max-flower of a chained tagged component tree be a maximal connected subgraph composed of good and/or square nodes only. Suppose we have a max-flower f of a chained tagged component tree T. The contraction of f in T consists of two steps: 


  * Replace f by a
single good round node g, such that g is connected to all bad nodes connected to
f and (g) is the union of tag sets of all nodes from f (assuming that square nodes have empty tag sets);  

  * If g has an empty tag set and exactly two neighbors b_1 and b_2, g is removed from the tree and b_1 is directly connected to b_2; otherwise, if g is a leaf and b is the bad node connected to g, the tag set (g) is added to (b) and g is removed from the tree.

After repeating this procedure for all (disjoint) max-flowers we obtain an unrooted tagged component tree T', that is said to be flower-contracted, that is, the tree T' has no square nodes, no good leaves, no good nodes of degree 2 with an empty tag set, and each remaining max-flower of T' corresponds to a single good node.
As we will see in the next subsection, the computation of (,) is derived from the analysis of an unrooted tagged component tree that is exactly the flower-contracted version of the chained tagged component tree (,) and is denoted by (,). See examples of its construction in Figure <ref>. 










 §.§ Cover and optimal cover


The diagram R(,) can have any number of good and bad cycles of types
, _å and _. Due to Observations <ref>
and <ref>, we assume that R(,) has at most one cycle of type
_å and no cycle of type _å^ i with i ≥ 2. Therefore, the cost of cutting a component is always one, independently of
the number of tags of the corresponding node in (,) and –
even if a node of (,) has both tags – at most one of them can be
“used” in each joint inversion merging components, that costs either 1 or 2.

Similar to <cit.>, in our analysis we focus on paths covering the bad nodes of (,). 
We denote by τ(P) the cost of a path P, that can be of two types. 
The path P is short if it contains a single bad node. It corresponds to the cut of the component represented by its bad node and has therefore cost τ(P)=1.
On the other hand, the path P is long if it contains at least two bad nodes. It
corresponds to the merging of all components represented by its nodes, by a
joint inversion applied to two cycles, each of the two belonging to one of the
two endpoints of the path.
The cost of P is therefore either τ(P)=1, if its endpoints share at least
one tag (indel-saving path), or τ(P)=2 otherwise
(indel-neutral path).



A cover of (,) is defined as a
set of paths  such that each bad
node of (,) is contained in at least one path P ∈.
The cost of  is given by τ()=∑_P ∈τ(P). 
If τ() is minimum,  is 
an optimal cover and
τ()=τ((,))=(,) <cit.>.


The reason behind contracting the tree to get one with the minimum number of good nodes and whose leaves are bad nodes is  simply to get a more compact tree, while preserving the same bad nodes and tags of the original tree. In other words, since the flower-contractions preserve in (,) all the tags from (,) in the same relative positions with respect to the bad nodes, we have τ((,)) = τ((,)).




  §.§.§ Covering a tree with traversals


Given a tree T with ℓ leaves, a leaf-branch of T is: (i) either the complete tree T, if ℓ≤ 2; (ii) or, if ℓ≥ 3, 

a maximal path u_1,u_2,…,u_k,

such that u_1 is a leaf of T and, for i=2,…,k, the degree of internal node u_i in T is two. 
The second case includes a leaf-branch consisting of a leaf only, if that is directly connected to a branching node of T.


A path P whose both endpoints are leaves is called a traversal.
Observe that, if ℓ≥ 2 is the number of leaves of a tagged component tree (,), the minimum number of traversals required to cover all ℓ leaves is ⌈ℓ/2⌉. 

Indeed, any unrooted tree with at least two leaves can be completely covered with this minimum number of traversals. If the number of leaves ℓ is even, the traversals can be obtained with a very simple procedure (Algorithm <ref>, from <cit.>). If ℓ is odd, it is necessary to remove one leaf-branch from the tree, run Algorithm <ref> and add one extra traversal connecting the removed leaf-branch and any other leaf.




The fact that Algorithm <ref> covers the complete tree proves the following theorem.

 
Given a tree T with 2n leaves, it is always possible to find a vertex v in T, such that there is a cover of T composed of n traversals, all of whom containing the vertex v. Such a vertex is called a balanced vertex of T.

[Proof given in <cit.>]
Considering any two paths in the set returned by Algorithm <ref>, their endpoints alternate along the circle which contains the leaves in increasing order. Therefore these two paths clearly intersect each other. If in a tree a set of paths does not contain two disjoint paths, then all the paths share a common vertex v (a proof is given in <cit.>). And because these paths connect v to the leaves, they cover all edges of the tree.







































 




  §.§.§ The simplest instances give a lower and an upper bound


A node of the tagged component tree (,) whose tag set is empty is called clean, otherwise it is tagged.


We will now give solutions for the simplest instances of the problem of computing the cost (,) of an optimal cover of (,), that are: (i) the case in which all leaves are tagged and share at least one tag and (ii) the case in which all leaves are clean. These two cases correspond, respectively, to tight lower and upper bounds for (,) and are based on optimal covers composed of traversals and at most one short path. 


Let all ℓ≥2 leaves of a tagged component tree (,) share at least one tag. The cost of any optimal cover of (,) is (,)=⌈ℓ/2⌉.


Any traversal is indel-saving (costs 1) because the leaves of (,) share a tag.
As we have already explained before, with Algorithm <ref> we can find ⌈ℓ/2⌉ traversals covering (,) completely.













When the tree has clean leaves, the length of the leaf-branches can influence the cost of an optimal cover.
A leaf-branch of the tree (,) is long if it contains at least two bad nodes, otherwise it is short. 


Let all ℓ≥ 2 leaves of a tagged component tree (,) be clean. The cost of any optimal cover of (,) is 

    (,) = {[ ℓ+1    ;   ℓ     ].



Any traversal is indel-neutral (costs 2) because the leaves of (,) are clean. 
When ℓ is even, with Algorithm <ref> we can cover the tree with a 
set of ℓ/2 traversals, giving an optimal cost of ℓ in this case.
When ℓ is odd, let S be a short leaf-branch of (,), if there is any, otherwise any of the long leaf-branches.
The subtree obtained from (,) by removing the leaf-branch S can be covered by a 
set of ℓ-1/2 traversals obtained wit Algorithm <ref>.
Then, if S is a short leaf-branch, it can be covered by a short path, giving an optimal cost of ℓ - 1 + 1 = ℓ.
Otherwise, S is a long leaf-branch and we have the classical situation of a “fortress” <cit.>, in which S can only be covered by a long path with cost 2, resulting in the optimal cost of ℓ-1 + 2 = ℓ+1.


    










§ OBTAINING AN OPTIMAL COVER OF TREES WITH AT LEAST TWO LEAVES THAT SHARE NO TAG


In this section we will 
describe our approach of finding an optimal
cover of all intermediate and more intrincate instances of the tagged component tree. 

Given a path
P, a P-reduction -P(,) of (,) results in a smaller
tagged component tree as follows.
Let T' be the tagged tree obtained from (,) by replacing each bad node b of P by a good node g, such that (g)=(b).
Then -P(,) is the flower-contracted version of
T'. A P-reduction is said to be safe if  τ((,))=τ(-P(,)) + τ(P), otherwise it is unsafe.
We will build optimal covers by first “simplifying” the tagged component tree with safe reductions.

From now on we will denote the three possible non-empty tag sets {},
{} and {,}, respectively, simply by ,  and .
We can then refer to
-, -, - or -nodes or -leaves, depending on the respective set of tags.
Tagged component trees and their optimal covers will be shown in figures with the following notation: 



  * Leaves will be usually labeled as described: (i) a, a_1, a_2, etc., will be labels of -leaves; (ii) b, b_1, b_2, etc., will be labels of -leaves; (iii) x, x_1, x_2, etc., will be labels of -leaves; and (iv) s is the label of the solo leaf (defined in Section <ref>), while c, c_1, c_2, etc., will be labels of other clean leaves.


  * In the given optimal covers, 
traversals will be represented by the symbol , semi-traversals (defined in Section <ref>) will be represented by the symbol  and the dots above these symbols will indicate the cost of each path.








 §.§ Properties of tagged component tree topologies and their covers


We need to describe the possible topologies of tagged component trees in order to devise our approach of simplifying the tree and finding optimal covers.



  §.§.§ Subtrees and partition subtrees

    Let 𝒩 be a set of nodes of (,). Then 𝒩 denotes the subtree induced by 𝒩, i. e., the smallest connected subtree of
    (,) containing all the nodes from 𝒩. 
    The leaves of (,) can be partitioned into four disjoint classes
    , ,  and , that are, respectively,
    the sets of -leaves, -leaves, -leaves and -leaves of (,).
    A partition subtree is then a subtree ℒ where ℒ is the union of one to four leaf classes.
    In general, the topology and connections between the possible partition subtrees
  drive our approach of finding an optimal cover for the tree (,).
    The four partition subtrees
    , , 
     and  are called canonical subtrees of (,). While canonical subtree  is said to be clean, subtrees ,  and  are said to be tagged.
 
    

    


    
   

  §.§.§ Complementary subtree
  
    Let ℒ be a partition subtree. 
    The complementary subtree of 
    ℒ, denoted by ℒ, is the partition
    subtree ℒ', where ℒ' is the set composed of all leaves of (,) except those from
    ℒ. 
    Complementary subtree is a reciprocal concept, thus ℒ' is the subtree ℒ itself.
    For example, considering the canonical subtree , its complementary subtree is =∪∪.
    Another example is the partition subtree ∪, whose complementary subtree is ∪=∪. 
    Note that ℒ and (,)\ℒ can be distinct and, while the first is necessarily a tree, the second can be a forest.

   

  §.§.§ Links and bad links

   
     If ℒ_1 and ℒ_2 are two non-empty and disjoint partition subtrees, there is exactly one path connecting ℒ_1 to
    ℒ_2 in (,).
    This path is called the link between ℒ_1 and
    ℒ_2. A link is a bad link when it contains at
    least one bad node, otherwise it is a good link.
    
    
    
    
    A bad link that
    contains two or more bad nodes is called long bad link.
    Otherwise, if it contains a single bad node, it is called short bad
    link. 
    
    
    
   

  §.§.§ Co-rooted and separated partition subtrees

    
    Two non-empty partition subtrees ℒ_1 and ℒ_2 are said to be separated when they are
    disjoint and connected by a bad link. Otherwise, they are co-rooted.
    A partition subtree ℒ is said to be
    isolated if it is separated from its complementary subtree ℒ, and 
    non-isolated if it is co-rooted with its complementary subtree ℒ. 
    If each canonical subtree is non-isolated and, in addition, the partition subtree ∪ is non-isolated, then (,) is said to be fully
    co-rooted.
    At the other extreme, if each canonical subtree L is isolated and, in addition, for a tree with four leaf types, either the subtree ∪, or the subtree ∪, or the subtree ∪ is isolated, then (,) is said
    to be fully separated. Examples of various topologies are given in Figure <ref>.
    
        





















  §.§.§ In-, out- and semi-traversals
      
    Let u_1 and u_2 be two leaves of (,). 
If both u_1 and u_2 are in the same canonical subtree L, the traversal between u_1 and u_2 is said to be an in-traversal (of the canonical
subtree L). 
On the other hand, if u_1 and u_2 are in distinct canonical subtrees L_1 and L_2, the traversal between u_1 and u_2 is said to be an out-traversal (between the
canonical subtrees L_1 and L_2). Note that in-traversals of tagged canonical subtrees are indel-saving (cost 1), while in-traversals of the clean canonical subtree are indel-neutral (cost 2). Out-traversals are usually indel-neutral, except in the case of one subtree being  and the other subtree being either  or , when they are indel-saving. 

Now let u_1 be a leaf of a canonical subtree L and u_2 be an internal node of (,) that is not in L. The path connecting u_1 and u_2 is called a semi-traversal, that can be indel-saving or indel-neutral depending on whether u_1 and u_2 share a tag or not.






  §.§.§ Tag mates


Let a tagged canonical subtree L be separated from a partition subtree ℒ by a bad link P. 
As we explain in the following, the bad link P can be possibly covered by an

indel-saving out-traversal or by an indel-saving semi-traversal.





First suppose that at least one leaf of the subtree ℒ shares a tag with the leaves of L.

In this case, the bad link P can be
covered by an indel-saving out-traversal P' (with τ(P')=1) and we say that subtree ℒ contains a trivial tag mate of L.

An example of trivial -mate is given in Figure <ref> (i).

	
Now suppose that subtree ℒ has no trivial tag mate of L.



In this case ℒ might have some internal node that shares a tag with the leaves of L, 
therefore it can still be possible to cover the bad link P by an indel-saving semi-traversal.
More precisely, let the extended subtree ℒ be ℒ∪{p}, where p is the bad node of the bad link P that is closest to ℒ.
If the tag set of at least one node m of ℒ shares a tag with the leaves of L, the node m is said to be a non-trivial tag mate of L at ℒ.
The fact that ℒ contains a non-trivial tag mate of L is denoted by ℒℒ, where  is either the tag  or the tag . Examples of non-trivial tag mates are
∪ and
∪, the latter shown in Figure <ref> (ii)-(iii).

Observe that, if ℒ includes the class , it is unnecessary to verify whether the extended subtree ℒ contains a non-trivial tag mate, because in this case it obviously contains a trivial one.






	






 §.§ Procedure of computing an optimal cover


For any canonical subtree L, the cost of an in-traversal of L is at most the same as the cost of an out-traversal between L and any other canonical subtree. This suggests an approach of searching optimal covers maximizing in-traversals. 
We need to be careful, however, and also allow out-traversals for covering bad links and possibly unpaired leaves. 













Given a tree (,) with at least two types of leaves that share no tag, 

we will search for an optimal cover with a three-step procedure.

The first step consists of determining whether the solo leaf exists: it is a leaf of the clean subtree that must be kept by any reduction.
The second step consists of safely reducing the sizes of the four subtrees ,
,  and  of (,) with 
in-traversals,

until we reach a certain minimum number of leaves per canonical subtree, obtaining a residual tree. The third step is then finding an optimal cover of the residual tree,
that requires a lengthy enumeration of all possible cases.




  §.§.§ Solo leaf


When reducing the clean subtree, we need to be careful with a particularity of the topology that can influence the cost of an optimal cover. 
Let the tree (,) with at least three leaves have a clean leaf s in a short leaf-branch and let -s(,) be the tree obtained by pruning s and performing a flower-contraction in (,). Obviously, the tree -s(,) has exactly one leaf less than (,). If
τ((,))=τ(-s(,)) + 1, then s is said to be a solo leaf. In other words, the clean leaf s is a solo leaf if 
there is some optimal cover of (,) that includes a short path covering s. See examples in Figure <ref> (i) and (ii).



The solo leaf is the last leaf to be paired when we search for an optimal cover of (,). 

In some sense, it represents the absence of a “fortress” <cit.>: if, instead, the last unpaired clean leaf would not be a solo leaf but part of a long leaf-branch, it could only be covered together with its branch by an indel-neutral path, whose cost is 2.


In contrast to clean leaves in short leaf-branches of (,), tagged leaves in short leaf-branches need no special treatment

for the following reasons:


  * If originally a tagged canonical subtree is composed of a single leaf, it is indeed important to identify whether its leaf is in a long or in a short leaf-branch, since the latter allows it to be covered by a short path. But
the single leaf being in a short leaf-branch is equivalent to the corresponding subtree being non-isolated, a condition that can be easily verified.

  * If a tagged canonical subtree L has at least two leaves,

there is no advantage of any leaf being in a short leaf-branch: in this case it could possibly be covered by a short path, but if it would be in a long leaf-branch, the whole branch could be covered by an indel-saving path, whose cost is the same as that of a short path.

The difference between keeping a clean leaf or a  tagged leaf in a short leaf-branch is illustrated in Figure <ref>.


 
 
 
 
 
 





A tagged component tree (,) can have more than one clean short leaf-branch, but in our approach at most one is covered by a short path: even if some optimal cover includes two short paths covering two clean short leaf-branches, there is another optimal cover with the same cost covering the two leaf-branches by an in-traversal of . Therefore, if the tree has clean short leaf-branches, it suffices to characterize at most one as solo leaf.


However, even if (,) has a single clean short leaf-branch, the leaf of this branch is not necessarily a solo leaf, as shown in Figure <ref> (iii). Actually the procedure of searching for a solo leaf is quite tricky and depends on various aspects of the distinct topologies of a tagged component tree. The only approach we could devise so far tests all possible hypotheses (each clean short leaf-branch of (,) as the possible solo leaf) and takes one that results in the smallest cover cost. This exhaustive search dominates the complexity of our whole procedure for computing the distance, as we will demonstrate in Section <ref>.




  §.§.§ Reducing tagged component trees with balanced in-traversals



Given a canonical subtree L with |L| ≥ 4, a balanced in-traversal of L is defined as follows:


  * If |L| is even, any traversal from the set returned by Algorithm <ref> is a balanced in-traversal.

  * If |L| is odd, let P be any leaf-branch of L. A balanced in-traversal of L is a balanced in-traversal of L\ P.



Let a path P be an in-traversal of some canonical subtree L. The corresponding P-reduction costs 2 if L= and 1 otherwise. It is called a balanced reduction if P is a balanced in-traversal.

And it is said to be preserving if -P(,) and (,) have the same topology with respect to
partition subtrees, bad links and solo leaf,

and if in -P(,) subtree L has exactly two leaves less than in (,). 


Let L be a tagged canonical subtree of (,) with |L| ≥ 4. Any balanced P-reduction of L is preserving.


Since the in-traversal P is balanced, it “crosses” the subtree L. This guarantees that the P-reduction does not create a new bad leaf, nor a new bad link, nor it increases the length of any remaining leaf-branch.  Furthermore, the flower-contraction after the reduction preserves all tags, therefore we do not lose any tag mate. 

 






For any tagged component tree (,) with || ≥ 4, a preserving P-reduction of  is any balanced P-reduction such that, if (,) has a solo leaf s, P does not cover s. Such a reduction is called solo-safe reduction. If (,) has no solo leaf, any balanced reduction of  is a solo-safe reduction.


Here we can repeat the arguments of the proof of Lemma <ref>. Furthermore, since P does not cover the solo leaf, we do not lose it.


 







A preserving balanced reduction is very often safe. Indeed, a solo-safe reduction of  down to two leaves is always safe. The same is true for any
balanced reduction of tagged canonical subtrees  and  down to two leaves and for any
balanced reduction of tagged canonical subtree  down to three leaves. Actually, only in some particular cases a balanced reduction of  from four to two leaves is unsafe. These facts will be demonstrated by the Reduction Bounds stated later in this section. We will also demonstrate that, although a canonical subtree  L with only three leaves has no balanced in-traversal, a reduction 


to a single leaf can be safe, even if it is non-preserving (as we showed in Figure <ref>). 


We can now analyse the topologies of each type of tagged component tree and set the lower bounds for safe reductions in each canonical subtree. Since a reduction removes two leaves from the tree, for each case analysis we need to consider whether the number of leaves in the canonical subtree being reduced is even or odd. We start by setting the bounds for canonical subtrees  and :


Each of the canonical subtrees  and  can be safely reduced to one or two leaves in any tagged component tree.


Without loss of generality, we will do the case analsis considering only .
First suppose we have a tagged component tree with two non-empty canonical subtrees  and L. Then suppose  has three leaves and all of them are endpoints of out-traversals to canonical subtree L. In this case we could replace two out-traversals between  and L by an in-traversal of  and an in-traversal of L. Note that L can be either  or , but in both cases this replacement would lead to a smaller cost than the original traversals.
Now suppose we have a tagged component tree with three non-empty canonical subtrees , L_1 and L_2. Then suppose  has three leaves and two of them are endpoints of out-traversals to canonical subtree L_1, while the third leaf of  is endpoint of an out-traversal to canonical subtree L_2. In this case we could replace an out-traversal between  and L_1 and the out-traversal between  and L_2 by an in-traversal of  and an out-traversal between L_1 and L_2. By assigning the possible canonical subtrees to L_1 and L_2, one can verify that this replacement would lead to at most the same cost as the original traversals. (A similar analysis can be done for the case in which the tagged component tree has four non-empty canonical subtrees.) Clearly, if a reduction from 3 to 1 is possible, then a reduction from 4 to 2 is also possible.





In Appendix 1.






Let ℓ_t be the number of leaves in canonical subtree L_t. 
The leaf composition of the tree (,) is given by the values , ,   and .

Due to the symmetry of costs for -nodes and for -nodes in covering paths, we assume without loss of generality that after the reduction we obtain a residual tree in which ≥. To achieve this, if  is non-empty and if  is either empty or has an odd number of leaves, we can simply “swap” -nodes and -nodes. Now, for each type of tagged component tree, the bounds of 
each canonical subtree

will be defined in the five Reduction Bounds listed below and whose proofs are given in Appendix 1.









Two non-empty canonical subtrees L_1 and L_2 such that L_1 and L_2 share no tag: 
Let ℓ_1=|L_1| and ℓ_2=|L_2|. Without loss of generality, assume that L_1 is tagged. Given that w ∈{1, 2} is the cost of an in-traversal of L_2 (that can be tagged or clean),
the number of leaves in both subtrees L_1 and L_2 can be safely reduced to one or two, with cost
⌊ (ℓ_1 - 1)/2 ⌋ + w⌊ (ℓ_2 - 1)/2 ⌋.

















Three non-empty canonical subtrees , , and :



  * If  and  are odd, and given that n = max{, 2},
the number of leaves in subtrees  and  can be safely reduced to one, and the number of leaves in subtree  can be safely reduced to two or three, with cost 
( - 1)/2 + ( - 1)/2 + 2⌊ (n - 2)/2 ⌋. 

  * Otherwise  is even, the number of leaves in subtree  can be safely reduced to two and the number of leaves in subtrees  and  can be safely reduced to one or two, with cost ( - 2)/2 + ⌊ ( - 1)/2 ⌋ + 2⌊ ( - 1)/2 ⌋.








Three non-empty canonical subtrees , , and :



  * If both  and  are odd, the number of leaves in subtrees  and  can be safely reduced to one and the number of leaves in subtree  can be safely reduced to one or two, with cost 
( - 1)/2 + ( - 1)/2 + ⌊ ( - 1)/2 ⌋. 

  * Otherwise,  is even. If  is odd and given that n = max{, 2}, the number of leaves in subtrees  can be safely reduced to two, the number of leaves in  can be safely reduced to one and the number of leaves in subtree  can be safely reduced to two or three, with cost 
( - 2)/2 + ( - 1)/2 + ⌊ (n - 2)/2 ⌋. 

  * Finally, both  and  are even and n = max{, 3}. The number of leaves in subtrees  and  can be safely reduced to two, and the number of leaves in subtree  can be safely reduced to three or four, with cost 
( - 2)/2 + ( - 2)/2 + ⌊ (n - 3)/2 ⌋.








Three non-empty canonical subtrees , , and :



  * If at least one value among  and  is odd, the number of leaves in each subtree can be safely reduced to one or two, with cost 
⌊ ( - 1)/2 ⌋ + 2⌊ ( - 1)/2 ⌋ + ⌊ ( - 1)/2 ⌋.

  * Otherwise, both  and  are even and n = max{, 2}. Then the number of leaves in subtrees  and  can be safely reduced to two, and the number of leaves in subtree  can be safely reduced to two or three, with cost 
( - 2)/2 + ( - 2) + ⌊ (n - 2)/2 ⌋.








Four non-empty canonical subtrees:



  * If all ,  and  are odd, the number of leaves in subtrees ,  and  can be safely reduced to one, and the number of leaves in subtree  can be safely reduced to one or two, with cost 
( - 1)/2 + ( - 1)/2 + ( - 1) + ⌊ ( - 1)/2 ⌋.

  * Otherwise, if  is odd and among  and  one value is odd and the other is even, we set n = max{, 2}. The number of leaves in subtree  can be safely reduced to one, the number of leaves in subtrees  and  can be safely reduced to one or two, and the number of leaves in subtree 
 can be safely reduced to two or three, with cost 
⌊ ( - 1)/2 ⌋ + ( - 1)/2 + 2⌊ ( - 1)/2 ⌋ + ⌊ (n - 2)/2 ⌋.

  * Finally, if  is even and at least one value among  and  is also even, we set n = max{, 3}.
The number of leaves in subtree  can be safely reduced to two, the number of leaves in subtrees  and  can be safely reduced to one or two, and the number of leaves in subtree 
 can be safely reduced to three or four, with cost 
( - 2)/2 + ⌊ ( - 1)/2 ⌋ + 2⌊ ( - 1)/2 ⌋ + ⌊ (n - 3)/2 ⌋.














Reduction Bounds <ref> to <ref> jointly define an algorithm to find the residual tree of any tagged component tree (Algorithm <ref> in Appendix 1). Once we have the resulting residual tagged component tree (see an example of an execution of Reduction Bound <ref> - case 2 - in   Figure <ref>), its optimal cover can be obtained from the lengthy enumeration of all possible residual trees, given in the remainder of this section.   








  §.§.§ Covering all residual trees


A residual leaf composition can be represented by a quadruple  of four non-negative values that always has  in the first position,  in the second position,  in the third position and  in the fourth position.
Recall that, due to the symmetry of costs for -nodes and for -nodes in
covering paths, we assume without loss of generality that ≥.
According to the results presented so far, we have 56 residual leaf compositions distributed in three groups.






Group 1: Residual trees with exactly two non-empty canonical subtrees L_1 and L_2, such that the tag sets of the classes L_1 and L_2 share no tag, defined in Reduction Bound <ref>. 






This group includes 11 residual leaf compositions listed in Table <ref>. The complete enumeration is given in Appendix 2.
As an example of Group 1, we give the topologies and respective optimal covers of leaf composition 2200 in Figure <ref>.




	
	







Group 2: Residual trees with exactly three non-empty canonical subtrees, 
forming three subgroups, defined by Reduction Bounds <ref> to <ref>.


















This group includes 25 residual leaf compositions listed in Table <ref>. The complete enumeration is given in Appendix 2.
In particular, in this group we have the residual leaf composition 1130 (Reduction Bound <ref>, first case) and also residual leaf compositions with three or four leaves in subtree  (cases of Reduction Bounds <ref> and <ref>).
Some topologies of these leaf compositions can be further reduced by an extra in-traversal and are then said to be reducible.
As an example of Group 2, we give the topologies and respective optimal covers of leaf composition 1130 and its 
reduction 1110 in Figure <ref>.










Group 3: Residual trees with four non-empty canonical subtrees, defined by Reduction Bound <ref>, whose cases 2 and 3 include residual leaf compositions with three or four leaves in subtree , containing reducible topologies.






In total, this group includes 20 residual leaf compositions listed in Table <ref>. The complete enumeration is given in Appendix 2.
As an example, we consider the leaf composition 2223. The non-reducible topologies and respective optimal covers are shown in Figure <ref>, and the ones reducible to 2221 are shown in Figure <ref>, both in Appendix 2.





  §.§.§ Proof of correctness and complexity


The correctness of our approach is a consequence of the correctness of Reduction Bounds <ref> to <ref> and the enumeration of all possible residual trees, as stated in the following theorem.




Given a tagged component tree (,), let τ be the sum of the cost of applying the appropriate Reduction Bound (among <ref>-<ref>) to (,) and the cost of covering the obtained residual tree R(,), that can be found in the full enumeration (in Appendix 2). The value τ is optimal, that is, τ = (,).


Reduction Bounds <ref> to <ref> (whose proofs are given in 

Appendix 1) give the number of safe balanced in-traversals that we can use to reduce each canonical subtree. For the residual trees, the exhaustive enumeration of all topologies guarantees that we can always find an optimal cover.


The following considerations show that the topology description that we consider contains all necessary properties to the search of optimal covers.

Since the cost of an in-traversal of  canonical subtree L is at most the same as the cost of an out-traversal between L and any other canonical subtree, in the absence of bad links and if each canonical subtree has an even number of leaves, it is clear that with in-traversals only we cover the tree optimally. 

Otherwise, bad links, tag mates and solo leaf are sufficient properties to drive our search for optimal covers:


  * Note that, if long bad links exist, one can find an optimal cover by attempting to cover them by only three types of paths: (1) indel-saving out-traversals, (2) indel-saving semi-traversals (with tag mates) and (3) indel-neutral out-traversals. (Another possibility would be to have bridges, that are paths connecting two internal nodes. Indeed, an optimal cover can contain a bridge, but in this case there is always an alternative optimal cover composed of traversals, semi-traversals and at most one short path - see Proposition <ref> 
in Appendix 1.)
Therefore, besides the leaves, tag mates are the only nodes we have to consider to cover bad links.

  * As explained in Section <ref>, if there are unpaired leaves, only in the clean subtree we need to be careful and keep the solo leaf, that is in a short leaf-branch of (,), to be the last leaf to be paired. For tagged leaves, it makes no difference whether the leaf is in a short or in a long leaf-branch, unless originally the corresponding subtree is composed of a single leaf (in this case, the leaf being in a short leaf-branch is equivalent to the corresponding subtree being non-isolated, a condition that is considered when we enumerate the covers of all possible residual trees).












With respect to the complexity, the critical point is finding solo-safe reductions of the clean subtree, which results in a quadratic procedure.


The time and space complexity of our procedure of computing the inversion-indel distance is quadratic in the number of markers |≫|+|å|+||.




In Appendix 1.




§ CONCLUSION


In this work we have completed the study of the inversion-indel distance 
between two chromosomes  and  with unequal contents, by
presenting an approach to compute the extra cost (,)
of sorting bad components of the relational diagram R(,).
We gave easy-to-compute lower and upper bounds. For the intermediate instances, our approach
is based on the composition of several properties of tagged component trees and the enumeration of optimal covers of a long list of minimal residual trees that can be obtained by reducing them.  
The whole procedure can be done in quadratic time and space on the number of markers |≫|+|å|+||.


In future work, it seems now possible to address the more general problem of computing the multichromosomal genomic distance <cit.> with insertions and deletions using techniques similar to those used in this paper combined with the more general component tree presented in <cit.>.

IEEEtran







#1

1.25







§ APPENDIX 1: OMITTED PROOFS AND ALGORITHMS











  




 §.§ Proofs





























The bounds given by Proposition <ref> and Reduction Bounds <ref> to <ref> were set assuming the worst case of fully separated trees.
The reason is that,
if a fully separated tree T_1 and non fully separated tree T_2 have the same number of leaves per canonical subtree, in T_1 we might need to keep more leaves for covering bad links. In other words, if, together with the reduction, some amount of remaining leaves is enough for giving an optimal cover of T_1, the same number is clearly enough for giving an optimal cover of T_2.






Proposition <ref>:






Reduction Bound <ref>:

Two leaves from each canonical subtree are sufficient to cover the possible bad link between them and compensate an unpaired leaf from the other subtree. 
It is then clear that, if ℓ_1 ≥ 4 (respect. ℓ_2 ≥ 4), it can be reduced to 2 or 3 by preserving reductions (Lemma <ref>) that are safe. 
The question now is whether ℓ_1 and/or ℓ_2 can still be reduced from three to one.
If one subtree has only one leaf, it is clear that we can reduce the other from three leaves to one. If both subtrees have three leaves, it is clear that both can be reduced to one leaf. If one subtree has three leaves and the other has two, we have the following possibilities: 

(i) L_1 is either  or  and L_2=: in this case we have one out-traversal to cover the bad link. Suppose we have a cover that contains another out-traversal. This cover would have a cost of five. However, if instead we do an in-traversal in each canonical subtree, we also have a cost of five, therefore this reduction is safe.

(ii) L_1 = and L_2 =: the reduction in this case was proven to be safe by Proposition <ref>.





The following proposition will be used to prove the correctness of Reduction Bounds <ref> to <ref>.





The bad links of a fully separated tagged component tree (,) with three non-empty canonical subtrees L_1, L_2 and L_3 can be covered by two paths, one connecting L_1 and L_2, and the other connecting L_1 and L_3.


 We simply refer to Figure <ref> (ii-b) of the paper. It is clear that if we pick any of the three subtrees, say subtree no. 1, a pair with a path between subtrees 1 and 2 and a path between subtrees 1 and 3 covers all bad links of the tagged component tree.






Reduction Bound <ref>:

Proposition <ref> guarantees that  and  can be safely reduced to one or two leaves. Since all bad links can be covered by two out-traversals (Proposition <ref>), we need to reserve two leaves from  to cover the bad links, and two other leaves from  to possibly compensate unpaired leaves in the other two subtrees, meaning that the number of leaves in  can be safely reduced to four or five. Further reductions depend on the following case analysis. 

Case 1: Note that, if  is odd and  is odd, they can be both reduced to one and we do not need to compensate unpaired leaves. Then the number of leaves in  can be safely reduced to two or three. Let us examine whether we could still reduce from three to one: if both tagged subtrees are isolated and the tree has the solo leaf, such a reduction could either create a new leaf or transform the solo leaf into a leaf in a long leaf-branch, being then unsafe. Therefore in this case the bounds for the clean subtree are two or three.

Case 2: Now let  be even. 

Suppose that we have five leaves in , two leaves in 

and four out-traversals involving . We could then replace, at the same cost, two of these out-traversals by an in-traversal of  and an out-traversal between  and . But then we would have a triangle covering the bad links, therefore we could replace one other out-traversal between  and  by an in-traversal of  (covering its unpaired leaf) and an in-traversal of , at the same cost. (A similar analysis could be done for the case of a single leaf in .) Consequently, if the number of leaves in  is odd, it can be safely reduced to one. Clearly, if the number of leaves in  is even, it can be safely reduced to two.






Reduction Bound <ref>:

Proposition <ref> guarantees that  and  can be safely reduced to one or two leaves. Since all bad links can be covered by two out-traversals (Proposition <ref>), we need to reserve two leaves from  to cover the bad links and two other leaves from  to possibly compensate unpaired leaves in the other two subtrees, meaning that the number of leaves in  can be safely reduced to four or five. Further reductions depend on the following case analysis. 

Case 1: Note that, if  is odd and  is odd, they can be both reduced to one and we do not need to compensate unpaired leaves. Then number of leaves in  can be safely reduced to two or three. But actually we could still reduce from three to one: suppose the unpaired (third) leaf of subtree  is covered by an out-traversal to one of the other two subtrees. At the same cost we could replace it by an in-traversal of . Therefore in this case  can be safely reduced to one or two.

Case 2: Now let  be even, that is reduced to two, and  be odd, that is reduced to one. The number of leaves in  can be then safely reduced to three or four. But actually we could still reduce from four to two: suppose the unpaired (fourth) leaf of subtree  is covered by an out-traversal to one of the other two subtrees. At the same cost we could replace it by an in-traversal of . Therefore in this case  can be safely reduced to two or three.

Case 3: Finally, if  is even and  is even, they can be both reduced to two. The number of leaves in  can be then safely reduced to four or five. But actually we could still reduce from five to three: suppose the unpaired (fifth) leaf of subtree  is covered by an out-traversal to one of the other two subtrees. At the same cost we could replace it by an in-traversal of . Therefore in this case  can be safely reduced to three or four.






Reduction Bound <ref>:
 Proposition <ref> guarantees that  can be safely reduced to one or two leaves. We also know that all bad links can be covered by two out-traversals (Proposition <ref>) and we can always pair  with   and  with one of the other two subtrees. Note that  is a more “powerful” version of , therefore in the following analysis we can often generalize the statements of Reduction Bound <ref>.

Case 1: Suppose  is odd, being reduced to one. 


  * If  is odd and  is odd, by generalizing Reduction Bound <ref> – Case 1, we know that  can be safely reduced to one and  can be safely reduced to three. But, actually, here  can also be reduced from three to one: one leaf is enough to cover the eventual bad link separating  from .

  * If  is odd and  is even, by generalizing Reduction Bound <ref> – Case 2, we know that  can be safely reduced to two and  can be safely reduced to one.

  * If  is even and  is odd, by generalizing Reduction Bound <ref> – Case 2, we know that  can be safely reduced to one and  can be safely reduced to two.


Case 2: Suppose  is even, being reduced to two.


  * If  is odd, by generalizing Reduction Bound <ref> – Case 2, we know that  can be safely reduced to one and the number of leaves in  can be safely reduced to one or two.

  * If  is even, by generalizing Reduction Bound <ref> – Case 2, we know that  can be safely reduced to two.
Then the number of leaves in  can be safely reduced to three or four. But actually we can still reduce it from four to two: suppose we have two out-traversals between subtrees  and  and two out-traversals between subtrees  and . We could then replace one out-traversal between  and  and one out-traversal between  and  by one out-traversal between  and  and one in-traversal of . Therefore in this case  can be safely reduced to two.
 





The following proposition will be used to prove the correctness of Reduction Bound <ref>.





The bad links of a fully separated tagged component tree (,) with four non-empty canonical subtrees L_1, L_2, L_3 and L_4, such that L_1 ∪ L_2 is separated from L_3 ∪ L_4 can be covered by two “crossing” paths, that either connect L_1 to L_3 and L_2 to L_4 or connect  L_1 to L_4 and L_2 to L_3.


 We simply refer to Figure <ref> (ii-c) of the paper. Note that partition subtrees 1 ∪ 3 and 2 ∪ 4 are co-rooted. It is then clear that a pair with a path between subtrees 1 and 3 and a path between subtrees 2 and 4 covers all bad links of the tagged component tree. A second choice also exists, because 1 ∪ 4 and 2 ∪ 3 are also co-rooted. Therefore a pair with a path between subtrees 1 and 4 and a path between subtrees 2 and 3 also covers all bad links of the tagged component tree.







Reduction Bound <ref>:
 Proposition <ref> guarantees that  and  can be safely reduced to one or two leaves. Since a tree with four canonical subtrees is a generalization of case 2 of Reduction Bound <ref>, we also know that  can be safely reduced to one or two leaves. 
Furthermore, all bad links can be covered by two out-traversals (Proposition <ref>).
Therefore we can cover the eventual bad links by pairing  with either  or  and  with either  or .
We now need to examine the bounds for the subtree .

Case 1: Note that, if  is odd,  is odd and  is odd, they can all be reduced to one. Consequently, the number of leaves in  can be safely reduced to one or two.

Case 2: Now let  be odd, that is reduced to one, and let one of  or  be also odd, that is reduced to one, and the other one even, that is reduced to two. In order to cover the unpaired leaf in  or , the number of leaves in  can then be safely reduced to two or three.

Case 3: Finally, we have that  is even and can be safely reduced to two. Furthermore, at least one value among  and  is also even and can be safely reduced to two. 


  * Suppose first that either  or  is odd, being reduced to one. Then the number of leaves in  can be safely reduced to three or four.

  * Now suppose that both  and  are even, being reduced to two. Then the number of leaves in  can be safely reduced to four or five. But actually we can still reduce it from five to three: suppose that the unpaired (fifth) leaf of subtree  is covered by an out-traversal to one of the other three subtrees. At most at the same cost we could replace it by an in-traversal of . Therefore in this case  can be safely reduced to three or four.

















The following proposition helps us to complete the proof of correctness of our approach.




 
Any tagged component tree (,) has an optimal cover that
includes no bridge (a path connecting two internal nodes of (,)).


Any indel-neutral bridge can be elongated to connect two leaves with at most the same cost.


We can then assume that, if an optimal cover must include a bridge, it is indel-saving.
The cases of clean leaves only or leaves that share one tag are covered by Theorems <ref> and <ref>.

Now we will prove the case of a component tree with two non-empty canonical subtrees whose leaves share no tag.
By generalizing the statements of Theorems <ref> and <ref>, we can assume that there is an optimal cover that has no bridge connecting two nodes that belong to the same canonical subtree.
Therefore, such a bridge either connects one node of each subtree to one node of the other, or if there is bad link P between the subtrees, it can connect two nodes from P or a node from P and a node from one of the two subtrees. But, if we have such a bridge, we have no out-traversal nor semi-traversal, otherwise these would cover the same nodes covered by the bridge. This means that all the leaves of the two canonical subtrees are then covered by in-traversals or paths connecting a leaf to an internal node of the same canonical subtree.
We then have two types of cases: 

(i)  and  – such an indel-saving bridge would lead to an overall cost of w=⌈/2⌉ + ⌈/2⌉ + 1. If instead we replace this bridge by an indel-saving out-semitraversal, we get the cost of w'=⌈(-1)/2⌉ + ⌈/2⌉ + 1≤ w.

(ii)  and :
(a)  is odd – such an indel-saving bridge would lead to an overall cost of w=⌈/2⌉ +  (+1) + 1 and can be replaced by an indel-neutral out-traversal, resulting in the cost of w'=⌈(-1)/2⌉ + -1 + 2=⌈(-1)/2⌉ +  + 1≤ w;
(b)  is even and ≥ 2 – such an indel-saving bridge would lead to an overall cost of w=⌈/2⌉ +  + 1 and can be replaced by two indel-neutral out-traversals, resulting in the cost of w'=⌈(-2)/2⌉ + -2 + 4=⌈/2⌉ +  + 1= w;
(c)  is even and = 1 – such an indel-saving bridge would lead to an overall cost of w= 1 +  + 1 =  + 2 and can be replaced by one indel-neutral out-traversal, resulting in the cost of w'=  + 2= w. 

For trees with three or four types of leaves we can develop a similar proof, but with more cases to be analyzed.















Lemma <ref>:

Let n=|≫|+|å|+||.
The relational graph R(,), its number of cycles, their indel-potentials and the components can be computed in 𝒪(n) time <cit.>. 
	The tagged component tree can also be constructed in 𝒪(n) time <cit.>.
	For our transformation of the chained tagged component tree (,) into the tagged component tree (,), we traverse  in a bottom-up manner and recursively perform flower-contractions. For each removed tagged good leaf, its tag set is added to the one of its neighbor. While doing this, we obtain the sets of leaves , ,  and . 
	
	We then need to obtain the non-empty canonical subtrees and bad links separating them. 
	For each leaf class L, we again traverse the tree in a bottom-up manner. For each leaf in L we proceed until we find a branching vertex, that we will call subroot of L. After all leaves of L are visited, we repeat the procedure for all subroots of disjoint subtrees of L, until we get a single connected subtree.
	After repeating this procedure for all non-empty leaf classes, 
	the bad vertices that were not visited are then  bad links. 
	All traversals of the tree can be done in 𝒪(k) time, where k ≤ n is the number of nodes of (,). 
	
	For the reduction, we
	can obtain the set of 
	balanced in-traversals of each canonical subtree in 𝒪(k) time <cit.>. The reduction of each tagged canonical subtree requires another traversal of the tree and also takes 𝒪(k) time.
	
	After reducing the tagged canonical subtrees, but before performing the reduction of the clean subtree  we still need to 
	examine whether the tree has the solo leaf.
	The candidates can be found by detecting leaves in short leaf-branches, a procedure already described in <cit.>, but we still need to check for each candidate whether it is indeed a solo leaf. 
	 The only approach we could devise so far tests all possible hypotheses (no solo leaf and each clean short leaf-branch of (,) as solo leaf) and takes one that results in the smallest cover cost. 
	 In order to get the cover cost of each possible residual subtree, we need to examine its topology.
	Non-canonical partition subtrees and tag mates can be obtained by a single traversal of the residual tree, that takes 𝒪(k) time.
	Once we have obtained all required properties, we can look up the optimal cover cost at the residual leaf composition enumeration (in Appendix 2).
	 Therefore, the step of determining the solo leaf together with reducing the clean subtree and obtaining the cover of the residual tree has time complexity 𝒪(kℓ), where ℓ is the number of leaves in . Since ℓ≤ k ≤ n, the time complexity of this step is 𝒪(n^2) and it dominates the complexity of the whole procedure.
	
	In summary, the time complexity of our approach is 𝒪(n^2).






 §.§ Algorithms


Algorithm <ref> computes the residual tree of any tagged component tree based on Reduction Bounds <ref> to <ref>.
We observe that the reduction of tagged subtrees do not affect the solo leaf candidates. In fact a reduction can increase the length of a leaf-branch, turning a short into a long leaf-branch, as shown in Figure <ref>. However, this is a very limited behaviour that only happens when the reduction is not balanced, as in the reduction from 3 to one leaf, and can be prevented by the choice of the leaf to be kept in this reduction (see more details below). Therefore it is safe to detect the solo leaf after reducing all tagged subtrees. 










Reducing a canonical subtree from ℓ≥ 4 to 2 (if ℓ is even) or 3 (if ℓ is odd) is described in Algorithm <ref>: it suffices to take any set of balanced in-traversals (keeping the solo leaf if the reduced subtree is clean). In fact, this algorithm uses a generalization of a balanced reduction.
Let 𝒫 be a 
set of balanced in-traversals of some canonical subtree of (,).
A simultaneous 𝒫-reduction of (,) results in a smaller
tagged component tree as follows.
Let T' be the tagged tree obtained from (,) by replacing each bad node b of each P ∈𝒫 by a good node g, such that (g)=(b).
Then -𝒫(,) is the flower-contracted version of
T'. 


 



Reducing a canonical subtree from ℓ = 3 to 1 is described in Algorithm <ref>: here we need to take one leaf to be kept, while the other two are used for the reduction. In order to prevent the risk of creating a new bad leaf with the reduction and/or the risk of selecting an unsafe reduction, it is necessary to be careful with the decision of the leaf to be kept, that we call essential leaf.
Sometimes two or even the three leaves are suitable to be essential, but, since it suffices to identify a single one, the first one that is found is called the essential leaf. 

It is identified as follows:
 
  
  
 
 
 
  * It is the leaf of a leaf-branch of L that is also a leaf-branch of (,), if there is any. This case avoids the “destruction” of a possible solo leaf, as illustrated in Figure <ref>. It also avoids other unsafe reductions, as illustrated in Figure <ref>, parts (i) and (ii).
 
  * Otherwise at least one node of each leaf-branch P_i of L is connected to (,)\L; then let F(P_i) be the subgraph of (,)\L that is connected to the leaf-branch P_i and the set 𝒮(P_i) be the superset of the tag sets of the leafs of (,) that are in F(P_i). If, for two leaf-branches P_1 and P_2 of L, we have 𝒮(P_1) ∩𝒮(P_2) ∅, then any of the two leaves in P_1 or P_2 is the essential leaf. This case avoids that a canonical subtree become isolated, as illustrated in Figure <ref>, part (iii).
 
 
  * Otherwise any leaf of L is the essential leaf.
 
 

 



 

 








The only approach we could devise for determining the existence of the solo leaf tests all possible hypotheses (no solo leaf and each clean short leaf-branch of (,) as solo leaf) and takes one that results in the smallest cover cost. For that reason, reducing the clean subtree is done together with searching the solo leaf, as described in Algorithm <ref>.







































































§ APPENDIX 2: ENUMERATION OF OPTIMAL COVERS FOR RESIDUAL TREES


In this section we enumerate optimal covers and their respective costs for all topologies of residual trees that have at least one leaf with non-empty tag set and at least two leaves that do not share a tag.
Let  be the number of -leaves,  be the number of -leaves,  be the number of -leaves and  be number of -leaves in a residual tree. 
Recall that ≤ 2 for all residual trees. Due to the symmetry between -nodes and -nodes, we assume without loss of generality that ≥.
The enumeration is kept as extensive as necessary but as simple as possible.



 §.§ Residual trees are identified by their leaf composition

 A leaf composition is represented by a tuple  of four non negative values that always has  in the first position,  in the second position,  in the third position and  in the fourth position. 
 
Examples:


    
    0021:     
    A leaf composition in which subtrees  and  are empty, subtree  has two leaves and subtree  has one leaf.

    2124:     
    A leaf composition in which subtree  has two leaves, subtree  has one leaf, subtree  has two leaves and subtree  has four leaves.







 §.§ Nomenclature




  §.§.§ General topologies of residual trees


:     
		The tagged component tree ^R is fully co-rooted.

    :     
		The tagged component tree ^R is fully separated.

	:     
		There is a short leaf-branch in ^R with a clean leaf.






Relations between partition subtrees are described by the following notation, presented with the help of examples.



  §.§.§ Partition subtrees and their specific relations in possible topologies of residual trees



    :     
		The canonical subtree .

    :     
		The partition subtree ∪,
		in which the canonical subtrees
		 and  may be co-rooted or separated. 

    :     
		The partition subtree ∪, in which the subtrees  and 
		are co-rooted. 

	:     
		The subtree  is non-isolated, that is,  and its complementary subtree =∪∪ are co-rooted.

    :     
		The partition subtree ∪, in which the subtree  is separated from .

    :     
		The subtree  is isolated, that is,  is separated from 
		its complementary subtree =∪∪.

	
	
		
	:     
		The extended subtree  has an -mate.

		
	:     
		The tree obtained by pruning from ^R a clean short leaf-branch.

	:     
		The subtree  is non-isolated in a .

		





The relations above can be applied to non-canonical subtrees: 

()  ,  ()  ,  ()  ,  ()  ,  ()  ,  ()






  §.§.§ Logical operators


	 And: ;  Or: ;  Absence of given properties: ,



  §.§.§ Identifiers of the optimal covers


    I, II:     Basic optimal covers

	M:     Tag mate

	S:     Short path (usually covering a solo leaf)

	nR:     Not reducible

	:    
		Further reduction is possible for this type of topology

	W:     Worst case





Optimal covers are described by the following notation, presented here with the help of examples.



  §.§.§ Descriptions of optimal covers


	:     
		A short path (whose cost is one) covering an -leaf. 

	:     
		A covering in-traversal using two -leaves that have not been covered
		before. The dot on top indicates that the cost of this traversal is one.

	:     
		A covering out-traversal using one - and one -leaf that have not
		been covered before. The dots on top indicate that the cost of this traversal
		is two.

    :     
		The parentheses around the subtree indicate that the respective leaf has
		already been covered previously.

	:     
		A semi-traversal (of cost one) using an -leaf with an internal node that is an -mate. The specific (extended) subtree that contains the -mate is given in the topology description.

   | 2:    
		The cost of the cover is given to the right of the vertical bar.
 
  ∪ 2221:    
		The optimal cover in
		this case consists of the given in-traversal plus the cost of the optimal cover of the appropriate topology of the reduced leaf composition 2221.

	|+1:    
		A “+” means that the cost has to be added to that of the reduced leaf composition.






For each leaf composition and topology we describe one optimal cover, even though other optimal covers may also exist.



 §.§ Enumeration of residual leaf compositions of Group 1

Residual leaf compositions with exactly two non-empty canonical subtrees that do not share a tag, defined by Reduction Bound <ref>. This includes 11 leaf compositions, divided in three subgroups:




6cReduction Bound <ref>

 2c00     2c00      2c00

 1100     2100     1010     2010     0011      0021 

    2200     1020     2020     0012     0022 






 

Residual leaf compositions of subgroup 00



        
	     2l1100 

		     any topology     I          2
	    
        

          
        
	            2l2100 

		                       S     ,      2 

		              else          M      ,      2 

		                  else     W      ,      3
        
                    
        

                    
        
	            2l2200 

		                      I      ,      2 

		             short bad link         S      ,  , bad link cut     3 

		             else     
                                            Ma      ,  ,
                                                     3 

		                      Mb      ,  , 
		              3 

		                 else     W          4
        
        
 
        
Residual leaf compositions of subgroup 00



        
		     2l1010 

				    any topology     I          2
		     
		     
		     

		     
        
	             2l1020 

	                          S     ,      3 

		              else          Sa     ,      3 

		                       M      ,      3 

		                  else     W      ,      4
        
        

                    
                    
	            2l2010 

   		                  S     ,      2 

		             else     W      ,      3
		    
                    

                    
                        
	            2l2020 

		                   I      ,      3 

		              else     W          4
		    

 

Residual leaf compositions of subgroup 00



                    
	   	    2l0011 
	
				    any topology     I          2
		    
                    


                    
	            2l0012 

		                  S     ,      2 

		             else     W      ,      3
		    
                    

                    
                    
	            2l0021 

	                        S     ,      3 

		             else          Sa     ,      3 
 
		                     Ma      ,      3 

			              Mb      ,      3 

			 
			         else     W      ,      4
                    
                    


           
	            2l0022 

		                   I      ,      3 

		              else     W          4
		    

	



 §.§ Enumeration of residual leaf compositions of Group 2

Residual leaf compositions with exactly three non-empty canonical subtrees. This includes 25 leaf compositions, divided in three subgroups:





3cReduction Bound <ref>

 1cCase 1     2cCase 2
 
 110     210     220

 1110     2110     2210

1120     2120     2220

1130        

    

3cReduction Bound <ref>

1cCase 1     1cCase 2     1cCase 3

110     210     220

1101     2101     2201

1102     2102     2202

    2103     2203

        2204

     

4cReduction Bound <ref>

3cCase 1     1cCase 2

 101     102     201     202

 1011     1021     2011     2021

  1012     1022     2012     2022

              2023 

  




 


Reduction Bound <ref>: residual leaf compositions of subgroup 110 + 210 + 220



	
		2l1110 

			               S     ,      3 

			    else             Sa     ,      3 

			    	            Sb     ,      3 

			    	    else     ()     Ma    
				 ,      3

			    		        ()     Mb     
					 ,      3

			    		        else     W      ,      4
		



	
		2l1120 

			    any topology     I      ,      4
		




		2l1130 

		    
		  
		    2*S    
		2*,  ,     
		2*5 

		     
		()  ()         

		    else          ∪  1110     +2
		



    
             2l2110 

		            I      ,      3 

		    else           SM     ,  ,
		     3 

		        else     W      ,      4
		


        
	
		2l2120 

			               Sb     ,  ,      4 

			    ∃             S     ,  ,     
			4 

			    	                      

			   	    ()    
				()     M      ,  ,
				     4 

			             
			            

			                  

			    else           W      ,  ,      5
		









	
		2l2210 

			            S     ,  ,      3 

			            Ia      ,  ,
			     4 

			            Ib      ,  ,
			     4 

			    else          Ma    
			 ,  ,      4 

			             Mb      ,
			 ,      4 

			        else     W      ,  ,      5
        
        

        
         
            2l2220 

			                I      ,  ,      4 

			               IIa      ,      5 

			               IIb      ,      5
			

			                 Ma      ,
 			 ,  ,      5 

 			                Mb      ,  ,  ,      5 

			    
				              SMa     ,
				 ,  ,      5 

			    	             MMa      ,  ,
				     5

			    	              SMb     ,
				 ,  ,      5 

			   	             MMb      ,  ,
				     5 

			        else        W      ,  ,      6
		








 


Reduction Bound <ref>: residual leaf compositions of subgroup  110 + 210 + 220



   
		2l1101 

			    any topology     I      ,      2
		



	
		2l1102 

			    any topology     I      ,      2
		



	
		2l2101 

		         I      ,      2 

		    else     W      ,      3
		



	
		2l2102 

			    any topology     I      ,      3
		



	
		2l2103 

		         nR      ,      3 

		    else          ∪  2101     +1
		



        
	       2l2201 
	
			            Ia      ,  ,
			     3 

			            Ib      ,  ,
			     3 

			    else          Ma      ,
			 ,      3 

			             Mb      ,  ,
			     3 

			       else     W      ,  ,      4
		



	
		2l2202 

			         Ia      ,      3 

			         Ib      ,      3 

			    else     W      ,  ,
                                     4
        




	
		2l2203 

		          2*nR
		    2* ,  ,     
		2*4 

		     
		        
		   

		    else          ∪  2201     +1
		




		2l2204 

		      
		     nR    
		 ,      4 

		    else          ∪  2202     +1
		

 

Reduction Bound <ref>: residual leaf compositions of subgroup 101 + 102 + 201 + 202



	
		2l1011 

			         S     ,      2

			    else     W      ,      3
		




	
		2l1012 

			    any topology     I      ,      3
		



	
		2l1021 

			         I      ,      3 

			    else     W      ,      4
		



	
		2l1022 

			            I      ,  ,
			     4 

			    else          S     ,
                                                    ,
                                                       
                                                                       4 

			             Ma      ,  ,
			     4 

			             Mb      ,  ,
				     4 

				 
		                else     W      ,  ,
				      5
		



    
		2l2011 

			    any topology     I      ,      3
		



	
		2l2012 

			         S     ,      3

			    else     W      ,      4
		



	
		2l2021 

			            I      ,  ,
			     4

			    else          S     ,  ,      4 

			             Ma      ,  ,      4 

			              Mb
			     ,  ,      4 

			       else     W      ,
                                       ,
                                           5
		



	
		2l2022 

		             I      ,      4

		        else     W      ,  ,      5
		



	
		2l2023 

		           2*M    
		2* ,  ,      2*5 
 
		                  

		    else          ∪  2021     +1
		





 §.§ Enumeration of residual leaf compositions of Group 3

Residual leaf compositions with four non-empty canonical subtrees. This includes 20 leaf compositions:






6cReduction Bound <ref>

1cCase 1     2cCase 2    3cCase 3

111     112     211     212     221     222 

1111    1121    2111     2121    2211    2221

1112    1122    2112     2122    2212    2222

    1123    2113     2123    2213    2223

            2124    2214    2224








    
		2l1111 

		    ()()     Ia    
		 ,      3 

		    ()() (else)     Ib    
		 ,      3
		



	
		2l1112 

			         S     ,  ,
			     3 

			    else     W      ,  ,      4
		




		2l1121 

		                 I      ,  ,
		     4 

		    else     ()() 
		         S1     ,  ,      4 

			                 Ma      ,
			 ,      4 
 
			        ()()
		             S2     ,  ,      4

			                 Mb      ,
			 ,      4 
 
			        else         W      ,  ,      5
		



	
		2l1122 

			         I      ,  ,      4 

			    else     W      ,  ,      5
		



	
		2l1123 

	    ()      Ma      , ,
			 ,      5 

	    ()       Mb      , ,
			 ,      5 

	    else           ∪ 1121     +1
		
	




		2l2111 

			      ()     S     ,  ,
			     3 

			    else     W      ,  ,
			     4
		
		



	
		2l2112 

			    any topology     I      ,  ,      4
		



	
		2l2113 

			          2*S      2*,  ,       2*4 

			    ()                

			    else          ∪ 2111     +1
		



	
		2l2121 

			      ()     I
			     ,  ,      4 

			    else     W      ,  ,      5
		



	
		2l2122 

			            I      ,  ,
			     5 

			    else          S     ,  ,  ,
			     5 

			   	         Ma      ,  ,
				 ,      5 

			   	          Mb1        ,
				 ,  ,      5 

			   	     ()     Mb2    
				 ,  ,      5 

			   	    else     W      ,  ,      6
		



	
		2l2123 

			          2*I     2*  ,  ,       2*5 

			    ()          

			
			    else           ∪ 2121     +1
		



	
		2l2124 

			                  

			    ()      M      ,  ,  ,      6 
 [-.4em]
			                 

			                

			    else          ∪ 2122     +1
		




		2l2211 

			             Ia      ,  ,      4 

			             Ib      ,  ,      4 

			        
			     SMa     ,  ,
			 ,      4 

			    	         SMb     ,  ,
				 ,      4 

			    else         W      ,  ,      5
		





		2l2212 

			          ()     S1     ,  ,
			     4 

			         ()     S2    
			,  ,      4 

			    else         W      ,  ,      5
		



	
		2l2213 

			    2l 

			             2*nR    
			2* ,  ,      2*5 
 
			                       

			    else              ∪ 2211     +1
		



	
		2l2214 

		    2l  

		           {  () }    
		    2*S     2*,  ,
		         2*5 

		           {  () }            
 
			    else              ∪  2212     +1
		



        
		2l2221 

			     ∃              S1     ,  ,  ,     5 

			                 S2     ,  ,  ,     5 

		 	    	           ()     Ia    
		 		 ,  ,  ,      5 

		 	    	             1*Mb     2* ,   ,
				 ,      2*5 

		 	                  
		 	 1*Mb          

		 	   	             1*Ma     2* ,  ,
				 ,      2*5 

			        
                                                      1*Ma          

			    	           ()     Ib      ,  ,
				 ,      5 

		     else             W      ,  ,  ,
		      6
		



	
		2l2222 

			                ()     Ia      ,  ,      5 

			          ()     Ib      ,  ,      5 

			    else         W      ,  ,  ,
			     6
		



   
		2l2223 

		    {  () }         

		    {  () }         

		                      I      ,  ,  ,      6 

		                      S     ,  ,  ,      6 

                               

                              

	                              Ma      ,
			 ,  ,      6 

	                              Mb      ,
			 ,  ,      6 

	                       

	           else          ∪ 2221     +1
		



	
		2l2224 

		    2l  

			        {  () }    
			2*I     2* ,  ,
			     2*6

			        {  () }            

			    else              ∪  2222     +1
		
		






