# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 2 Preliminary Notation  
All trees are considered rooted in this method. Given a tree \(T\), we denote by \(\mathsf{r}(T)\) its root, by \(\mathsf{V}(T)\) its node set, by \(\mathsf{L}(T)\subseteq\mathsf{V}(T)\) its leaf set, and we let \(\mathsf{I}(T)=\mathsf{V}(T)-\mathsf{L}(T)\) be the set of its internal nodes. A node \(v^{\prime}\) is an _ancestor_ of \(v\) if \(v^{\prime}\) is on the path from \(\mathsf{r}(T)\) to \(v\), and the _parent_\(\mathsf{p}(v)\) of \(v\), of which \(v\) is a _child_, directly precedes \(v\) on this path. Conversely, \(v\) is a _descendant_ of \(v^{\prime}\). This ancestor-descendant relation is denoted as \(\leq\) and forms a partial order on the nodes, in which the root is minimal and the leaves are maximal. Any pair of nodes \(v\) and \(v^{\prime}\) not ordered by this relation are said to be _separated_, which we denote as \(v\parallel v^{\prime}\). Notice that a node \(v\) is both an ancestor and a descendant of itself; whenever this case needs to be excluded, we will talk about strict ancestors and strict descendants.  
We denote by \(\mathsf{E}(T)\) the set of edges of \(T\), each of which are represented by a pair of nodes \((\mathsf{p}(v),v)\). For any two nodes \(v\) and \(v^{\prime}\) of \(T\), there exists a unique path from \(v\) to \(v^{\prime}\) that we denote \(\mathsf{P}_{T}(v,v^{\prime})\subseteq\mathsf{E}(T)\). The distance between \(v\) and \(v^{\prime}\) is defined as \(\mathsf{D}_{T}(v,v^{\prime})=|\mathsf{P}_{T}(v,v^{\prime})|\). Given a node \(v\) of \(T\), \(T[v]\) is the _subtree_ of \(T\) rooted at \(v\) (i.e., containing only the descendants of \(v\)). The _lowest common ancestor_ (LCA) of a subset \(V\) of nodes, denoted as \(\mathsf{lca}_{T}(V)\), is the ancestor of all nodes in \(V\), which is the most distant from the root.  
A tree \(T^{\prime}\) is said to be an _extension_ of a tree \(T\) if \(T^{\prime}\) can be obtained from \(T\) by a sequence of operations among the following: (1) _Subdividing_ an edge \((u,w)\) by adding a new node \(v\) and replacing \((u,w)\) by two edges \((u,v)\) and \((v,w)\); (2) _Grafting_ a new node \(v\) below an existing node \(u\) by adding the edge \((u,v)\); (3) _Rerooting_ the tree to a new node \(u\) by adding the edge \((u,\mathsf{r}(T))\).  
The set of children of any node \(v\) is denoted by \(\mathrm{ch}(v)\). If \(|\mathrm{ch}(v)|=1\), then \(v\) is said to be _unary_ and we denote its only child by \(v_{\mathrm{c}}\). If \(|\mathrm{ch}(v)|=2\), then it is said to be _binary_ and, unless specified otherwise, we denote its children by \(v_{\ell}\) and \(v_{\mathrm{r}}\) in no particular order. A _binary tree_ is a tree where all internal (non-leaf) nodes are binary. If all internal nodes are unary or binary, then the tree is _partially binary_.  
If \(\mathcal{F}\) is a set of gene families, then a _synteny_ on \(\mathcal{F}\) is a subset \(X\subseteq\mathcal{F}\), which represents a group of genes assumed to have jointly evolved. Notice that we ignore the relative order of genes in the genomic region, as well as the physical distance between genes and regions. The genes of a synteny are considered to all belong to different gene families (i.e., repeated gene families inside a synteny are forbidden); therefore, a gene is simply identified by the family \(\Gamma\in\mathcal{F}\) it belongs to.  
A _species tree_\(S\) on a set \(\Sigma\) of species is a binary tree with a bijection between \(\mathrm{L}(S)\) and \(\Sigma\). For a set of syntenies \(\mathcal{X}\), a _synteny tree_\(\langle T,x,s\rangle\) is a tuple where \(T\) is a binary tree, \(x:\mathrm{L}(T)\to\mathcal{X}\) and \(s:\mathrm{L}(T)\to\Sigma\) are two functions, the second indicating the species to which each synteny belongs.  
Finally, the restriction of a function \(f\) to a subset \(A\) of its domain is denoted as \(f|_{A}\).