BACKGROUND
the small phylogeny problem consists in reconstructing the ancestral gene orders at the internal nodes of a species tree, given the gene orders of the extant genomes at the leaves of the tree.
there exist two main computational approaches for the reconstruction of ancestral gene orders from extant gene orders: rearrangement-based methods, and homology-based methods.
the rearrangement-based methods require a rearrangement model, and consist in finding a rearrangement scenario that minimizes the total rearrangement distance on the branches of the species tree  <cit> .
the homology-based methods consist in finding the ancestral gene orders associated with the internal nodes of the species tree, such that the total amount of homoplasy phenomenon observed in the species tree is minimized  <cit> .
homoplasy is a phenomenon by which two genomes in different lineages acquire independently a same feature that is not shared and derived from a common ancestor.
for the inference of the ancestral gene order at a tagged internal node, the homology-based methods are usually composed of two steps.
the first step consists in detecting a set of potential ancestral contiguity features, by comparison of pairs of extant genomes whose path goes through the ancestor in the species tree.
the second step is an assembling phase that requires to compute an accurate conservation score for each potential ancestral feature, based on the species tree.
using these scores, some heuristic algorithms are then used to resolve the conflicts between the ancestral features in order to assemble them into contiguous ancestral regions .
a car of an ancestral genome is an ordered sequence of oriented blocks  that potentially appear consecutively in this ancestral genome.
in the absence of tangible evolution model, the homology-based methods have the convenience to reconstruct cars that contain only reliable features inferred from a conservation signal observed in the extant genomes.
however, the ancestral genomes reconstructed using homology-based methods are often not completely assembled, as some rearrangement or content-modifying events might have caused the loss of some ancestral contiguity features in the extant genomes.
thus, the homology-based methods proposed in the literature usually enlarge the condition of contiguity in order to detect more potential ancestral contiguity features, -adjacencies between two blocks  <cit> , maximum common intervals of blocks  <cit> , gapped adjacencies  <cit> .
hence, these different types of contiguity features can be classified according to the tightness of their definition of contiguity.
the homology-based methods should then account for this classification when assembling different types of contiguity features.
this approach was used in  <cit>  where a method, gapadj, was presented for iteratively detecting gapped adjacencies.
gapadj uses a progressively relaxed definition of contiguity allowing an increasing number of gaps between ancestral contiguous synteny blocks in extant genomes, and iteratively assembling these gapped adjacencies using a heuristic traveling salesman algorithm .
the tsp is applied on a graph whose vertices are synteny blocks, and edges are potential ancestral adjacencies between these blocks.
here, we follow the same idea, and we present an homology-based method that is based on iteratively detecting and assembling ancestral adjacencies, while allowing some micro-rearrangements of synteny blocks at the extremities of the progressively assembled cars.
the method starts with a set of non-duplicated blocks as the initial set of cars, and detects iteratively the potential ancestral adjacencies between extremities of cars, while building up the cars progressively by adding, at each step, new non-conflicting adjacencies that induce the less homoplasy phenomenon.
the species tree is used, in some additional internal steps, to compute a score for the remaining conflicting adjacencies, and to detect other reliable adjacencies, in order to reach completely assembled ancestral genomes.
the first originality of the method comes from the usage of the progressively assembled cars for the detection of ancestral contiguity features allowing micro-rearrangements.
the second originality comes from the assembling method at each iterative step that consists in adding the contiguity features gradually giving priority to the features that minimize the homoplasy phenomenon, rather than relying on a heuristic algorithm for discarding false-positive features.
we discuss the usefulness of the method through a comparison with three other homology-based methods  on the same real dataset of amniote genomes for the reconstruction of the boreoeutherian genome.
preliminaries: genomes, species tree, conserved adjacencies
for the reconstruction of ancestral genomes from extant ones, genomes are represented by identifying homologous conserved segments along their dna sequences, called synteny blocks.
these blocks can be relatively small, or very large fragments of chromosomes.
the order and orientation of the blocks, and their distribution on chromosomes may vary in different genomes.
a signed block is a block preceded by a sign + or − representing its orientation.
by convention, a signed block +a is simply written a. here we assume that all genomes contain the same set of non-duplicated blocks and consist of several circular or linear chromosomes composed of signed blocks.
for example, consider the five genomes represented at the leaves of the tree in figure  <dig>  the bullets at the extremities of the chromosomes represent the telomeres of linear chromosomes.
genomes a and b consist of one linear chromosome each, and genomes c, d, and e consist of two linear chromosomes each.
a contiguous ancestral region  is defined as a potential chromosome of an ancestral genome.
a segment in a genome is an ordered set of signed blocks that appear consecutively in the genome.
the length of a segment is the number of blocks composing this segment.
in the above example, {b c d e} is a segment of length  <dig> in the genome a.
two segments of two different genomes are called syntenic segments if they contain the same set of blocks.
for example, the segments {h −g − f d} of genome d and {−d f g h} of genome e are syntenic.
an adjacency in a genome is an ordered pair of two consecutive signed blocks.
for example, in the above genomes,  is an adjacency of genomes a, b, c, and e, and  is an adjacency of genome b. since a whole chromosome or a segment can always be flipped, we have  = .
for example,  =  is an adjacency shared by genomes b, c, and d.
a species tree on a set of k genomes is a rooted tree with k leaves, where each genome is associated with a single leaf of the tree, and the internal nodes of the tree represent ancestral genomes.
for example, figure  <dig> shows a species tree on genomes a, b, c, d, and e.
here, for the reconstruction of ancestral gene orders, we consider an ancestral node of the species tree that has exactly two children resulting from a speciation .
the species partition defined by an ancestral node is the partition of the extant species into three sets: two ingroup sets i <dig> and i <dig> corresponding to the two lineages descending from the ancestor, and one outgroup set o containing all other extant genomes.
a conserved adjacency at an ancestral node of the species tree is an adjacency shared by at least two genomes belonging to at least two different sets of the species partition defined by the ancestral node.
such two genomes are linked by a path that goes through the ancestral node.
for example, in figure  <dig>   is a conserved adjacency of the black-colored ancestral node because it is shared by genomes c and e whose path goes through the ancestor.
the adjacency  is also a conserved adjacency of this ancestor because of its presence in genomes d and e.
a conserved adjacency at an ancestral node is considered as a potential adjacency of this ancestor.
homology-based methods for the reconstruction of ancestral gene orders usually consist in, first, detecting all the conserved adjacencies at the ancestral node, and next, assembling these conserved adjacencies into cars.
the difficulty in this assembling phase comes from the conflicts that may exist between some conserved adjacencies.
two adjacencies are called conflicting adjacencies when they involve a same block extremity, and thus they cannot be both present in the same ancestral genome.
for example, in figure  <dig>  the conserved adjacencies  and  of the black-colored node are conflicting as they both involve the right extremity of block g. two adjacencies that are not conflicting are called compatible.
a set of adjacencies is said non-conflicting  if all pairs of adjacencies in the set are compatible.
here, we distinguish two types of conserved adjacency regarding their presence or absence in the three sets of species defined by the considered ancestral node: the two ingroup sets i <dig> and i <dig>  and the outgroup set o. a fully-conserved adjacency is a conserved adjacency that is present in at least one genome of each of the three sets of species.
a partly-conserved adjacency is any other conserved adjacency.
for example, in figure  <dig>   is a fully-conserved adjacency of the black-colored ancestral node, while all other conserved adjacencies are partly-conserved adjacencies.
the homoplasy cost of an adjacency at a given ancestral node a counts the number of branches linked to this ancestor on which the adjacency would have been gained  or lost  if it was present in the ancestor.
it is defined as follows: it is either  <dig> if the adjacency is fully-conserved at a, or  <dig> if it is partly-conserved at a, or  <dig> if it is present in only one of the sets i <dig>  i <dig> and o, or  <dig> if it is present in none of these sets.
note that if an adjacency has an homoplasy cost of  <dig> or  <dig> at the ancestral node a, then the adjacency is not conserved at this node.
for example, in figure  <dig>  the adjacency  has a cost  <dig>  the adjacency  a cost  <dig>  the adjacency  a cost  <dig>  while the adjacency  has a cost  <dig>
method
the homology-based problem considered in this paper for the reconstruction of ancestral gene orders can be stated as follows:
problem.
given a species tree on a set of extant genomes, each composed of the same set of blocks, and given an ancestral node in this species tree, find a set of cars at the ancestral node, with a maximum number of adjacencies, that minimizes the total homoplasy cost.
compared to other homology-based methods for the reconstruction of ancestral gene orders, the progressive method presented in the following consists in adding adjacencies progressively, as opposed to discarding false adjacencies in a single assembling step.
a global description of the progressive method steps is presented in the following, and the refined descriptions are presented next.
inputs and start
the input of the method is a phylogeny with a tagged ancestral node whose block order is to be reconstructed, and a set of n orthologous blocks that are used to describe the block orders of the genomes at the leaves of the tree.
the initialization of the method consists in starting with an initial set of n cars, each composed of a single block.
overall idea
the core of the method relies on iteratively computing new block adjacencies in order to concatenate cars progressively .
at each step, a set of potential adjacencies is first detected, then the method selects a subset of non-conflicting adjacencies that are added to the current cars.
the following three steps are used iteratively in order to collect the ancestral adjacencies: step a) consists in detecting the conserved adjacencies and the homoplasy costs of these adjacencies are used to classify and select a subset of non-conflicting adjacencies to be added in current cars; step b) consists in resolving conflicts between adjacencies and selecting a subset of non-conflicting adjacencies to be added in current cars; step c) consists in detecting some adjacencies not conserved at the ancestral node, but supported by putative genome rearrangement events.
in the next paragraphs, we briefly give an overview of each of these steps.
a) adding non-conflicting conserved adjacencies
this step comes after the initialization phase, or after a step a), or b) or c) that ended up with a non-empty set of added adjacencies.
the step begins with the detection of the conserved adjacencies between the current cars at the ancestral node.
next, the non-conflicting fully-conserved adjacencies are selected in a first phase.
then, the non-conflicting partly-conserved adjacencies that are compatible with all fully-conserved adjacencies are added in a second phase.
the set of all conserved adjacencies added in the cars in this step is denoted by nc.
it constitutes a non-conflicting set of adjacencies.
the conserved adjacencies not added in this step are stored in a set c and tagged as conflicting adjacencies for a next step b).
b) resolving conflicts between adjacencies
this step comes after a step a) that ended up with an empty set nc, and a non-empty set c. it considers the set c of adjacencies tagged as conflicting in this last step a).
a cost, different from the homoplasy cost, is computed for each of these adjacencies, and a non-conflicting subset cm of c that has a maximum size and minimizes the sum of the adjacencies costs is computed.
this subset of adjacencies is added in the cars, and the remaining adjacencies of the set c−cm are discarded permanently.
c) detecting dcj-reliable adjacencies
this step comes after a step a) that ended up with an empty set nc, and an empty set c. it consists in finding new potential adjacencies that are not conserved at the ancestral node .
each of these new potential adjacencies is supported by the presence of an adjacency in the current set of cars, and two adjacencies in an extant genome g, such that those three adjacencies completed by the new potential adjacency induce a single genome rearrangement event, specifically double-cut-and-join  events, between the ancestral genome and the genome g. a maximum size non-conflicting subset of the new potential adjacencies is added in the cars, and the remaining adjacencies are discarded permanently.
we now give the detailed descriptions of step a), b) and c).
step a): detection of non-conflicting conserved adjacencies
in this section, we first explain how the conserved adjacencies are defined.
next, we describe how a subset of non-conflicting adjacencies is selected by giving priority to the fully-conserved adjacencies.
detection of the conserved adjacencies
we begin by stating the definition of a car adjacency in an extant genome at a leaf of the species tree, given the set of cars in the current step of the method.
let us recall that a car is an oriented sequence of signed blocks.
we denote by |x| the block corresponding to a signed block x in a car.
a signed car is a car possibly preceded by − indicating its reverse orientation.
for example, if car_x = {a −b c}, then -car_x = {−c b − a}.
let car_a and car_b be two signed cars in the current set of cars with car_a = {a <dig> a <dig> ... an} and car_b = {b <dig> b <dig> ... bm}.
the ordered pair  is a car adjacency in an extant genome g if there exists a pair of segments sa and sb consecutive in genome g such that the segment sa  contains only blocks from car_a , and satisfies the following constraints:
<dig>  i.)
sa is either the segment {an}, else ii) a segment of length na >  <dig> ending with the block |an|, else iii) a segment syntenic to a segment of car_a containing the block |an|,
<dig>  i) sb is either the segment {b1}, else ii) a segment of length nb >  <dig> starting with the block |b1|, else iii) a segment syntenic to a segment of car_b containing the block |b1|.
as for the blocks, the car adjacency  is equivalent to .
for example, consider the following three cars composed of ten blocks:
car_ <dig> = • a b c • ;
car_ <dig> = • d e f g • ;
car_ <dig> = • h i j •.
the genome g = • b c −d f • ; • e −g i j a −h • has three car adjacencies: , , and .
the pair  is a car adjacency because of segment s <dig> = {c} and s <dig> = {−d f } that are consecutive in the genome g, and such that s <dig> satisfies the constraint  <dig> i) and s <dig> satisfies the constraint  <dig> ii).
the car adjacency  is supported by the segments s <dig> = {e −g} satisfying  <dig> ii) and s <dig> = {i j} = {−j −i} satisfying  <dig> iii).
the car adjacency  is supported by the segments s <dig> = {j} satisfying  <dig> i) and s <dig> = {a} satisfying  <dig> i).
the block adjacency corresponding to the car adjacency  with car_a = {a <dig> a <dig> ... an} and car_b = {b <dig> b <dig> ... bm} is the adjacency .
in the previous example, the block adjacencies corresponding to ,  and  are respectively , , and .
proposition  <dig> let car_a = {a <dig> a <dig> ... an} be a signed car in the current set of cars.
an extant genome g has at most two car adjacencies of the form .
proof let us suppose that an extant genome g has more than two car adjacencies of the form .
say , , and  are three of them.
these car adjacencies would be supported by 1) three pairs of consecutive segments on g, ,,, such that 2) sa <dig> sa <dig> sa <dig> contain the block |an|, and 3) sx, sy , sz are non-intersecting segments since they belong to three different cars.
it is impossible to find an ordering of the six segments on g such that the constraints 1), 2) and 3) are all satisfied simultaneously.
thus, the genome g contains at most two car adjacencies of the form .
□
remark  <dig> the definitions of fully or partly conserved adjacencies are naturally extended to car adjacencies as follows: a conserved car adjacency at an ancestral node of the species tree is a car adjacency shared by at least two extant genomes that belong to at least two different sets of the species partition defined by the ancestral node.
a fully-conserved car adjacency is a conserved car adjacency belonging to at least one genome of each of the three sets of the species partition defined by the ancestral node.
a partly-conserved car adjacency is any other conserved car adjacency.
the homoplasy cost associated to a car adjacency is a natural extension of the definition given for the block adjacencies.
classification and selection of the conserved adjacencies
the overall idea of this phase is to select conserved adjacencies while giving priority to the fully-conserved adjacencies, and to the adjacencies that have the less conflicts with other adjacencies.
let s be the set of block adjacencies corresponding to the conserved car adjacencies at the ancestral node.
in the sequel, the abbreviations fs, ps, nc, c stand for fully, partly, non-conflicting, and conflicting conserved adjacencies respectively.
figure  <dig> shows the organization of the sets of adjacencies that are considered in this phase.
let fs and ps be the subsets of s that contain respectively the fully-conserved adjacencies and the partly-conserved adjacencies.
thus, s = fs ∪ ps and fs ∩ ps = ∅.
first, we consider the fully-conserved adjacencies.
let fs_nc be the subset of fs that contains the adjacencies that are compatible with all other adjacencies in fs.
the corresponding set of conflicting adjacencies is fs_c = fs - fs_nc.
the fully-conserved non-conflicting adjacencies contained in the set fs_nc are automatically retained to be added in the cars.
thus,  in the following, any adjacency that is in conflict with some adjacencies of fs_nc will be discarded permanently.
next, we consider the partly-conserved adjacencies.
let ps_d be the subset of ps containing adjacencies that are in conflict with some adjacencies of fs_nc, and ps_r be the set of the remaining adjacencies in ps.
thus, ps_r = ps - ps_d.
the adjacencies of ps_d are discarded permanently, as explained previously in .
let ps_nc be the subset of ps_r that contains the adjacencies that are compatible with all other adjacencies in ps_r.
the corresponding set of conflicting adjacencies is ps_c = ps_r - ps_nc.
finally, since the priority is given to fully-conserved adjacencies, we want to retain only the adjacencies of ps_nc that are not in conflict with the adjacencies of the set fs.
let ps_nc <dig> be the subset of ps_nc that contains the adjacencies that are compatible with all the adjacencies in fs.
the partly-conserved non-conflicting adjacencies contained in the set ps_nc <dig> are also retained automatically to be added in the cars.
it follows that the set of retained adjacencies nc = fs_nc ∪ ps_nc <dig> is a set of non-conflicting adjacencies.
this step a) of the method adds the set of adjacencies nc to the current cars of the ancestral genome, and updates the current set of conflicting adjacencies to the set c = s - ps_d − nc.
by construction, each adjacency contained in the set c is in conflict with at least one other adjacency of c, and compatible with all the adjacencies contained in the set nc.
the step a) can be recalled several times consecutively as far as the set nc of added adjacencies is not empty.
we now state a proposition ensuring that the current set of conflicting adjacencies c misses no previously found conflicting adjacency  such that the signed block a is the end of a signed car, and the signed block b is the start of a signed car in the current set of cars.
proposition  <dig> let  be an adjacency corresponding to a conserved car adjacency found in a previous step a) of the method.
the adjacency  is either present in the current set of cars, or is in conflict with an adjacency present in the current set of cars, or is also found in the current step a) i.e  ∈ s.
proof say that, in a previous step a), the adjacency  was supported by the detection of a conserved car adjacency  present in a subset g of the extant genomes.
1) if there exist in the current set of cars, a signed car car_a <dig> ending with the signed block a, and a signed car car_b <dig> starting with the signed block b, then the car adjacency  is also found in the same set  g of extant genomes.
thus, the adjacency  is also found in the current step.
2) otherwise, either there exists an adjacency of the form  or  in the current set of cars in conflict with the adjacency , or the adjacency  is present in the current set of cars.
□
step b): resolution of conflicts between adjacencies
this step considers a conflicting set c of adjacencies obtained at the end of a previous step a), and computes a non-conflicting subset of the set c to be added in the current set of cars.
definition of the cost of adjacencies
we begin by stating the definition of the cost of an adjacency in this step.
the mutation cost of a labeling of the nodes of a species tree on a given alphabet is the number of edges in the tree having two different labels at their extremities  <cit> .
here, the cost of an adjacency  ∈ c is the minimum mutation cost of a labeling of the nodes of the species tree on a binary alphabet { <dig>  1} such that  the ancestral node is labeled with  <dig>   the extant species nodes, where  corresponds to a car adjacency, are labeled with  <dig>  and  the other extant species nodes are labeled with  <dig>
in other terms, an adjacency has two possible states in a genome: present  or absent .
the cost of an adjacency  is the minimum number of changes of state necessary to explain the evolutionary history of the adjacency along the species tree, with the adjacency being present at the ancestral node.
for example, the costs of the two conflicting conserved adjacencies  and  shown in figure  <dig> are  <dig> and  <dig> respectively.
figure  <dig> shows two minimum mutation cost labelings of the nodes of the species tree corresponding to both adjacencies.
computation of the non-conflicting subset of adjacencies
the cost of a set of adjacencies is the sum of the costs of the adjacencies composing this set.
let m be the maximum size of a non-conflicting subset of the conflicting set c of adjacencies.
this step b) finds a non-conflicting subset cm of c of size m and minimum cost.
the set of adjacencies cm is added to the current cars of the ancestral genome, and the remaining adjacencies in the set c − cm are discarded permanently.
remark  <dig> note that the adjacencies of the set c − cm discarded in this step will never be detected again, since these adjacencies are in conflict with the adjacencies of the set cm added in the current step.
step c): detection of dcj-reliable adjacencies
this step considers the current set of cars, and computes new potential adjacencies not conserved, but supported by putative ancestral rearrangement events.
a double-cut-and-join  rearrangement event on a genome consists in the cut of two adjacencies of the genome in order to glue the four exposed extremities in a different way.
for example, a dcj event on the genome a =  that cuts the adjacencies  and  to obtain the adjacencies  and  produces the genome b = .
we now give the definition of potential ancestral adjacencies that can be inferred from putative genome rearrangements inspired from the definitions of reliable adjacencies in  <cit> .
here, we add the constraint that the signal of the reliable adjacency must be conserved on a path of the species tree that goes through the ancestor.
let car_a and car_b be two signed cars in the current set of cars with car_a = {a <dig> a <dig> ... an} and car_b = {b <dig> b <dig> ... bm}.
the adjacency  is a dcj-reliable adjacency of the ancestral node if there exists an adjacency  in the current set of cars such that the adjacencies  and  are present in an extant genome g <dig>  and  is a car adjacency in an extant genome g <dig> such that the genomes g <dig> and g <dig> belong to two different sets of the species partition defined by the ancestral node.
the potential presence of the adjacency  in the ancestral genome induces a dcj event that has cut the adjacencies  and  in the ancestral genome to produce the adjacencies  and  in the extant genome g <dig>
an example is given in section results and discussion.
in this step of the method, a maximum size non-conflicting subset of the dcj-reliable adjacencies is added in the cars, and the remaining dcj-reliable adjacencies are discarded permanently.
remark  <dig> note that the homoplasy cost of a dcj reliable adjacency is always  <dig>
RESULTS
we used procars to compute a set of cars for the boreoeutherian ancestral genome using the block orders of twelve amniote genomes, and we compared the result with the ancestors reconstructed by three other homology-based methods: anges  <cit> , infercars  <cit>  and gapadj  <cit> .
orthology blocks and phylogeny
we chose twelve genomes completely assembled and present in a pecan  <cit>  multiple alignment of  <dig> amniote genomes available in the release  <dig> of the ensembl compara database  <cit> .
the phylogenetic tree was directly infered from the classifications of the species obtained from the national center for biotechnology information taxonomy database  <cit>  .
we constructed a set of synteny blocks using the multiple alignments as seeds.
we used the block construction method described in  <cit> , keeping only the seeds that had an occurrence in each of the twelve genomes, removing the seeds that spanned less than 100kb, and joining seeds collinear in all genomes.
this resulted in a set of  <dig> genomes composed of  <dig> blocks for species homo sapiens , pan troglodytes , pongo abelii , macaca mulatta , mus musculus , rattus norvegicus , equus caballus , canis familiaris , bos taurus , monodelphis domestica , gallus gallus  and taeniopygia guttata .
reconstruction of the boreoeutherian ancestor
procars ran in  <dig> steps and finally returned  <dig> cars with a number of blocks per car ranging from  <dig> to  <dig> .
the total number of adjacencies computed for the boreoeutherian ancestor is  <dig> compared to the  <dig>   <dig>   <dig> adjacencies present in respectively homo sapiens, mus musculus and bos taurus.
number of cars, number of blocks per car, and number of new adjacencies returned at each iteration of procars method.
the numbers of blocks per car are detailed in table  <dig>  the human chromosomal syntenies are 1- <dig>  3- <dig>  4- <dig>  8- <dig>  12- <dig>  14- <dig> and 16- <dig>  in  <cit> , the boreoeuthe-rian ancestor has two more human chromosomal syntenies 7- <dig> and 10-12- <dig>  and all other syntenies were also found by procars.
number of blocks and human chromosomal syntenies  for each car computed by procars.
human chromosomal syntenies involving two human chromosomes are in bold.
comparison with other methods
all the methods  take as input a phylogeny with a tagged ancestral node in this phylogeny, and a set of blocks with the arrangement of the blocks in each extant genome of the phylogeny.
anges  <cit>  first builds a set of potential ancestral features  by comparing pairs of species whose path goes through the tagged ancestral node.
then, an arrangement of the blocks that corresponds to a subset of these adjacencies is built in order to satisfy the consecutive ones property.
this assembling phase requires the length of the branches of the phylogenetic tree.
infercars  <cit>  is based on an adaptation of the fitch parsimony method for adjacencies.
potential neighbors of blocks are modeled through graphs at each node of the phylogenetic tree.
conflicts between potential neighboring relations are resolved using a weight function which requires the length of the branches of the phylogenetic tree.
gapadj  <cit>  works iteratively, detecting new adjacencies at each step by allowing more and more gaps within adjacencies until the maximum number of gaps maxα is reached.
at each step, the assembling of the extended cars is done using a tsp algorithm, and a threshold τ is required to discard the less reliable adjacencies.
as gapadj is the only method with parameters , we ran gapadj on  <dig> sets of parameters for maxα ranging from  <dig> to  <dig>  and τ ranging from  <dig>  to  <dig> .
we then selected the reconstruction that had the minimal breakpoint distance to the ancestor reconstructed by procars.
the breakpoint distance between two genomes is the number of blocks extremities whose neighbors are not conserved in both genomes.
among the  <dig> sets of parameters tested, the closest result is obtained when τ equals  <dig>  and maxα equals  <dig>  giving a breakpoint distance of  <dig>  between this reconstruction and the ancestor reconstructed by procars.
that corresponds to  <dig> % of the block extremities having different neighbors in both reconstructions.
note that the reconstruction selected for gapadj is also the closest to the ancestors reconstructed by infercars and anges.
we then computed the list of adjacencies shared by all the methods and the adjacencies that are specific to a subset of the methods, as shown in figure  <dig>  the number of adjacencies shared by all the methods is  <dig>  the method which infers the highest number of specific adjacencies is gapadj , as suggested by the breakpoint distances shown in figure  <dig>  all adjacencies found by anges are also found by procars, as confirmed by the small breakpoint distance between the two methods.
finally, it is noteworthy that there is no adjacency shared by the three methods anges, infercars and gapadj that is not found by procars.
justification of procars specific adjacencies
adjacency  is found at iteration  <dig> of procars.
in the other methods, the block  <dig> is alone in a single-block car.
this adjacency was detected thanks to a step c) of procars method.
it is then a dcj-reliable adjacency detected as follows: at iteration  <dig>  adjacency  was found, block  <dig> is at the end of car  <dig>  and block  <dig> is at the end of car  <dig>  in bos taurus, the car adjacency  is conserved.
in mus musculus, block adcencies  and  are present.
hence, as the path from bos taurus to mus musculus goes through the ancestor, a potential dcj rearrangement on adjacencies  and  in the ancestor could explain the adjacencies found in mus musculus:  and .
moreover, this adjacency  found by procars is the one supporting the human chromosomal synteny 1- <dig> that was also reported in  <cit>  using a cytogenetic method, but not found by any of the other methods .
for each method, we give which human chromosomal synteny is found.
a number in a cell indicates that the synteny is found but with additionnal part of another chromosome.
adjacency  is found at iteration  <dig>  it is then a conserved adjacency detected as follows: at iteration  <dig>  block  <dig> is alone in a car, and block − <dig> is at the end of a car.
this adjacency  is present, on the one hand, in mus musculus and rattus norvegicus  and on the other hand in equus caballus and bos taurus .
hence, it is a partly-conserved adjacency and, as it is not in conflict with any other conserved adjacency, procars joined  <dig> and  <dig> at iteration  <dig>  in infercars and anges,  <dig> is alone in a car while  <dig> is also at the begining of a car.
therefore, cars found by infercars and anges are not in conflict with the adjacency  that procars added, but no signal was found by those methods to infer this adjacency.
in gapadj,  <dig> is alone in a car while  <dig> is in a car containing .
however,  is only present in species in the ingroup i <dig> .
therefore it is not a conserved adjacency, and that is why procars preferred the partly-conserved adjacency .
justification of adjacencies not found by procars
anges contains no specific adjacency and thus procars found all adjacencies detected by anges.
there are  <dig> adjacencies found by both gapadj and infercars but not by procars.
for adjacency , infercars inferred a unique car which is the concatenation of cars  <dig> and  <dig> of procars involving respectively blocks  <dig> and  <dig>  gapadj also inferred this concatenation of the two procars cars, except a segment of the car involving block  <dig> in procars which is in a separated car.
the  adjacency is only present in homo sapiens, pan troglodytes, pongo abelii and macaca mulatta  and hence cannot be a partly-conserved adjacency.
it is not a dcj-reliable adjacency either.
concerning the adjacency , procars has adjacencies  in car  <dig> while infercars  created adjacencies  in car  <dig> .
the adjacency  is present only in mus musculus and rattus norvegicus  and is hence not a conserved adjacency.
it is not a dcj-reliable adjacency either, otherwise this adjacency would have been detected during iteration  <dig>
human chromosomal syntenies
human syntenies found by other methods are: for anges: 3- <dig>  4- <dig>  8- <dig>  12- <dig>  14- <dig>  16-19; for infercars: 3- <dig>  4- <dig> and 12-22; for gapadj: 2-4- <dig>  3- <dig>  7- <dig>  5-6- <dig>  8- <dig>  10- <dig>  12- <dig> and 16- <dig>  a comparison between the four methods is given in table  <dig> and a karyotype of the ancestral genomes in additional file  <dig>  we can notice that procars returns the closest result to the ancestor reconstructed in  <cit>  using a cytogenetic method.
CONCLUSIONS
infercars is the first method using an adaptation of the fitch algorithm to infer ancestral gene orders based on homology instead of rearrangements.
anges makes use of common intervals to be able to account for micro-rearrangements.
gapadj brings the iterative approach allowing to build cars step by step.
with procars, we propose a new methodology which combines the different approaches found in other methods, using a model based on adjacencies only.
procars has the advantage to be a parameter-free method, without the requirement of branch lengths for the phylogenetic tree.
procars is based on a single definition of contiguity, the car adjacency, that allows some micro-rearrangements under a very simple model.
however, since procars considers only genomes containing the same set of non-duplicated blocks, it does not allow to reconstruct ancestors in the context of duplication or loss events.
in order to select the adjacencies at each step of procars, the adjacencies are classified according to an homoplasy cost instead of using a heuristic assembly algorithm.
procars gives priority to discarding conflicting adjacencies rather than necessarily adding new adjacencies at each step.
the final result of procars is a set of completely resolved cars, for which the arrangements of all the blocks are given.
as for other homology-based methods, procars is not suitable in the case of convergent evolution.
procars is also a greedy algorithm which could be seen as a disadvantage because adjacencies are added permanently at each step.
however, this greediness is balanced by the fact that procars works iteratively and adds only reliable non-conflicting adjacencies at each step.
availability of supporting data
procars is written in python and is available at http://bioinfo.lifl.fr/procars.
the dataset used in section
results and discussion is also available from this web page.
list of abbreviations
tsp: traveling salesman problem; car: contiguous ancestral region; nc: non-conflicting adjacencies; c: conflicting adjacencies; fs: fully-conserved adjacencies; ps: partly-conserved adjacencies; r: retained adjacencies; d: discarded adjacencies.
competing interests
the authors declare that they have no competing interests.
authors' contributions
ap wrote the program and its documentation, ran the experiments, and presented the results at the conference iscb-la' <dig>  ap, jsv, sb and ao analyzed and interpreted the data.
jsv wrote the results section.
ao conceived the study and its design, wrote a prototype of the program, and drafted the manuscript.
ap, jsv and sb critically revised the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
phylogeny of the  <dig> species used in the application.
a figure at the pdf format depicting the phylogeny of the  <dig> species used in the application.
the black node in the phylogeny corresponds to the boreoeutherian ancestor.
click here for file
additional file 2
chromosomal syntenies with the human genome.
a figure at the pdf format depicting the human chromosomal syntenies between the boreoeutherian ancestor found by the four methods procars, infercars, gapadj and anges.
click here for file
acknowledgements
ap's engineer position is supported by a région nord-pas-de-calais funding .
the participation of ap and ao to the conference iscb-la in october  <dig> was funded by inria and université de sherbrooke.
inria provided the funding for publication of the article.
this article has been published as part of bmc genomics volume  <dig> supplement  <dig>  2015: proceedings of the 10th international conference of the brazilian association for bioinformatics and computational biology .
the full contents of the supplement are available online at http://www.biomedcentral.com/bmcgenomics/supplements/16/s <dig>

 the small phylogeny problem consists in reconstructing the ancestral gene orders at the internal nodes of a species tree, given the gene orders of the extant genomes at the leaves of the tree. there exist two main computational approaches for the reconstruction of ancestral gene orders from extant gene orders: rearrangement-based methods, and homology-based methods. the rearrangement-based methods require a rearrangement model, and consist in finding a rearrangement scenario that minimizes the total rearrangement distance on the branches of the species tree. the homology-based methods consist in finding the ancestral gene orders associated with the internal nodes of the species tree, such that the total amount of homoplasy phenomenon observed in the species tree is minimized. homoplasy is a phenomenon by which two genomes in different lineages acquire independently a same feature that is not shared and derived from a common ancestor. for the inference of the ancestral gene order at a tagged internal node, the homology-based methods are usually composed of two steps. the first step consists in detecting a set of potential ancestral contiguity features, by comparison of pairs of extant genomes whose path goes through the ancestor in the species tree. the second step is an assembling phase that requires to compute an accurate conservation score for each potential ancestral feature, based on the species tree. using these scores, some heuristic algorithms are then used to resolve the conflicts between the ancestral features in order to assemble them into contiguous ancestral regions. a car of an ancestral genome is an ordered sequence of oriented blocks that potentially appear consecutively in this ancestral genome. in the absence of tangible evolution model, the homology-based methods have the convenience to reconstruct cars that contain only reliable features inferred from a conservation signal observed in the extant genomes. however, the ancestral genomes reconstructed using homology-based methods are often not completely assembled, as some rearrangement or content-modifying events might have caused the loss of some ancestral contiguity features in the extant genomes. thus, the homology-based methods proposed in the literature usually enlarge the condition of contiguity in order to detect more potential ancestral contiguity features, -adjacencies between two blocks, maximum common intervals of blocks, gapped adjacencies. hence, these different types of contiguity features can be classified according to the tightness of their definition of contiguity. the homology-based methods should then account for this classification when assembling different types of contiguity features. this approach was used in where a method, gapadj, was presented for iteratively detecting gapped adjacencies. gapadj uses a progressively relaxed definition of contiguity allowing an increasing number of gaps between ancestral contiguous synteny blocks in extant genomes, and iteratively assembling these gapped adjacencies using a heuristic traveling salesman algorithm. the tsp is applied on a graph whose vertices are synteny blocks, and edges are potential ancestral adjacencies between these blocks. here, we follow the same idea, and we present an homology-based method that is based on iteratively detecting and assembling ancestral adjacencies, while allowing some micro-rearrangements of synteny blocks at the extremities of the progressively assembled cars. the method starts with a set of non-duplicated blocks as the initial set of cars, and detects iteratively the potential ancestral adjacencies between extremities of cars, while building up the cars progressively by adding, at each step, new non-conflicting adjacencies that induce the less homoplasy phenomenon. the species tree is used, in some additional internal steps, to compute a score for the remaining conflicting adjacencies, and to detect other reliable adjacencies, in order to reach completely assembled ancestral genomes. the first originality of the method comes from the usage of the progressively assembled cars for the detection of ancestral contiguity features allowing micro-rearrangements. the second originality comes from the assembling method at each iterative step that consists in adding the contiguity features gradually giving priority to the features that minimize the homoplasy phenomenon, rather than relying on a heuristic algorithm for discarding false-positive features. we discuss the usefulness of the method through a comparison with three other homology-based methods on the same real dataset of amniote genomes for the reconstruction of the boreoeutherian genome. preliminaries: genomes, species tree, conserved adjacencies for the reconstruction of ancestral genomes from extant ones, genomes are represented by identifying homologous conserved segments along their dna sequences, called synteny blocks. these blocks can be relatively small, or very large fragments of chromosomes. the order and orientation of the blocks, and their distribution on chromosomes may vary in different genomes. a signed block is a block preceded by a sign + or − representing its orientation. by convention, a signed block +a is simply written a. here we assume that all genomes contain the same set of non-duplicated blocks and consist of several circular or linear chromosomes composed of signed blocks. for example, consider the five genomes represented at the leaves of the tree in figure the bullets at the extremities of the chromosomes represent the telomeres of linear chromosomes. genomes a and b consist of one linear chromosome each, and genomes c, d, and e consist of two linear chromosomes each. a contiguous ancestral region is defined as a potential chromosome of an ancestral genome. a segment in a genome is an ordered set of signed blocks that appear consecutively in the genome. the length of a segment is the number of blocks composing this segment. in the above example, {b c d e} is a segment of length in the genome a. two segments of two different genomes are called syntenic segments if they contain the same set of blocks. for example, the segments {h −g − f d} of genome d and {−d f g h} of genome e are syntenic. an adjacency in a genome is an ordered pair of two consecutive signed blocks. for example, in the above genomes, is an adjacency of genomes a, b, c, and e, and is an adjacency of genome b. since a whole chromosome or a segment can always be flipped, we have =. for example, = is an adjacency shared by genomes b, c, and d. a species tree on a set of k genomes is a rooted tree with k leaves, where each genome is associated with a single leaf of the tree, and the internal nodes of the tree represent ancestral genomes. for example, figure shows a species tree on genomes a, b, c, d, and e. here, for the reconstruction of ancestral gene orders, we consider an ancestral node of the species tree that has exactly two children resulting from a speciation. the species partition defined by an ancestral node is the partition of the extant species into three sets: two ingroup sets i and i corresponding to the two lineages descending from the ancestor, and one outgroup set o containing all other extant genomes. a conserved adjacency at an ancestral node of the species tree is an adjacency shared by at least two genomes belonging to at least two different sets of the species partition defined by the ancestral node. such two genomes are linked by a path that goes through the ancestral node. for example, in figure is a conserved adjacency of the black-colored ancestral node because it is shared by genomes c and e whose path goes through the ancestor. the adjacency is also a conserved adjacency of this ancestor because of its presence in genomes d and e. a conserved adjacency at an ancestral node is considered as a potential adjacency of this ancestor. homology-based methods for the reconstruction of ancestral gene orders usually consist in, first, detecting all the conserved adjacencies at the ancestral node, and next, assembling these conserved adjacencies into cars. the difficulty in this assembling phase comes from the conflicts that may exist between some conserved adjacencies. two adjacencies are called conflicting adjacencies when they involve a same block extremity, and thus they cannot be both present in the same ancestral genome. for example, in figure the conserved adjacencies and of the black-colored node are conflicting as they both involve the right extremity of block g. two adjacencies that are not conflicting are called compatible. a set of adjacencies is said non-conflicting if all pairs of adjacencies in the set are compatible. here, we distinguish two types of conserved adjacency regarding their presence or absence in the three sets of species defined by the considered ancestral node: the two ingroup sets i and i and the outgroup set o. a fully-conserved adjacency is a conserved adjacency that is present in at least one genome of each of the three sets of species. a partly-conserved adjacency is any other conserved adjacency. for example, in figure is a fully-conserved adjacency of the black-colored ancestral node, while all other conserved adjacencies are partly-conserved adjacencies. the homoplasy cost of an adjacency at a given ancestral node a counts the number of branches linked to this ancestor on which the adjacency would have been gained or lost if it was present in the ancestor. it is defined as follows: it is either if the adjacency is fully-conserved at a, or if it is partly-conserved at a, or if it is present in only one of the sets i i and o, or if it is present in none of these sets. note that if an adjacency has an homoplasy cost of or at the ancestral node a, then the adjacency is not conserved at this node. for example, in figure the adjacency has a cost the adjacency a cost the adjacency a cost while the adjacency has a cost method the homology-based problem considered in this paper for the reconstruction of ancestral gene orders can be stated as follows: problem. given a species tree on a set of extant genomes, each composed of the same set of blocks, and given an ancestral node in this species tree, find a set of cars at the ancestral node, with a maximum number of adjacencies, that minimizes the total homoplasy cost. compared to other homology-based methods for the reconstruction of ancestral gene orders, the progressive method presented in the following consists in adding adjacencies progressively, as opposed to discarding false adjacencies in a single assembling step. a global description of the progressive method steps is presented in the following, and the refined descriptions are presented next. inputs and start the input of the method is a phylogeny with a tagged ancestral node whose block order is to be reconstructed, and a set of n orthologous blocks that are used to describe the block orders of the genomes at the leaves of the tree. the initialization of the method consists in starting with an initial set of n cars, each composed of a single block. overall idea the core of the method relies on iteratively computing new block adjacencies in order to concatenate cars progressively. at each step, a set of potential adjacencies is first detected, then the method selects a subset of non-conflicting adjacencies that are added to the current cars. the following three steps are used iteratively in order to collect the ancestral adjacencies: step a) consists in detecting the conserved adjacencies and the homoplasy costs of these adjacencies are used to classify and select a subset of non-conflicting adjacencies to be added in current cars; step b) consists in resolving conflicts between adjacencies and selecting a subset of non-conflicting adjacencies to be added in current cars; step c) consists in detecting some adjacencies not conserved at the ancestral node, but supported by putative genome rearrangement events. in the next paragraphs, we briefly give an overview of each of these steps. a) adding non-conflicting conserved adjacencies this step comes after the initialization phase, or after a step a), or b) or c) that ended up with a non-empty set of added adjacencies. the step begins with the detection of the conserved adjacencies between the current cars at the ancestral node. next, the non-conflicting fully-conserved adjacencies are selected in a first phase. then, the non-conflicting partly-conserved adjacencies that are compatible with all fully-conserved adjacencies are added in a second phase. the set of all conserved adjacencies added in the cars in this step is denoted by nc. it constitutes a non-conflicting set of adjacencies. the conserved adjacencies not added in this step are stored in a set c and tagged as conflicting adjacencies for a next step b). b) resolving conflicts between adjacencies this step comes after a step a) that ended up with an empty set nc, and a non-empty set c. it considers the set c of adjacencies tagged as conflicting in this last step a). a cost, different from the homoplasy cost, is computed for each of these adjacencies, and a non-conflicting subset cm of c that has a maximum size and minimizes the sum of the adjacencies costs is computed. this subset of adjacencies is added in the cars, and the remaining adjacencies of the set c−cm are discarded permanently. c) detecting dcj-reliable adjacencies this step comes after a step a) that ended up with an empty set nc, and an empty set c. it consists in finding new potential adjacencies that are not conserved at the ancestral node. each of these new potential adjacencies is supported by the presence of an adjacency in the current set of cars, and two adjacencies in an extant genome g, such that those three adjacencies completed by the new potential adjacency induce a single genome rearrangement event, specifically double-cut-and-join events, between the ancestral genome and the genome g. a maximum size non-conflicting subset of the new potential adjacencies is added in the cars, and the remaining adjacencies are discarded permanently. we now give the detailed descriptions of step a), b) and c). step a): detection of non-conflicting conserved adjacencies in this section, we first explain how the conserved adjacencies are defined. next, we describe how a subset of non-conflicting adjacencies is selected by giving priority to the fully-conserved adjacencies. detection of the conserved adjacencies we begin by stating the definition of a car adjacency in an extant genome at a leaf of the species tree, given the set of cars in the current step of the method. let us recall that a car is an oriented sequence of signed blocks. we denote by |x| the block corresponding to a signed block x in a car. a signed car is a car possibly preceded by − indicating its reverse orientation. for example, if car_x = {a −b c}, then -car_x = {−c b − a}. let car_a and car_b be two signed cars in the current set of cars with car_a = {a a... an} and car_b = {b b... bm}. the ordered pair is a car adjacency in an extant genome g if there exists a pair of segments sa and sb consecutive in genome g such that the segment sa contains only blocks from car_a, and satisfies the following constraints: i.) sa is either the segment {an}, else ii) a segment of length na > ending with the block |an|, else iii) a segment syntenic to a segment of car_a containing the block |an|, i) sb is either the segment {b1}, else ii) a segment of length nb > starting with the block |b1|, else iii) a segment syntenic to a segment of car_b containing the block |b1|. as for the blocks, the car adjacency is equivalent to. for example, consider the following three cars composed of ten blocks: car_ = • a b c •; car_ = • d e f g •; car_ = • h i j •. the genome g = • b c −d f •; • e −g i j a −h • has three car adjacencies:,, and. the pair is a car adjacency because of segment s = {c} and s = {−d f } that are consecutive in the genome g, and such that s satisfies the constraint i) and s satisfies the constraint ii). the car adjacency is supported by the segments s = {e −g} satisfying ii) and s = {i j} = {−j −i} satisfying iii). the car adjacency is supported by the segments s = {j} satisfying i) and s = {a} satisfying i). the block adjacency corresponding to the car adjacency with car_a = {a a... an} and car_b = {b b... bm} is the adjacency. in the previous example, the block adjacencies corresponding to, and are respectively,, and. proposition let car_a = {a a... an} be a signed car in the current set of cars. an extant genome g has at most two car adjacencies of the form. proof let us suppose that an extant genome g has more than two car adjacencies of the form. say,, and are three of them. these car adjacencies would be supported by 1) three pairs of consecutive segments on g,,,, such that 2) sa sa sa contain the block |an|, and 3) sx, sy, sz are non-intersecting segments since they belong to three different cars. it is impossible to find an ordering of the six segments on g such that the constraints 1), 2) and 3) are all satisfied simultaneously. thus, the genome g contains at most two car adjacencies of the form.   □ remark the definitions of fully or partly conserved adjacencies are naturally extended to car adjacencies as follows: a conserved car adjacency at an ancestral node of the species tree is a car adjacency shared by at least two extant genomes that belong to at least two different sets of the species partition defined by the ancestral node. a fully-conserved car adjacency is a conserved car adjacency belonging to at least one genome of each of the three sets of the species partition defined by the ancestral node. a partly-conserved car adjacency is any other conserved car adjacency. the homoplasy cost associated to a car adjacency is a natural extension of the definition given for the block adjacencies. classification and selection of the conserved adjacencies the overall idea of this phase is to select conserved adjacencies while giving priority to the fully-conserved adjacencies, and to the adjacencies that have the less conflicts with other adjacencies. let s be the set of block adjacencies corresponding to the conserved car adjacencies at the ancestral node. in the sequel, the abbreviations fs, ps, nc, c stand for fully, partly, non-conflicting, and conflicting conserved adjacencies respectively. figure shows the organization of the sets of adjacencies that are considered in this phase. let fs and ps be the subsets of s that contain respectively the fully-conserved adjacencies and the partly-conserved adjacencies. thus, s = fs ∪ ps and fs ∩ ps = ∅. first, we consider the fully-conserved adjacencies. let fs_nc be the subset of fs that contains the adjacencies that are compatible with all other adjacencies in fs. the corresponding set of conflicting adjacencies is fs_c = fs - fs_nc. the fully-conserved non-conflicting adjacencies contained in the set fs_nc are automatically retained to be added in the cars. thus, in the following, any adjacency that is in conflict with some adjacencies of fs_nc will be discarded permanently. next, we consider the partly-conserved adjacencies. let ps_d be the subset of ps containing adjacencies that are in conflict with some adjacencies of fs_nc, and ps_r be the set of the remaining adjacencies in ps. thus, ps_r = ps - ps_d. the adjacencies of ps_d are discarded permanently, as explained previously in. let ps_nc be the subset of ps_r that contains the adjacencies that are compatible with all other adjacencies in ps_r. the corresponding set of conflicting adjacencies is ps_c = ps_r - ps_nc. finally, since the priority is given to fully-conserved adjacencies, we want to retain only the adjacencies of ps_nc that are not in conflict with the adjacencies of the set fs. let ps_nc be the subset of ps_nc that contains the adjacencies that are compatible with all the adjacencies in fs. the partly-conserved non-conflicting adjacencies contained in the set ps_nc are also retained automatically to be added in the cars. it follows that the set of retained adjacencies nc = fs_nc ∪ ps_nc is a set of non-conflicting adjacencies. this step a) of the method adds the set of adjacencies nc to the current cars of the ancestral genome, and updates the current set of conflicting adjacencies to the set c = s - ps_d − nc. by construction, each adjacency contained in the set c is in conflict with at least one other adjacency of c, and compatible with all the adjacencies contained in the set nc. the step a) can be recalled several times consecutively as far as the set nc of added adjacencies is not empty. we now state a proposition ensuring that the current set of conflicting adjacencies c misses no previously found conflicting adjacency such that the signed block a is the end of a signed car, and the signed block b is the start of a signed car in the current set of cars. proposition let be an adjacency corresponding to a conserved car adjacency found in a previous step a) of the method. the adjacency is either present in the current set of cars, or is in conflict with an adjacency present in the current set of cars, or is also found in the current step a) i.e ∈ s. proof say that, in a previous step a), the adjacency was supported by the detection of a conserved car adjacency present in a subset g of the extant genomes. 1) if there exist in the current set of cars, a signed car car_a ending with the signed block a, and a signed car car_b starting with the signed block b, then the car adjacency is also found in the same set  g of extant genomes. thus, the adjacency is also found in the current step. 2) otherwise, either there exists an adjacency of the form or in the current set of cars in conflict with the adjacency, or the adjacency is present in the current set of cars.   □ step b): resolution of conflicts between adjacencies this step considers a conflicting set c of adjacencies obtained at the end of a previous step a), and computes a non-conflicting subset of the set c to be added in the current set of cars. definition of the cost of adjacencies we begin by stating the definition of the cost of an adjacency in this step. the mutation cost of a labeling of the nodes of a species tree on a given alphabet is the number of edges in the tree having two different labels at their extremities. here, the cost of an adjacency ∈ c is the minimum mutation cost of a labeling of the nodes of the species tree on a binary alphabet { 1} such that the ancestral node is labeled with the extant species nodes, where corresponds to a car adjacency, are labeled with and the other extant species nodes are labeled with in other terms, an adjacency has two possible states in a genome: present or absent. the cost of an adjacency is the minimum number of changes of state necessary to explain the evolutionary history of the adjacency along the species tree, with the adjacency being present at the ancestral node. for example, the costs of the two conflicting conserved adjacencies and shown in figure are and respectively. figure shows two minimum mutation cost labelings of the nodes of the species tree corresponding to both adjacencies. computation of the non-conflicting subset of adjacencies the cost of a set of adjacencies is the sum of the costs of the adjacencies composing this set. let m be the maximum size of a non-conflicting subset of the conflicting set c of adjacencies. this step b) finds a non-conflicting subset cm of c of size m and minimum cost. the set of adjacencies cm is added to the current cars of the ancestral genome, and the remaining adjacencies in the set c − cm are discarded permanently. remark note that the adjacencies of the set c − cm discarded in this step will never be detected again, since these adjacencies are in conflict with the adjacencies of the set cm added in the current step. step c): detection of dcj-reliable adjacencies this step considers the current set of cars, and computes new potential adjacencies not conserved, but supported by putative ancestral rearrangement events. a double-cut-and-join rearrangement event on a genome consists in the cut of two adjacencies of the genome in order to glue the four exposed extremities in a different way. for example, a dcj event on the genome a = that cuts the adjacencies and to obtain the adjacencies and produces the genome b =. we now give the definition of potential ancestral adjacencies that can be inferred from putative genome rearrangements inspired from the definitions of reliable adjacencies in. here, we add the constraint that the signal of the reliable adjacency must be conserved on a path of the species tree that goes through the ancestor. let car_a and car_b be two signed cars in the current set of cars with car_a = {a a... an} and car_b = {b b... bm}. the adjacency is a dcj-reliable adjacency of the ancestral node if there exists an adjacency in the current set of cars such that the adjacencies and are present in an extant genome g and is a car adjacency in an extant genome g such that the genomes g and g belong to two different sets of the species partition defined by the ancestral node. the potential presence of the adjacency in the ancestral genome induces a dcj event that has cut the adjacencies and in the ancestral genome to produce the adjacencies and in the extant genome g an example is given in section results and discussion. in this step of the method, a maximum size non-conflicting subset of the dcj-reliable adjacencies is added in the cars, and the remaining dcj-reliable adjacencies are discarded permanently. remark note that the homoplasy cost of a dcj reliable adjacency is always  we used procars to compute a set of cars for the boreoeutherian ancestral genome using the block orders of twelve amniote genomes, and we compared the result with the ancestors reconstructed by three other homology-based methods: anges, infercars and gapadj. orthology blocks and phylogeny we chose twelve genomes completely assembled and present in a pecan multiple alignment of amniote genomes available in the release of the ensembl compara database. the phylogenetic tree was directly infered from the classifications of the species obtained from the national center for biotechnology information taxonomy database. we constructed a set of synteny blocks using the multiple alignments as seeds. we used the block construction method described in, keeping only the seeds that had an occurrence in each of the twelve genomes, removing the seeds that spanned less than 100kb, and joining seeds collinear in all genomes. this resulted in a set of genomes composed of blocks for species homo sapiens, pan troglodytes, pongo abelii, macaca mulatta, mus musculus, rattus norvegicus, equus caballus, canis familiaris, bos taurus, monodelphis domestica, gallus gallus and taeniopygia guttata. reconstruction of the boreoeutherian ancestor procars ran in steps and finally returned cars with a number of blocks per car ranging from to. the total number of adjacencies computed for the boreoeutherian ancestor is compared to the adjacencies present in respectively homo sapiens, mus musculus and bos taurus. number of cars, number of blocks per car, and number of new adjacencies returned at each iteration of procars method. the numbers of blocks per car are detailed in table the human chromosomal syntenies are 1- 3- 4- 8- 12- 14- and 16- in, the boreoeuthe-rian ancestor has two more human chromosomal syntenies 7- and 10-12- and all other syntenies were also found by procars. number of blocks and human chromosomal syntenies for each car computed by procars. human chromosomal syntenies involving two human chromosomes are in bold. comparison with other methods all the methods take as input a phylogeny with a tagged ancestral node in this phylogeny, and a set of blocks with the arrangement of the blocks in each extant genome of the phylogeny. anges first builds a set of potential ancestral features by comparing pairs of species whose path goes through the tagged ancestral node. then, an arrangement of the blocks that corresponds to a subset of these adjacencies is built in order to satisfy the consecutive ones property. this assembling phase requires the length of the branches of the phylogenetic tree. infercars is based on an adaptation of the fitch parsimony method for adjacencies. potential neighbors of blocks are modeled through graphs at each node of the phylogenetic tree. conflicts between potential neighboring relations are resolved using a weight function which requires the length of the branches of the phylogenetic tree. gapadj works iteratively, detecting new adjacencies at each step by allowing more and more gaps within adjacencies until the maximum number of gaps maxα is reached. at each step, the assembling of the extended cars is done using a tsp algorithm, and a threshold τ is required to discard the less reliable adjacencies. as gapadj is the only method with parameters, we ran gapadj on sets of parameters for maxα ranging from to and τ ranging from to. we then selected the reconstruction that had the minimal breakpoint distance to the ancestor reconstructed by procars. the breakpoint distance between two genomes is the number of blocks extremities whose neighbors are not conserved in both genomes. among the sets of parameters tested, the closest result is obtained when τ equals and maxα equals giving a breakpoint distance of between this reconstruction and the ancestor reconstructed by procars. that corresponds to % of the block extremities having different neighbors in both reconstructions. note that the reconstruction selected for gapadj is also the closest to the ancestors reconstructed by infercars and anges. we then computed the list of adjacencies shared by all the methods and the adjacencies that are specific to a subset of the methods, as shown in figure the number of adjacencies shared by all the methods is the method which infers the highest number of specific adjacencies is gapadj, as suggested by the breakpoint distances shown in figure all adjacencies found by anges are also found by procars, as confirmed by the small breakpoint distance between the two methods. finally, it is noteworthy that there is no adjacency shared by the three methods anges, infercars and gapadj that is not found by procars. justification of procars specific adjacencies adjacency is found at iteration of procars. in the other methods, the block is alone in a single-block car. this adjacency was detected thanks to a step c) of procars method. it is then a dcj-reliable adjacency detected as follows: at iteration adjacency was found, block is at the end of car and block is at the end of car in bos taurus, the car adjacency is conserved. in mus musculus, block adcencies and are present. hence, as the path from bos taurus to mus musculus goes through the ancestor, a potential dcj rearrangement on adjacencies and in the ancestor could explain the adjacencies found in mus musculus: and. moreover, this adjacency found by procars is the one supporting the human chromosomal synteny 1- that was also reported in using a cytogenetic method, but not found by any of the other methods. for each method, we give which human chromosomal synteny is found. a number in a cell indicates that the synteny is found but with additionnal part of another chromosome. adjacency is found at iteration it is then a conserved adjacency detected as follows: at iteration block is alone in a car, and block − is at the end of a car. this adjacency is present, on the one hand, in mus musculus and rattus norvegicus and on the other hand in equus caballus and bos taurus. hence, it is a partly-conserved adjacency and, as it is not in conflict with any other conserved adjacency, procars joined and at iteration in infercars and anges, is alone in a car while is also at the begining of a car. therefore, cars found by infercars and anges are not in conflict with the adjacency that procars added, but no signal was found by those methods to infer this adjacency. in gapadj, is alone in a car while is in a car containing. however, is only present in species in the ingroup i. therefore it is not a conserved adjacency, and that is why procars preferred the partly-conserved adjacency. justification of adjacencies not found by procars anges contains no specific adjacency and thus procars found all adjacencies detected by anges. there are adjacencies found by both gapadj and infercars but not by procars. for adjacency, infercars inferred a unique car which is the concatenation of cars and of procars involving respectively blocks and gapadj also inferred this concatenation of the two procars cars, except a segment of the car involving block in procars which is in a separated car. the adjacency is only present in homo sapiens, pan troglodytes, pongo abelii and macaca mulatta and hence cannot be a partly-conserved adjacency. it is not a dcj-reliable adjacency either. concerning the adjacency, procars has adjacencies in car while infercars created adjacencies in car. the adjacency is present only in mus musculus and rattus norvegicus and is hence not a conserved adjacency. it is not a dcj-reliable adjacency either, otherwise this adjacency would have been detected during iteration human chromosomal syntenies human syntenies found by other methods are: for anges: 3- 4- 8- 12- 14- 16-19; for infercars: 3- 4- and 12-22; for gapadj: 2-4- 3- 7- 5-6- 8- 10- 12- and 16- a comparison between the four methods is given in table and a karyotype of the ancestral genomes in additional file we can notice that procars returns the closest result to the ancestor reconstructed in using a cytogenetic method.  infercars is the first method using an adaptation of the fitch algorithm to infer ancestral gene orders based on homology instead of rearrangements. anges makes use of common intervals to be able to account for micro-rearrangements. gapadj brings the iterative approach allowing to build cars step by step. with procars, we propose a new methodology which combines the different approaches found in other methods, using a model based on adjacencies only. procars has the advantage to be a parameter-free method, without the requirement of branch lengths for the phylogenetic tree. procars is based on a single definition of contiguity, the car adjacency, that allows some micro-rearrangements under a very simple model. however, since procars considers only genomes containing the same set of non-duplicated blocks, it does not allow to reconstruct ancestors in the context of duplication or loss events. in order to select the adjacencies at each step of procars, the adjacencies are classified according to an homoplasy cost instead of using a heuristic assembly algorithm. procars gives priority to discarding conflicting adjacencies rather than necessarily adding new adjacencies at each step. the final result of procars is a set of completely resolved cars, for which the arrangements of all the blocks are given. as for other homology-based methods, procars is not suitable in the case of convergent evolution. procars is also a greedy algorithm which could be seen as a disadvantage because adjacencies are added permanently at each step. however, this greediness is balanced by the fact that procars works iteratively and adds only reliable non-conflicting adjacencies at each step. availability of supporting data procars is written in python and is available at http://bioinfo.lifl.fr/procars. the dataset used in section results and discussion is also available from this web page. list of abbreviations tsp: traveling salesman problem; car: contiguous ancestral region; nc: non-conflicting adjacencies; c: conflicting adjacencies; fs: fully-conserved adjacencies; ps: partly-conserved adjacencies; r: retained adjacencies; d: discarded adjacencies. competing interests the authors declare that they have no competing interests. authors' contributions ap wrote the program and its documentation, ran the experiments, and presented the results at the conference iscb-la' ap, jsv, sb and ao analyzed and interpreted the data. jsv wrote the results section. ao conceived the study and its design, wrote a prototype of the program, and drafted the manuscript. ap, jsv and sb critically revised the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 phylogeny of the species used in the application. a figure at the pdf format depicting the phylogeny of the species used in the application. the black node in the phylogeny corresponds to the boreoeutherian ancestor. click here for file additional file 2 chromosomal syntenies with the human genome. a figure at the pdf format depicting the human chromosomal syntenies between the boreoeutherian ancestor found by the four methods procars, infercars, gapadj and anges. click here for file acknowledgements ap's engineer position is supported by a région nord-pas-de-calais funding. the participation of ap and ao to the conference iscb-la in october was funded by inria and université de sherbrooke. inria provided the funding for publication of the article. this article has been published as part of bmc genomics volume supplement 2015: proceedings of the 10th international conference of the brazilian association for bioinformatics and computational biology. the full contents of the supplement are available online at http://www.biomedcentral.com/bmcgenomics/supplements/16/s 
the rearrangement-based methods consist in minimizing a total rearrangement distance on the branches of a species tree. the homology-based methods consist in the detection of a set of potential ancestral contiguity features, followed by the assembling of these features into contiguous ancestral regions. in the context of ancestral gene order reconstruction from extant genomes, there exist two main computational approaches: rearrangement-based, and homology-based methods. in this paper, we present a new homology-based method that uses a progressive approach for both the detection and the assembling of ancestral contiguity features into cars. ancestral gene orders reconstructionsmall phylogeny problemboreoeutherian ancestor28- october x-meeting - international conference on the brazilian association for bioinformatics and computational biology belo horizonte, brazil the method is based on detecting a set of potential ancestral adjacencies iteratively using the current set of cars at each step, and constructing cars progressively using a 2-phase assembling method.
 in the context of ancestral gene order reconstruction from extant genomes, there exist two main computational approaches: rearrangement-based, and homology-based methods. the rearrangement-based methods consist in minimizing a total rearrangement distance on the branches of a species tree. the homology-based methods consist in the detection of a set of potential ancestral contiguity features, followed by the assembling of these features into contiguous ancestral regions.  in this paper, we present a new homology-based method that uses a progressive approach for both the detection and the assembling of ancestral contiguity features into cars. the method is based on detecting a set of potential ancestral adjacencies iteratively using the current set of cars at each step, and constructing cars progressively using a 2-phase assembling method.  we show the usefulness of the method through a reconstruction of the boreoeutherian ancestral gene order, and a comparison with three other homology-based methods: anges, infercars and gapadj. the program, written in python, and the dataset used in this paper are available at http://bioinfo.lifl.fr/procars/. ancestral gene orders reconstructionsmall phylogeny problemboreoeutherian ancestor28- october x-meeting - international conference on the brazilian association for bioinformatics and computational biology belo horizonte, brazil 