# Validation of Automated Chromosome Recovery in the Reconstruction of Ancestral Gene Order
## 2 Raccroche  
We first sketch our algorithm for ancestral plant genome inference, RACCROCHE, Reconstruction of **AnC**estral **CO**ntigs and **CH**romosomEs [5], including reconstruction of the intermediate ancestral genomes giving rise to modern species, designed with a particular focus on flowering plant evolution. The strategy implemented in this approach combines the following components:  
1. In Line 1 of Algorithm 1, the replacement of the traditional selection of one-to-one orthologs among input genomes, as a first step, by the identification of many-to-many correspondences among gene families of limited size within these genomes from pairwise SynMap [6; 7] comparisons. 2. In Line 3, the use of generalized adjacencies [8; 9], namely, any pair of genes close to each other within a predefined window size on a chromosome, instead of just immediately adjacent genes. 3. In Lines 6-7, the compilation of oriented candidate adjacencies at each of the ancestral nodes of a given binary branching tree phylogeny using the \"safe\" criterion that such an adjacency must be evidenced in genomes in two or three of the subtrees connected by this node, not just one or none. 4. In Lines 8-9, the large set of these candidates is then resolved, at each node, by maximum weight matching (MWM) to give an optimally compatible subset, which ipso facto defines linearly (or circularly) compatible \"contigs\" of the ancestral genomes to be constructed, thus avoiding the branching segments that plague other methods [10]. Use of MWM for ancestral gene order reconstruction was introduced some time ago, but with modest results [11]. 5. In Line 10, local sequence matching, satisfying proximity and contiguity conditions, of each ancestral contig on all of the chromosomes of the extant genomes, followed in Line 11 by the construction of a total chromosomal co-occurrence matrix of contigs belonging to each ancestral node. 6. In Line 12, a clustering applied to the co-occurrence matrix. This is then decomposed into chromosomal sets of closely clustered contigs. Within each contig, the order of the genes is already predetermined by the MWM step. Ordering the contigs along the chromosomes is carried out by a linear ordering algorithm. ```
input :\(\mathit{Tr}\), an unrooted binary branching phylogeny \(H\), the number of annotated extant genomes related by \(\mathit{Tr}\) \(W\), size of window including all generalized adjacencies output :reconstructed ancestral chromosomes
1 generate gene families from pairwise SynMap comparisons of extant genomes;
2 forgenome\(i\gets 1\)to\(H\)do
3 list all generalized adjacencies occurring within a window of a preset size \(W\);
4 end for
5 foreachancestor in \(\mathit{Tr}\)do
6 assign adjacency weights as the number of subtrees connected by a branch to _ancestor_, containing at least one occurrence of the adjacency;
7 select candidate adjacencies with weights 2 or 3;
8 construct an adjacency graph from the candidate adjacencies;
9 construct contigs using Maximum Weight Matching from the adjacency graph;
10 match contigs to extant genomes;
11 count the frequency of co-occurrence of contigs on extant chromosomes;
12 cluster ancestral contigs into ancestral chromosomes according to contig co-occurrence;
13 end for
```  
**Algorithm 1**RACCROCHE--reconstruction of ancestral contigs and chromosomesThe last two steps, leading to the reconstruction of a set of distinct chromosomes, without any projection on, or even reference to, the gross chromosomal architecture of the extant genomes, seem entirely novel. Moreover, the utilization of generalized adjacencies and gene family size restrictions is an innovation inspired by the particular case of plants, in the context of widespread and recurrent whole genome duplication (WGD) and fractionation.