# Validation of Automated Chromosome Recovery in the Reconstruction of Ancestral Gene Order
## 6 Simulations
### Parameters for Simulations
```
input :\(anc\) and \(anct\), arrays of integers defining the ancestor-descendant relations in \(Tr\), a fully labelled binary branching phylogeny \(r_{h}\) and \(r_{k}\), integers representing the number of WGD on the branch leading to extant genome \(h\) or ancestor genome \(k\), respectively \(M(H,J)\), matrix of integers representing the number of genes in each gene family in extant genomes calculated from real data, where \(H\) is the number of extant genomes, \(l\) is the total number of gene families \(\textbf{output}\):\(N(I\times J)\), matrix of integers representing the number of genes in each gene family in ancestral genomes, where \(I\) is the number of ancestors in \(Tr\), \(J\) is the total number of gene families in each ancestor
1 initialize \(N(1\times J)\gets 1\) and \(N(k\times J)\gets r_{k}N((k-1)\times J)\) for all \(J\) gene families;
2 initialize cost penalties \(a,b,c,d\);
3 minimize \(\textbf{cost}\leftarrow\sum_{j=1}^{J}(\sum_{h=1}^{H}\textbf{cost}_{1}(h,j)+ \sum_{k=1}^{K}\textbf{cost}_{2}(k,j))\) to obtain optimal \(a,b,c,d\), where \(\textbf{cost}_{1}\) and \(\textbf{cost}_{2}\) are defined in Equations (2) and 3 respectively;
4 forgene family \(j\gets 1\) to \(J\)do
5 minimize \(\textbf{cost}_{j}\leftarrow\sum_{h=1}^{H}\textbf{cost}_{1}(h,j)+\sum_{k=1}^{K} \textbf{cost}_{2}(k,j)\) to obtain \(N(i,j)\) using nonlinear programming with respect to \(N(k,j)\) for ancestor \(k\) and optimal \(a,b,c,d\);
6
7 end for return \(N(I\times J)\), array of integers representing gene family sizes in the ancestors;
```  
**Algorithm 2**Estimate optimal gene family sizes in simulated ancestral genomes. The simulation is very dependent on its starting point, namely, the chromosomes of Ancestor 1, and their gene content. True, RACCROCHE reconstructs a version of Ancestor 1, but its basis in the contigs constructed by MWM means that each gene family occurs at most once. However, real gene family sizes vary within a genome, and the distribution of these sizes on Ancestor 1 will have an important influence on the simulation of the set of extant genomes. To simulate Ancestor 1, we thus try to associate gene family sizes for each of the genes determined by the RACCROCHE reconstruction. For this, we make use of the distributions of family sizes in the extant genomes. We define two cost matrices, \(\textbf{cost}_{1}(H\times I)\) for extant genomes and \(\textbf{cost}_{2}(I\times I)\) for ancestral genomes, that help us determine the gene family sizes of the ancestral chromosomes, essential for ensuring our simulations mirror as closely as possible the evolutionary processes we inferred for the real data. In considering a gene family \(i\), we define a quantity \(\Delta\) that measures the difference between the number of genes in it generated by zero, one or more WGDs, \(r_{h}\times N(anc(h),j)\) and the number we previously posited for this family \(M(h,j)\) in the case of extant genomes, or \(r_{k}\times N(anct(k),j)\) and \(N(k,j)\) in the case of ancestral genomes. Then, depending on whether \(\Delta\) represents a gene loss or gain, we assign a specific cost, \(a,b,c\) or \(d\). We then minimize the total cost to optimize the cost parameters, and then to optimize the \(N(k,j)\). \[\textbf{cost}_{1}(h,j)=\left\{ \begin{array}{ll}a(1+\log_{2}(-\Delta))&\text{ if } \Delta<0,(\text{cost of generating too many genes}),\\ b(1+\log_{2}\Delta)&\text{ if }\Delta>0,(\text{cost of generating too few genes}),\\ 0&\text{ if }\Delta=0,\end{array} \right. \tag{2}\]  
where \(\Delta\gets M(h,j)-r_{h}\times N(anc(h),j)\). \[\textbf{cost}_{2}(k,j)=\left\{ \begin{array}{ll}c(1+\log_{2}(-\Delta))& \text{ if }\Delta<0,(\text{cost of generating too many genes}),\\ d(1+\log_{2}\Delta)&\text{ if }\Delta>0,(\text{cost of generating too few genes}),\\ 0&\text{ if }\Delta=0.\end{array} \right. \tag{3}\]  
where \(\Delta\gets N(k,j)-r_{k}\times N(anct(k),j)\).