\section{Introduction}
\label{sec:intro}
An important step towards fully understanding signals of QGP formation and collectivity in heavy ion collisions, is providing realistic extrapolations of the dynamics of pp collisions. Collisions of protons with nuclei is an important stepping stone, as the full nuclear geometry is already involved here, but the situation remains somewhat simpler than a full AA collision, as the number of sub-collisions is equal to the number of wounded nucleons in the target.

In ref.~\cite{Bierlich:2016smv} we argued that the approximations normally used when extrapolating pp dynamics to pA collisions are too crude. We will present inclusion of fluctuations to the Glauber formalism, giving rise to a "wounded" cross section with contributions from diffractive excitations. We compare inclusion of fluctuations calculated in the \protect\scalebox{0.8}{DIPSY}\xspace model with those from the Glauber--Gribov model, and use them to calculate distributions of wounded nucleons at LHC energies. Finally we present a simple model based on these principles, which allows for extrapolation of multiparton interaction models to pA, and comparisons to data.

\section{Including fluctuations in pA collisions}
\subsection{Fluctuations in proton--proton}
The \protect\scalebox{0.8}{DIPSY}\xspace \cite{Flensburg:2011kk} model is a dynamic initial state model, built on the Mueller dipole model \cite{Mueller:1994jq}. The model includes dynamics up to LL-BFKL, plus additional corrections from satuation and momentum conservation\footnote{The \protect\scalebox{0.8}{DIPSY}\xspace initial state model is implemented in a full event generator, with final state radiation from the \protect\scalebox{0.8}{Ariadne}\xspace shower \cite{Lonnblad:1992tz}. Hadronization is carried out by P\protect\scalebox{0.8}{YTHIA}8\xspace \cite{Sjostrand:2014zea}, with added coherence effects from rope hadronization \cite{Bierlich:2014xba}. For more information, visit \texttt{http://home.thep.lu.se/DIPSY}.}.
The initial state is built up through evolution from an initial proton consisting of three valence dipoles. The evolution is in impact-parameter space and rapidity, with the dipole splitting probability per unit rapidity:
\begin{equation}
  \label{eq:dipoleradiation}
  \frac{d\mathcal{P}_g}{dY}=\frac{N_c \alpha_s}{2\pi^2}d^2\pmb{x}_g
\frac{(\pmb{x}_1-\pmb{x}_2)^2}{(\pmb{x}_1-\pmb{x}_g)^2 (\pmb{x}_g-\pmb{x}_2)^2}.
\end{equation}
An emission produces two new dipoles, $(\pmb{x}_1,\pmb{x}_g)$ and
$(\pmb{x}_g,\pmb{x}_2)$. The interaction probability between two dipoles, one from the left-moving cascade and one from the right-moving cascade:
\begin{equation}
  \label{eq:dipoleinteraction}
P=\frac{\alpha_s^2}{4}\left[\ln\left(
\frac{(\pmb{x}_1-\pmb{x}_3)^2(\pmb{x}_2-\pmb{x}_4)^2}
{(\pmb{x}_1-\pmb{x}_4)^2(\pmb{x}_2-\pmb{x}_3)^2}\right)\right]^2.
\end{equation}
Using the optical theorem, cross section can now be calculated. With convenient normalization, the optical theorem in impact parameter space reads:
\begin{equation}
	\Im{(A_{el})} = \frac{1}{2}(|A_{el}|^2 + P_{abs}).
\end{equation}
Where "abs" is short for "absorption", \emph{i.e.}~inelastic non-diffractive contributions. By inserting from equation (\ref{eq:dipoleinteraction}), we obtain the real elastic amplitude in impact parameter space, including all fluctuations in projectile and target:
\begin{equation}
	\label{eq:tofB}
	T(b) \equiv -iA_{el} =  1 - \exp\left(-\sum_{ij} f_{ij}\right).
\end{equation}
Since fluctuations are related to diffraction through the Good-Walker formalism, calculation of several semi-inclusive proton-proton cross sections is possible with equation (\ref{eq:tofB}). Here the absorptive, single diffractive and double diffractive:
\begin{align}
	\frac{d\sigma_{abs}}{d^2b} &= 2\left< T(b)\right> - \left< T(b)\right>^2,\\
	\frac{d\sigma_{SD,(p|t)}}{d^2b} &= \left<\left<T\right>^2_{(t|p)}\right>_{(p|t)} - \left<T\right>^2_{p,t},\\
	\frac{d\sigma_{DD}}{d^2b} &=\left<T^2\right>_{p,t} - \left<\left< T\right>^2_t\right>_p - \left<\left< T\right>^2_p\right>_t + \left<T\right>^2_{p,t}.
\end{align}
where subscripts $p$ and $t$ indicates averages over projectile and target respectively. The \protect\scalebox{0.8}{DIPSY}\xspace formalism applies for protons and nuclei alike, and has recently been applied directly to pA collisions \cite{Gustafson:2015ada}. In this work \protect\scalebox{0.8}{DIPSY}\xspace is only used to calculate fluctuations in the proton transverse structure, and a simpler model is used for extrapolation to pA (see section \ref{sec:extra}).

\subsection{Parametrization of cross section fluctuations}
When extrapolating from pp to pA collisions, it is important to keep in mind that many measurements will rely on a centrality measure, \emph{e.g.}~particle production in the forward (Pb going) direction. The relevant semi-inclusive cross section for an interaction between projectile and target will therefore have contributions from absorptive, single diffractive and double diffractive processes. We dub this the "wounded" cross section, inspired by the wounded nucleon model by Bia\l as \emph{et al}~\cite{Bialas:1976ed}:
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/sigmaWounded.eps}
	\caption{\label{fig:sigwounded}Fluctuations in $\sigma_w$ for \protect\scalebox{0.8}{DIPSY}\xspace and three versions of GG fluctuations. GG fluctuations using a log-normal parametrization of $P_{tot}(\sigma)$ seems to be able to describe the \protect\scalebox{0.8}{DIPSY}\xspace fluctuations best.}
\end{figure}
\begin{equation}
\frac{d\sigma_w}{d^2b} = \frac{d\sigma_{abs}}{d^2b} + \frac{d\sigma_{SD,t}}{d^2b} +  \frac{d\sigma_{DD}}{d^2b} =  2\left<T\right>_{p,t} - \left<\left<T\right>^2_t\right>_p.
\end{equation}
We can now compare the fluctuations in $\sigma_w$ produced by \protect\scalebox{0.8}{DIPSY}\xspace with the often used parametrization, Glauber--Gribov Colour Fluctuations (GG) \cite{Alvioli:2013vk}. Here the fluctuations are parametrized with a distribution $P_{tot}(\sigma)$ such that:
\begin{align}
	\sigma_{tot} & = \int d\sigma  \sigma P_{tot}(\sigma) \\
		     & = \int d\sigma \rho \frac{\sigma^2}{\sigma + \sigma_0}\exp\left[-\frac{(\sigma/\sigma_0 -1)^2}{\Omega^2} \right], \label{eq:pstrik}
\end{align}
where the usual choice for $P_{tot}(\sigma)$ has been inserted in equation (\ref{eq:pstrik}). The parameters of the model can be fitted to semi-inclusive cross sections by assuming a functional form for $T$. Here we use a semi-transparent disk with:
\begin{equation}
	T(b,\sigma) = T_0 \Theta\left(\sqrt{\frac{\sigma}{2\pi T_0}} - b\right).
\end{equation}
The semi-inclusive cross sections are:
\begin{align}
	\sigma_{tot} &= \int d^2b \int d\sigma P_{tot}(\sigma)2T(b,\sigma) \\
	\sigma_{el} &= \int d^2b \left|\int d\sigma P_{tot}(\sigma) T(b,\sigma) \right|^2\\
	\sigma_{w} &= \int d^2b \int d\sigma P_{tot}(\sigma) \left[ 2T(b,\sigma) - T(b,\sigma)\right]
\end{align}
In figure \ref{fig:sigwounded} we show fluctuations in $\sigma_w$ at $\sqrt{s_{NN}} = 5.02$ TeV with \protect\scalebox{0.8}{DIPSY}\xspace as well as GG, compared to GG with an modified $P_{tot}$ distribution -- a log-normal distribution -- which we find describes the \protect\scalebox{0.8}{DIPSY}\xspace fluctuations better:
\begin{equation}
 P_{tot}(\sigma,b) = \frac{1}{\Omega \sqrt{2\pi}}\exp \left(-\frac{\log^2(\sigma/\sigma_0)}{2\Omega^2} \right).
\end{equation}
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/npartWounded.eps}
	\caption{\label{fig:npart}Number of participants in collisions of pPb at 5.02 TeV using four different Glauber models.}
\end{figure}
\subsection{Extrapolation to pA}
\label{sec:extra}
In order to model pA collisions using the pp results from the previous section, we use a Woods-Saxon potential in the GLISSANDO parametrization \cite{Rybczynski:2013yba}. Colliding a proton with a lead nucleus at $\sqrt{s_{nn}} = 5.02$ TeV using the $\sigma_w$ as the relevant cross section is, however, not enough to proceed, as we want to distinguish absorptively wounded nucleons from diffractively excited ones. This is not possible in a GG parametrization, as it does not allow for separate fluctuations in projectile and target. This is accomodated in a crude way by allowing nucleons to fluctuate between two sizes with a fixed probablity. The real elastic amplitude for a projectile with radius $R_p$ to collide with target $R_t$ is $T(b) = \alpha\Theta(R_p + R_t - b)$, where $\alpha$ is an opacity. Adding a parameter ($c$) for the fluctuation probablity, the model has a total of four parameters ($r_1$, $r_2$, $c$ and $\alpha$), which can again be fitted to semi-inclusive pp cross sections. Following this logic, we can extend the GG model to enable us to distinguish between the two types of wounded nucleons, as the conditional probability for a wounded nucleon to also be diffractively excited, amounts to:
\begin{equation}
	\Theta\left(\sqrt{\sigma_{GG}/\pi} - (r_1 - r_2) - b\right) \frac{2 - \alpha}{2 - \alpha c}.
\end{equation}
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/npartAbs.eps}
	\caption{\label{fig:npartabs}Number of absorptively wounded participants in collisions of pPb at 5.02 TeV using four different Glauber models.}
\end{figure}
In figure \ref{fig:npart} we show the distribution of wounded nucleons for the GG model with added target fluctuations as per the above recipe for both the regular and the log-normal parametrization of $P_{tot}(\sigma)$. For comparison we show also the pure 2-radius model (named $2\times 2$) as well as ordinary black disk Glauber.
In figure \ref{fig:npartabs} we compare to the number of absorptively wounded participants. We see that the model retains their ordering as expected. We also see that adding fluctuations clearly produces a higher tail, both comparing fluctuating models to the black disk, but also comparing the log-normal distribution to the standard choice.
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/sumet.eps}
	\caption{\label{fig:sumet}Distribution of $\sum E_\perp$ in the lead-going direction. used as a centrality observable by ATLAS.}
\end{figure}
\FloatBarrier
\section{Final states}
\subsection{Particle production}
We now want to estimate final states, by coupling the wounded nucleons to a model for particle production. A situation with just a single absorptively wounded nucleons is simple. It can simply be taken equal to a pp inelastic non-diffractive event, for which we will use the P\protect\scalebox{0.8}{YTHIA}8\xspace MPI handling \cite{Sjostrand:1987su}. Adding another absorptive sub-collision does, however, not contribute equally much. The situation here is similar to doubly absorptive proton--deuteron scattering. \footnote{This is particularly visible if one considers the cut Pomeron diagrams of the two processes.}

In the following we therefore treat additional absorptive sub-collisions \emph{as if} they were diffractive excitations. The real diffractive excitations are treated in the same way. High $p_\perp$ secondary absorptive exchanges are treated in a perturbative framework, whereas low $p_\perp$ are treated using a framework drawing from the old Fritiof event generator \cite{Andersson:1986gw}. This particle production model is dubbed "FritiofP8". For comparison we also show events where everything is treated as an absorptive sub-collision, dubbed "Absorptive".
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/multMiddle.pdf}
	\caption{\label{fig:etaMiddle}Multiplicity distribution in $\eta$ for pPb, mid-centrality.}
\end{figure}
\subsection{Comparison to data}
Recent data by ATLAS \cite{Aad:2015zza} suggests the use of $\sum E_\perp$ in the forward direction as centrality observable. In figure \ref{fig:sumet} we show results for this distribution for both FritiofP8 and Absorptive.
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figures/multCent.pdf}
	\caption{\label{fig:etaCent}Multiplicity distribution in $\eta$ for pPb, central events.}
\end{figure}
We see that the FritiofP8 model gives a softer distribution which is much more similar to data than the Absorptive. We bin in centrality by taking fractiles of this distribution, which gives multiplicity distributions in $\eta$, as shown in figure \ref{fig:etaMiddle} for mid-centrality events and figure \ref{fig:etaCent} for central events.
We see that while the "absorptive" model overshoots, FritiofP8 manages to describe well the multiplicity in absolute numbers, the centrality dependance and the $\eta$-asymmetry.

\section{Acknowledgements}

\nocite{*}
\bibliographystyle{elsarticle-num}


\section{Introduction}

Supertree methods combine the evolutionary relationships of a set of
phylogenetic trees \textbf{G}, into a single tree \textbf{T} \cite{BinindaEmonds2014}. These
methods differ from the consensus-based approaches \cite{Gordon1986, Dong2010},
by allowing input trees to have different but overlapping set of taxa.
Supertrees are useful in combining input trees generated
from completely incomparable approaches, such
as statistical analysis of discrete dataset and distance analysis of
DNA-DNA hybridization data \cite{BinindaEmonds2014}. Input trees often exhibit
conflicting topologies, due to different evolutionary histories of respective genes,
stochastic errors in site and taxon sampling, and biological errors due to
paralogy, incomplete lineage sorting, or horizontal gene transfer \cite{Ranwez2010}.
Supertree methods quest for resolving such conflicts in order to produce
a `median tree', which minimizes the sum of a given distance
measure with respect to the input trees \cite{Ranwez2010}. Large scale supertrees are
intended towards assembling the \emph{Tree of Life} \cite{Reaz2014}.

Our earlier work \cite{Sourya2014}, and the study in \cite{BinindaEmonds2014}, provide
a comprehensive review of various supertree methods. \emph{Indirect} supertree methods
first generate intermediate structures like matrices (as in MRP \cite{Baum1992},
Minflip \cite{Chen2006}, SFIT \cite{Creevey2005}) or graphs (as in Mincut (MC) \cite{Semple2000},
modified Mincut \cite{Page2002}) from
the input trees, and subsequently resolve these intermediate structures to
produce the final supertree. These methods, especially MRP, are quite
accurate, but computationally intensive. \emph{Direct} methods,
on the other hand, derives the supertree directly from input tree topologies.
These methods may aim for minimizing either the sum of false positive (FP) branches
(as in the \emph{veto} approaches like
PhySIC \cite{Ranwez2007}, SCM \cite{Roshan2004}) or the sum of
Robinson-Foulds (RF) \cite{Robinson1981} distance (as in
RFS \cite{Bansal2010}) between \textbf{T} and \textbf{G}. Another
approach named Superfine \cite{Swenson2011, Neves2012} employs
greedy heuristics on MRP \cite{Baum1992} or Quartet Maxcut (QMC) \cite{Snir2010},
to derive the supertree, which may not be completely resolved.
Supertrees formed by synthesizing the subtrees (such as triplets \cite{Ranwez2010, Lin2009},
quartets \cite{Snir2010, Reaz2014}) of the input trees, exhibit quite high
performance. But, time and space complexities of these methods
depend on the size of the subtree used.

We have previously developed COSPEDTree \cite{Sourya2014},
a supertree algorithm using evolutionary relationships
among individual pair of taxa (couplets). The method is computationally
efficient, but produces somewhat conservative (not fully resolved)
supertrees, with low number of false positive (FP) but high number of
false negative (FN) branches between \textbf{T} and \textbf{G}.
Here we propose its improved version, termed as
COSPEDTree-II, which produces better resolved supertree,
with lower number of FN branches between \textbf{T} and \textbf{G},
keeping the FP count also low. We have also proposed a mechanism to
convert a non-resolved supertree into a strict binary tree, to reduce the
FN count. COSPEDTree-II requires
significantly lower running time than COSPEDTree and most of the
reference methods, particularly for the datasets having
high number of trees or taxa.

Rest of this manuscript is organized as follows. First,
we review the basics of COSPEDTree (as in \cite{Sourya2014})
in section~\ref{sec:overview_cosped}. The method COSPEDTree-II is
then described in section~\ref{sec:Methodology}. Performance of
COSPEDTree-II is summarized in section~\ref{sec:Results}.

\section{Overview of COSPEDTree}
\label{sec:overview_cosped}

\begin{figure}[!ht]
\centering
\subfigure[]{\label{fig:source_1}\includegraphics[width=0.4\linewidth,keepaspectratio=true]{SourceTree1.pdf}}\qquad
\subfigure[]{\label{fig:source_2}\includegraphics[width=0.4\linewidth,keepaspectratio=true]{SourceTree2.pdf}}
\caption{Example input phylogenetic trees. All the nodes are labeled by
Newick \cite{Sukumaran2010} representation.}
\label{fig:input_trees}
\end{figure}

Let \textbf{G} consist of $M$ rooted input trees $t_1, t_2, \ldots, t_M$. For
an input tree $t_j$ ($1 \leq j \leq M$), let $L(t_j)$
be its set of constituent taxa. Suppose a pair of taxa $p$ and
$q$ belong to $L(t_j)$. Further, let $\phi_{p}$ and $\phi_{q}$ be the
parent internal nodes (points of speciation) of $p$ and $q$, respectively.
COSPEDTree \cite{Sourya2014} defines four
boolean relations $r^{pq}_{k}$ ($k \in \{ 1,2,3,4 \}$) between $p$ and $q$,
with respect to $t_j$, as:

\begin{enumerate}
 \item Earlier Speciation of $p$ than $q$ \textbf{($r^{pq}_{1}$)} is true,
 if $\phi_{p}$ is ancestor of $\phi_{q}$ in $t_j$. For the tree
 in Fig.~\ref{fig:source_2}, $r^{bX}_{1}$ is true, where $X \in \{a, c\}$.
 Similarly, $r^{eY}_{1}$ is true for $Y \in \{a, c, b\}$.
 \item  Later Speciation of $p$ than $q$ \textbf{($r^{pq}_{2}$)} is true,
 if $\phi_{p}$ is a descendant of $\phi_{q}$. So, $r^{qp}_{1}$ and $r^{pq}_{2}$
 are equivalent.
 \item Simultaneous Speciation of $p$ and $q$ \textbf{($r^{pq}_{3}$)} is true, if $\phi_{p}$ =
 $\phi_{q}$. In Fig.~\ref{fig:source_1}, $r^{ab}_{3}$ and $r^{cd}_{3}$
 are true.
 \item Incomparable Speciation of $p$ and $q$ \textbf{($r^{pq}_{4}$)} is true, when
 $\phi_{p}$ and $\phi_{q}$ occur at different (and independent)
 clades. For the tree in Fig.~\ref{fig:source_1},
 $r^{ac}_{4}$ is true.
\end{enumerate}

Using another taxon $s \in L(t_j)$, properties of $r_{1}$ to $r_{4}$
can be stated as the following:

\begin{description}
 \item[P1:] Both $r_{1}$ and $r_{2}$ are transitive. Thus,
 \begin{itemize}
  \item $r^{pq}_{1}$ \& $r^{qs}_{1}$ $\Rightarrow$ $r^{ps}_{1}$.
  \item $r^{pq}_{2}$ \& $r^{qs}_{2}$ $\Rightarrow$ $r^{ps}_{2}$.
 \end{itemize}
 \item[P2:] $r_{3}$ is an equivalence relation.
 \item[P3:] $r^{pq}_{3}$ (= $r^{qp}_{3}$) \& $r^{ps}_{k}$
 $\Rightarrow$ $r^{qs}_{k}$, where $k \in \{1, 2, 4\}$.
 \item[P4:] $r^{pq}_{1}$ (= $r^{qp}_{2}$) \& $r^{ps}_{4}$ (= $r^{sp}_{4}$)
 $\Rightarrow$ $r^{qs}_{4}$ (= $r^{sq}_{4}$).
\end{description}

\emph{Support tree set} $\varGamma_{pq}$ for a couplet ($p, q$)
is defined as:
\begin{equation}
\varGamma_{pq} = \{t_j: (p, q) \in L(t_j)\}
\end{equation}
The \emph{frequency} $F^{pq}_{k}$ ($k \in \{1,2,3,4\}$) of a relation
$r^{pq}_{k}$ between a couplet ($p, q$) is the number of input trees $t_j$
where $t_j \in \varGamma_{pq}$ and $r^{pq}_{k}$ is true.

The \emph{set of allowed relations} $R(p,q)$ between a couplet ($p, q$) is
defined as the following:
\begin{equation}
\label{eq:allowed_reln}
 R(p,q) = \{ r^{pq}_{k}: F^{pq}_{k} > 0 \}
\end{equation}
A couplet ($p, q$) exhibits \emph{conflict} if $|R(p,q)| \geq 2$
(where $|.|$ denotes the cardinality of a set). The
\emph{consensus relation} between ($p, q$) is the relation having
the maximum frequency.

\textit{Priority} measure $P^{pq}_{k}$ for a relation $r^{pq}_{k}$ \
($k \in \{1,2,3,4\}$) between a couplet ($p, q$) is defined as the following:
\begin{equation}
P^{pq}_{k} = F^{pq}_{k} - \displaystyle \sum_{1 \leq k' \leq 4, k' \neq k} F^{pq}_{k'}
\end{equation}
COSPEDTree also defines a \emph{support score} $V^{pq}_{k}$ for individual
relations $r^{pq}_{k}$ as the following:
\begin{equation}
V^{pq}_{k} = F^{pq}_{k} \times P^{pq}_{k}
\end{equation}
The consensus relation $r^{pq}_{k}$ between a couplet ($p, q$)
exhibits the highest $P^{pq}_{k}$ and $F^{pq}_{k}$ values. So,
corresponding $V^{pq}_{k}$ also becomes the highest among all
relations between ($p, q$).

Final supertree \textbf{T} \emph{resolves} (assigns a particular relation to)
individual couplet ($p, q$) with a single relation $r^{pq}_{k}$ ($k \in \{ 1,2,3,4 \}$)
between them. Maximum agreement property \cite{Bansal2010} of a
supertree quests for resolving individual couplets with their respective
consensus relations. But, satisfying such property is NP-hard
since consensus relations among couplets can be mutually
conflicting \cite{Sourya2014}. Thus, order of selection of
individual candidate relations $r^{pq}_{k}$ (to resolve the corresponding
couplet ($p, q$)) is crucial. In view of this, COSPEDTree first
constructs a set of relations $S_r$, such that if a relation
$r^{pq}_{k} \in S_r$, the couplet ($p, q$) is resolved with $r^{pq}_{k}$.
To construct $S_r$, COSPEDTree applies an iterative greedy approach.
At each iteration, it selects a relation $r^{p'q'}_{k}$
to resolve ($p', q'$) among all unresolved couplets, provided:
\begin{center}
$V^{p'q'}_{k'}$ = $\max_{\substack{\forall (p, q), \forall k}} V^{pq}_{k}$.
\end{center}
If the selected relation $r^{p'q'}_{k'}$ does not contradict with any of the already
selected relations in $S_r$ (according to the properties P1 to P4 mentioned
before), it is included in $S_r$.

\begin{figure}[!ht]
\centering
\subfigure[]{\label{fig:mult_par_1}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{multiple_parent1.pdf}}
\subfigure[]{\label{fig:mult_par_2}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{multiple_parent2.pdf}}
\subfigure[]{\label{fig:disc_node}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{disconnected_node.pdf}}
\subfigure[]{\label{fig:leaf_reln_dff}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{leaf_reln_dff.pdf}}
\caption{(a) Transitive parent problem (b) Multiple parent problem MPP.
(c) No parent problem NPP. (d) solution of NPP by COSPEDTree, by inserting
a hypothetical root R.}
\label{fig:forest_prop}
\end{figure}

Suppose, L(\textbf{G}) = $\cup^{M}_{j=1}L(t_j)$ denotes
the complete set of input taxa. Then, $N$ = $|$L(\textbf{G})$|$.
Using the set of relations $S_r$, COSPEDTree partitions L(\textbf{G})
into $s$ mutually exclusive taxa clusters
$C_{1}$,$C_{2}$,$\ldots$,$C_{s}$, with the following rule (details are
provided in \cite{Sourya2014}):

\begin{description}
 \item[R1:] If a pair of taxa $p$ and $q$ belong to the same cluster $C_i$
 ($1 \leq i \leq s$), $r^{pq}_3 \in S_r$.
 \item[R2:] Suppose $C_{i}$ and $C_{j}$ ($1 \leq i,j \leq s$, $i \neq j$) are
 any two distinct taxa clusters. Then, $\forall p \in  C_{i}$, and $\forall q \in  C_{j}$,
 $r^{pq}_k \in S_r$, where $k \in \{1, 2, 4\}$. This property is denoted by
 saying that $r^{C_iC_j}_k$ is true, or $C_{i}$ is related with $C_{j}$ via the
 relation $r_k$.
\end{description}

COSPEDTree creates a directed acyclic graph (DAG), whose nodes
are individual taxa clusters $C_{i}$ ($1 \leq i \leq s$).
A directed edge from $C_{i}$ to $C_{j}$ means $r^{C_iC_j}_1$
is true. However, occurrence of one or more of the following properties means this DAG
needs to be refined to form a tree:

\begin{enumerate}
 \item Transitive parent problem (TPP): for three nodes A, B, and C,
 when $r^{AC}_1$, $r^{BC}_1$, and $r^{AB}_1$ are simultaneously true,
 as indicated in Fig.~\ref{fig:mult_par_1}.
 \item Multiple parent problem (MPP): when $r^{AC}_1$, $r^{BC}_1$,
 and $r^{AB}_4$ are simultaneously true, as shown in Fig.~\ref{fig:mult_par_2}.
 \item No parent problem (NPP) (Fig.~\ref{fig:disc_node}): when a node $A$
 does not have any parent, i.e. So, there exists no node $B$ such that
 $r^{BA}_1$ is true.
\end{enumerate}

COSPEDTree \cite{Sourya2014} applies transitive reduction to resolve
TPP. The problem MPP is solved by arbitrary parent
assignment, while NPP is resolved by assigning one hypothetical
root node to the isolated node (as shown in Fig.~\ref{fig:leaf_reln_dff}).
Finally, a depth first traversal of this DAG produces the
supertree \textbf{T}. As there is no restriction regarding
the number of taxa in individual taxa clusters
(partitions with respect to the relation $r_3$), \textbf{T} may not
be strictly binary (completely resolved).

\section{Proposed Methodology}
\label{sec:Methodology}

COSPEDTree-II extends COSPEDTree by incorporating the following
modifications:

1) COSPEDTree-II skips the formation of $S_r$. Rather, the taxa clusters
(containing one or more taxon) are first derived, solely by the
frequencies of different relations between individual couplets.
Subsequently, directed edges between individual pairs of clusters
are assigned, according to the properties of individual couplets
contained within these cluster pairs. Such processing on the taxa clusters,
rather than the couplets, achieves high speedup and much
lower running time.

2) In COSPEDTree, if a relation $r^{pq}_{k}$ ($1 \leq k \leq 4$)
between a couplet ($p, q$) is supported in a tree
$t_j \in \varGamma_{pq}$, the frequency $F^{pq}_{k}$ is
incremented by 1. COSPEDTree-II, on the other hand, uses
fractional and dynamic frequency values. In the above case,
COSPEDTree-II increments $F^{pq}_{k}$ with a \emph{weight}
$W^{t_j}_{pq}$ ($0 < W^{t_j}_{pq} \leq 1$), which
varies for individual couplets ($p, q$), and also
for individual trees $t_j \in \varGamma_{pq}$.

3) For the problem MPP, COSPEDTree-II proposes a
deterministic selection of the parent, for the
node having multiple parents.

4) COSPEDTree-II also suggests a mechanism to convert a non-binary
supertree into a binary tree.

Subsequent sections describe all such improvements.

\subsection{Fractional frequency value for relations}
\label{subsec:weight_freq}

\begin{figure}[!ht]
\centering
\subfigure[]{\label{fig:no_edge_1}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{NoEdgePrior1.pdf}}
\subfigure[]{\label{fig:no_edge_2}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{NoEdgePrior2.pdf}}
\subfigure[]{\label{fig:bidir_edge_1}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{BiDirPrior1.pdf}}
\subfigure[]{\label{fig:ex_suptree}\includegraphics[width=0.23\linewidth,keepaspectratio=true]{ExSupTree.pdf}}
\caption{Fig. (a) to (c) shows three input trees. Fig. (d) shows
the corresponding supertree.}
\label{fig:reln_priority}
\end{figure}

COSPEDTree-II applies a fractional frequency value $W^{t_j}_{pq}$
if an input tree $t_j$ supports the relation $r^{pq}_{k}$
between a couplet ($p,q$). Value of $W^{t_j}_{pq}$
depends on the set $L(t_j)$. Utility of such a dynamic (and fractional) frequency measure
is explained by Fig.~\ref{fig:reln_priority}, which shows
three input trees (Fig.~\ref{fig:no_edge_1} to
Fig.~\ref{fig:bidir_edge_1}) and corresponding supertree (Fig.~\ref{fig:ex_suptree}).
For the couplet (A,C), all of the relations $r_2$, $r_3$ and $r_4$ are
supported. However, we observe that the relation $r_3$ is supported only because
corresponding tree does not include taxa B and D. Similarly, the relation
$r_2$ occurs due to the absence of the taxon D. When both B and D are
present (Fig.~\ref{fig:bidir_edge_1}), the relation $r_4$ (which is the ideal
relation between (A,C)) is satisfied. So, the relation $r_4$ should be
given higher weight, since the corresponding tree has higher
taxa coverage. So, our proposed dynamic frequency measure varies according
to the coverage of taxa of different input trees.

Considering an input tree $t_j$ ($1 \leq j \leq M$) and a couplet ($p,q$) in
$L(t_j)$, first we define the following notations:

\begin{itemize}
 \item $V(t_j)$: set of nodes (leaf or internal) of $t_j$.
 \item $LCA^{t_j}_{pq}$: lowest common ancestor (LCA) of
 $p$ and $q$ in $t_j$.
 \item $Clade_{t_j}(v)$: subtree rooted at an internal node
 $v \in (V(t_j) - L(t_j))$.
 \item $Cluster_{t_j}(v)$: Set of taxa underlying $Clade_{t_j}(v)$.
\end{itemize}

With such definitions, the set of \emph{excess taxa} (excluding the couplet itself)
underlying the LCA node of ($p,q$) in $t_j$, is defined as the following:
\begin{equation}
 U^{t_j}_{pq} = Cluster_{t_j}(LCA^{t_j}_{pq}) - \{p, q\}
\end{equation}
For ($p,q$), \emph{union of all excess taxa} underlying
the respective $LCA^{t_j}_{pq}$ nodes for all
$t_j \in \varGamma_{pq}$, is:
\begin{equation}
 U^{\mbox{\textbf{G}}}_{pq} = \bigcup_{t_j \in \varGamma_{pq}} U^{t_j}_{pq}
\end{equation}
We assign the weight of a relation $r^{pq}_{k}$
($1 \leq k \leq 4$) between ($p,q$) in an input tree $t_j$, as:
\begin{equation}
\label{eq:weight_couplet_reln}
 W^{t_j}_{pq} = \frac{|U^{\mbox{\textbf{G}}}_{pq} \bigcap L(t_j)|}{|U^{\mbox{\textbf{G}}}_{pq}|}
\end{equation}
where $W^{t_j}_{pq}$ = 1 if $U^{\mbox{\textbf{G}}}_{pq}$ = $\phi$.

Thus, the weight equals the proportion of taxa within
$U^{\mbox{\textbf{G}}}_{pq}$, that is covered in the input tree
$t_j$. Frequency $F^{pq}_{k}$ of the relation $r^{pq}_{k}$, is now redefined
as the following:
\begin{equation}
 F^{pq}_{k} = \sum_{t_j \mbox{ supports } r^{pq}_{k}} W^{t_j}_{pq}
\end{equation}

\subsection{Generating taxa clusters}
\label{subsec:taxa_clust_gen}

COSPEDTree \cite{Sourya2014} creates taxa clusters after formation of the \emph{set
of resolving relations} $S_r$. COSPEDTree-II, on the other hand, creates taxa
clusters before resolving any couplets at all. Rather, for individual couplets ($p,q$),
COSPEDTree-II inspects the values of $F^{pq}_{k}$ for individual relations $r^{pq}_{k}$
($k \in \{1, 2, 3, 4\}$). Creation of taxa clusters requires identifying couplets
which can be resolved by the relation $r_3$. COSPEDTree-II
places a pair of taxa $p$ and $q$ in the same taxa cluster (thereby
resolving the couplet ($p,q$) with the relation $r_3$), provided:

\begin{enumerate}
 \item Either $|R(p,q)|$ = 1 and $r^{pq}_{3} \in R(p,q)$ ($R(p,q)$
 is already defined in Eq.~\ref{eq:allowed_reln}).
 \item Or $|R(p,q)|$ = 2 and $r^{pq}_{3}$ is majority consensus. In such a case,
 $F^{pq}_{3} \geq 0.5 * \{\sum_{k} F^{pq}_{k}\}$.
 \item If $|R(p,q)| >$ 2, the couplet ($p,q$) is not placed in the same taxa cluster,
 even if $r^{pq}_{3}$ is majority consensus. This is because, as the
 couplet exhibits high degree of conflict, we check the relations between
 $p$, $q$, and other taxa set.
\end{enumerate}

The first condition is obvious. A couplet having only $r_3$ as its allowed
relation would be preferably resolved with it. On the other hand, if there
exists one more relation $r^{pq}_{k'}$ ($k' \neq 3$) within $R(p,q)$, we check whether
$F^{pq}_{3} > F^{pq}_{k'}$, which ensures that $r^{pq}_{3}$ is
the majority consensus relation of ($p,q$). In such a case, the
couplet is highly probable of being resolved with $r_3$ in the final
supertree.

Above mentioned heuristics are applied for individual couplets, to perform
the equivalence partitioning (taxa clusters) of the input taxa
set L(\textbf{G}).

\subsection{Connectivity between taxa clusters to form DAG}
\label{subsec:taxa_clust_conn}

Creation of the taxa clusters is followed by the assignment of
directed edges between them. As mentioned in
section~\ref{sec:overview_cosped}, directed edge from a
cluster $C_i$ to a cluster $C_j$ corresponds to the
relation $r^{C_iC_j}_1$ (= $r^{C_jC_i}_2$)
being true. In such a case, the cluster pair ($C_i$, $C_j$)
is said to be \emph{resolved by the relation} $r_1$. In general,
a pair of clusters can be resolved via any one of the relations $r_1$, $r_2$ or
$r_4$ (no directed edge in this case).
For individual relations $r_k$ ($k \in \{1, 2, 4\}$), we
define its frequency $F^{C_iC_j}_k$ with respect to the pair of
cluster ($C_i, C_j$), as the following:
\begin{equation}
 F^{C_iC_j}_k = \sum_{\forall p \in C_i, \forall q \in C_j} F^{pq}_{k}
\end{equation}
Priority of individual relations $r_k$ ($k \in \{1, 2, 4\}$)
for the cluster pair ($C_i, C_j$) is defined as the following:
\begin{equation}
 P^{C_iC_j}_{k} = F^{C_iC_j}_{k} - \sum_{k' \in \{1, 2, 4\}, k \neq k'} F^{C_iC_j}_{k'}
\end{equation}
Support score of a relation $r_k$ between the cluster pair ($C_i, C_j$) is
defined as:
\begin{equation}
 V^{C_iC_j}_{k} = P^{C_iC_j}_{k} + F^{C_iC_j}_{k}
\end{equation}
Note that we have used sum, rather than the product, of the priority and
frequency measures. This is due to the disparity of signs of frequency (which
is always non-negative) and the priority (which can be negative even for a
consensus relation) measures.
Higher support score of a relation (between a pair of clusters)
indicates higher frequency and priority of the corresponding relation.

The set $Q$ of support scores for different relations between
individual cluster pairs is defined as follows:
\begin{equation}
 Q = \{V^{C_iC_j}_{k}: C_i \neq C_j, k \in \{1, 2, 4\}, F^{C_iC_j}_k > 0 \}
\end{equation}
Individual taxa clusters are now resolved by an iterative algorithm,
using the set $Q$. Each iteration extracts a relation
$r^{C_xC_y}_{k'}$ ($k' \in \{1, 2, 4\}$)) from $Q$, provided the following:
\begin{equation}
 V^{C_xC_y}_{k'} = \max_{\substack{\forall (C_i, C_j), \forall k}} V^{C_iC_j}_{k}
\end{equation}
Following conditions are checked to see whether the extracted relation $r_{k'}$
can resolve the cluster pair ($C_x$, $C_y$).

\begin{enumerate}
 \item If ($C_x$, $C_y$) is already resolved with a different relation,
 $r_{k'}$ is not applied.
 \item If $k'$ = 1 or 2, resolving ($C_x$, $C_y$) with $r_{k'}$ would
 create a directed edge between the cluster pair. If such an
 edge forms a cycle with the existing configuration of the taxa clusters,
 $r_{k'}$ is not applied.
\end{enumerate}

For no such above mentioned conflicts, the relation $r_{k'}$ is applied
between $C_x$ and $C_y$.

The set $Q$ is implemented as a max-priority queue \cite{Cormen2001},
to achieve \BigO{1} time complexity for extracting the cluster
pair having the maximum support score. Iterations continue until $Q$ becomes
empty. However, the final DAG may still have the
problems TPP, MPP, and NPP (as defined in Fig.~\ref{fig:forest_prop}).
The problem TPP is removed by transitive reduction (already described in
COSPEDTree \cite{Sourya2014}). COSPEDTree-II employs a
better solution for the problem MPP, which is
described in the following section.

\subsection{Solving Multiple Parent Problem (MPP)}
\label{subsec:solnC2}

As shown in Fig.~\ref{fig:mult_par_2}, the problem MPP corresponds to a
cluster $C_z$ having $k$ ($k \geq$ 2) other clusters $C_1, C_2, \ldots, C_k$
as its parent, which are not themselves connected by any directed edges.
The objective is to assign a unique parent $C_p$ ($1 \leq p \leq k$) to the
cluster $C_z$. Such assignment was arbitrary in COSPEDTree \cite{Sourya2014}.
COSPEDTree-II proposes a deterministic selection of $C_p$, by a measure
called the \emph{internode count} $I_{t_j}(p,q)$ between a couplet ($p,q$),
with respect to a rooted tree $t_j$. The measure was introduced in \cite{Liu2011}
for unrooted trees. Here, the measure is adapted for a rooted tree $t_j$,
as the number of internal nodes between $p$ and $q$
through the node $LCA^{t_j}_{pq}$.

As individual trees $t_j$ carry overlapping taxa subsets of L(\textbf{G}),
we define a \emph{normalized internode count distance}
between $p$ and $q$ in $t_j$ as:
\begin{equation}
I^{N}_{t_j}(p,q) = \frac{I_{t_j}(p,q)}{W^{t_j}_{pq}}
\end{equation}
where $W^{t_j}_{pq}$ is defined in the Eq.~\ref{eq:weight_couplet_reln}.
So, $I^{N}_{t_j}(p,q)$ becomes low only when both $I_{t_j}(p,q)$ is low
and $W^{t_j}_{pq}$ is high (when the tree $t_j$ carries higher proportion of
the taxa subset belonging to $U^{\mbox{\textbf{G}}}_{pq}$).

Significance of the internode count distance can be explained by considering
a rooted triplet $(r,(p,q))$ (shown in the Newick \cite{Sukumaran2010} format),
consisting of three taxa $p$, $q$ and $r$. Here, $I^{N}(p,q) < I^{N}(p,r) = I^{N}(q,r)$.
In general, lower internode count means corresponding
couplet is evolutionarily closer, compared to the other couplets.

\emph{Average internode count} of a couplet $(p,q)$, with respect
to \textbf{G}, is defined by the following expression:
\begin{equation}
 I_{avg}(p,q) = \frac{1}{|\varGamma_{pq}|} \sum_{t_j \in \varGamma_{pq}} I^{N}_{t_j}(p,q)
\end{equation}
The \emph{internode count distance between a pair of cluster} $C_x$ and
$C_y$ is defined by the following equation:
\begin{equation}
 I(C_x, C_y) = \frac{\sum_{\forall p \in C_x, q \in C_y} I_{avg}(p,q)}{|C_x||C_y|}
\end{equation}
where $|C_x|$ denotes the cardinality of the taxa cluster $C_x$.

For the MPP problem, COSPEDTree-II selects the cluster $C_p$ ($1 \leq p \leq k$)
as the parent of $C_z$, provided that $C_p$ has the lowest internode count
distance to $C_z$:
\begin{equation}
 C_p = \mbox{argmin}_{\substack{1 \leq i \leq k}} I(C_z, C_i)
\end{equation}
Such condition is based on the assumption that the cluster pair
having lower internode count, is possibly closer in
the evolutionary tree, compared to other cluster pairs.

\subsection{Binary supertree generation}
\label{subsec:refine_tree}

\begin{figure}[!ht]
\centering
\subfigure[]{\label{fig:multi_furc_clust}\includegraphics[width=0.8\linewidth,keepaspectratio=true]{Binary_Multifurcation_Example.pdf}}
\subfigure[]{\label{fig:multi_furc}\includegraphics[width=0.45\linewidth,keepaspectratio=true]{binary_multifurcation_input_tree.pdf}}
\subfigure[]{\label{fig:multi_furc_refine}\includegraphics[width=0.45\linewidth,keepaspectratio=true]{binary_multifurcation_input_tree_refine.pdf}}
\caption{(a) Example of a multifurcation, containing the taxa
subset $X = A \cup B \cup C \cup D$. (b) an input tree $t_{j|X}$,
restricted to the taxa subset $X$. (c) Tree $t'_{j|X}$ created from $t_{j|X}$.}
\label{fig:binary_refine}
\end{figure}

After resolving the problem MPP, the refined DAG is converted to the
supertree \textbf{T}, by a depth first traversal procedure (as
described in COSPEDTree \cite{Sourya2014}). However, the generated
supertree \textbf{T} may not be completely resolved. COSPEDTree-II
proposes a refinement strategy which converts \textbf{T} into a
strict binary tree.

Suppose, the tree contains an internal multi-furcating node of degree
$n$ ($> 2$). Let $X_1, X_2, \ldots, X_n$ denote the taxa subsets
descendant from it, where each taxa subset $X_i$ ($1 \leq i \leq n$) consists
of one or more taxon named as $X_{i1}, X_{i2}, \ldots$, etc.
Union of these taxa subsets is represented by $X$ = $\cup^{n}_{i=1} X_{i}$.
Suppose, $t_{j|X}$ represents the input tree $t_j$ ($1 \leq j \leq M$)
\emph{restricted} to the set of taxa $X$. Thus, $L(t_{j|X})$ =
$L(t_{j}) \cap X$. Considering Fig.~\ref{fig:multi_furc_clust} as
an example, the node $R$ represents a multi-furcation with degree 4.
Four taxa subsets A, B, C, and D, descend from R. Here,
$X = A \cup B \cup C \cup D$. Generation of a binary
tree requires introducing bifurcations among these
taxa subsets. So, for individual input trees $t_j$,
corresponding restricted input tree $t_{j|X}$ is produced,
as shown in Fig.~\ref{fig:multi_furc}.

Our proposed binary refinement first generates a tree $t'_{j|X}$
from the tree $t_{j|X}$, such that
the leaves of $t'_{j|X}$ represent individual taxa subsets $X_i$
($1 \leq i \leq n$). In other words, individual taxon in $t_{j|X}$
is replaced by the name of its corresponding taxa subset
(without any duplicate). For example, both the taxa $A_2$ and $A_3$
(belonging to the taxa subset $A$) are present in the tree $t_{j|X}$ (as shown in
Fig.~\ref{fig:multi_furc}). So, in $t'_{j|X}$, a leaf node labeled $A$
is first inserted as a child of the LCA node of $A_2$ and $A_3$.
Subsequently, the leaves $A_2$ and $A_3$ are deleted from $t'_{j|X}$.
This process is repeated for other taxa subsets $B$, $C$ and $D$
as well. Fig.~\ref{fig:multi_furc_refine} shows the tree $t'_{j|X}$.

For the current set of taxa $X$, each of the input trees $t_j$
are processed to generate the corresponding $t'_{j|X}$.
These trees are then used as input
to an existing triplet based supertree approach
thTBR \cite{Lin2009}, to generate a supertree $T_{X}$ consisting
of the taxa subsets $X_i$ as its leaves. The supertree method is selected
since it processes rooted triplets, and generates a
rooted output tree. The tree $T_{X}$ is used as a template, such that its
order of bifurcation among individual taxa subsets $X_i$ is
replicated to the original multi-furcating node $R$ and
its descendants. As the degree of
multifurcation ($n$ in this case) is much lower than the total number
of taxa ($N$), construction of $T_{X}$ is very fast. This process is continued
until all the multi-furcating nodes are resolved.

\begin{table}\center\scriptsize
\caption{Results for Marsupials \cite{Cardillo2004} dataset
($M$ = 158, $N$ = 267)}
\begin{tabular}{|p{2.4cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.7cm}|p{1.5cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 Minflip$^{*}$ \cite{Chen2006} &792 &946 &1738 &75.84 &20m \\%\hline
 MMC$^{*}$ \cite{Page2002} &911 &1251 &2162 &69.3 & - \\%\hline
 MRP PAUP$^{*}$ \cite{Baum1992} &756 &400 &1156 &86.59 &4.6m  \\%\hline
 PhySIC \cite{Ranwez2007} &0 &1324 &1324 &35.1 &14s \\%\hline
 RFS \cite{Bansal2010} &710 &361 &1071 &105.6 &6.5m \\%\hline
 SCM$^{*}$ \cite{Roshan2004} &0 &1220 &1220 &40.75 & - \\%\hline
 SFIT$^{*}$ \cite{Creevey2005} &1327 &979 &2306 &61.69 &111h \\%\hline
 Superfine(MRP)$^{*}$ \cite{Swenson2011} &750 &396 &1346 &89.54 &3m  \\%\hline
 thSPR \cite{Lin2009} &740 &860 &1600 &97.26 &3m \\%\hline
 thTBR \cite{Lin2009} &739 &859 &1598 &97.1 &3m \\%\hline
 Supertriplet \cite{Ranwez2010} &598 &390 &988 &ER &57s \\%\hline
 COSPEDTree &326 &841 &1167 &68.93 &6m \\%\hline
  \textbf{COSPEDTree-II} &\textbf{459} &\textbf{695} &\textbf{1154} &\textbf{78.02} &\textbf{2.4s + 2.2s} \\%\hline
  \textbf{COSPEDTree-II+B} &\textbf{827} &\textbf{482} &\textbf{1309} &\textbf{89.34} &\textbf{2.4s+2.2s+34.4s} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_marsupials}
\end{table}

\begin{table}\center\scriptsize
\caption{Results for Placental Mammals \cite{Beck2006} ($M$ = 726, $N$ = 116)}
\begin{tabular}{|p{2.4cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.7cm}|p{1.5cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 Minflip$^{*}$ \cite{Chen2006} &2965 &4002 &6967 &276.64 &7.25m \\%\hline
 MRP PAUP$^{*}$ \cite{Baum1992} &2545 &1902 &4447 &313.77 &3.5m  \\%\hline
 PhySIC \cite{Ranwez2007} &0 &4830 &4830 &222.86 &3s \\%\hline
 RFS \cite{Bansal2010} &2481 &1650 &4131 &511.54 &4.2m \\%\hline
 SCM$^{*}$ \cite{Roshan2004} &0 &4816 &4816 &223.86 & - \\%\hline
 SFIT$^{*}$ \cite{Creevey2005} &3315 &2353 &5668 &316.53 &108h \\%\hline
 QIMP$^{*}$ \cite{Holland2007} & 2423 & 1823 & 4246 & 477.84 & - \\%\hline
 Superfine(MRP)$^{*}$ \cite{Swenson2011} &2540 &1746 &4286 &439.65 &9.25m  \\%\hline
 Superfine(QMC)$^{*}$ \cite{Swenson2011} &2631 &1835 &4466 &432.84 & 6m \\%\hline
 thSPR \cite{Lin2009} &2627 &3268 &5895 &496.23 &7s \\%\hline
 thTBR \cite{Lin2009} &2626  &3272  &5898 &496.25 &6.39s \\%\hline
 Supertriplet \cite{Ranwez2010} & F & F & F & F & F \\%\hline
 COSPEDTree &1232 &3762 &4994 &394.42 &3.2m \\%\hline
  \textbf{COSPEDTree-II} &\textbf{1406} &\textbf{2601} &\textbf{4007} &\textbf{429.34} &\textbf{3.5s + 0.5s} \\%\hline
  \textbf{COSPEDTree-II+B} &\textbf{2730} &\textbf{1819} &\textbf{4549} &\textbf{491.85} &\textbf{3.5s+0.5s+9.2s} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_placental_mammals}
\end{table}

\begin{table}\center\scriptsize
\caption{Results for Seabirds \cite{Kennedy2002} dataset
($M$ = 7, $N$ = 121)}
\begin{tabular}{|p{2.4cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.7cm}|p{1.5cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 Minflip$^{*}$ \cite{Chen2006} &38 &72 &110 &3.24 &11s \\%\hline
 MRP PAUP$^{*}$ \cite{Baum1992} &61 &166 &227 &4.97 &11s  \\%\hline
 PhySIC \cite{Ranwez2007} &0 &150 &150 &0.64 &3s \\%\hline
 RFS \cite{Bansal2010} &28 &14 &42 &5.63 &4s \\%\hline
 SCM$^{*}$ \cite{Roshan2004} &1 &66 &67 &2.75 & - \\%\hline
 SFIT$^{*}$ \cite{Creevey2005} &42 &202 &244 &2.22 &1h \\%\hline
 Superfine(MRP)$^{*}$ \cite{Swenson2011} &32 &19 &51 &4.43 &3s  \\%\hline
 Superfine(QMC)$^{*}$ \cite{Swenson2011} &29 &19 &48 &4.6 & 3s \\%\hline
 thSPR \cite{Lin2009} &69 &242 &311 &5.71 &6s \\%\hline
 thTBR \cite{Lin2009} &115 &234 &349 &5.73 &6s \\%\hline
 Supertriplet \cite{Ranwez2010} & 2 & 176 & 178 & ER & 5.6s \\%\hline
 COSPEDTree &24 &81 &105 &2.37 &3s \\%\hline
  \textbf{COSPEDTree-II} &\textbf{27} &\textbf{66} &\textbf{93} &\textbf{2.58} &\textbf{0.2s + 0.3s} \\%\hline
  \textbf{COSPEDTree-II+B} &\textbf{50} &\textbf{37} &\textbf{86} &\textbf{5.02} &\textbf{0.2s+0.3s+3.1s} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_seabirds}
\end{table}

\begin{table}\center\scriptsize
\caption{Results for THPL \cite{Wojciechowski2000} dataset
($M$ = 19, $N$ = 558)}
\begin{tabular}{|p{2.4cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.7cm}|p{1.5cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 Minflip$^{*}$ \cite{Chen2006} &142 &149 &291 &4.93 &1.1h \\%\hline
 MRP PAUP$^{*}$ \cite{Baum1992} &75 &476 &551 &6.27 &31m   \\%\hline
 PhySIC \cite{Ranwez2007} &0 &279 &279 &1.19 &5.7m \\%\hline
 RFS \cite{Bansal2010} &106 &66 &172 &11.9 &4.5m \\%\hline
 SCM$^{*}$ \cite{Roshan2004} &13 &128 &141 &4.64 & - \\%\hline
 Superfine(MRP)$^{*}$ \cite{Swenson2011} &85 & 50 &135 &6.39 &1m  \\%\hline
 Superfine(QMC)$^{*}$ \cite{Swenson2011} &62 &43 &105 &6.5 & 1.5m \\%\hline
 thSPR, thTBR \cite{Lin2009} & ER & ER & ER & ER & ER  \\%\hline
 Supertriplet \cite{Ranwez2010} & F & F & F  &F  &F \\%\hline
 COSPEDTree &88 &162 &250 &4.21 &4.5m \\%\hline
  \textbf{COSPEDTree-II} &\textbf{96} &\textbf{137} &\textbf{233} &\textbf{5.74} &\textbf{2s + 9s} \\%\hline
  \textbf{COSPEDTree-II+B} &\textbf{166} &\textbf{114} &\textbf{280} &\textbf{8.22} &\textbf{2s+9s+1.2m} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_THPL}
\end{table}

\begin{table}\center\scriptsize
\caption{Results for Cetartiodactyla \cite{Price2005} dataset
($M$ = 201, $N$ = 299)}
\begin{tabular}{|p{2.4cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.7cm}|p{1.5cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 MMC$^{*}$ \cite{Page2002} &1181 &1438 &2619 &83.84 & - \\%\hline
 MRP PAUP$^{*}$ \cite{Baum1992} &860 &964 &1824 &120.84 & -   \\%\hline
 PhySIC \cite{Ranwez2007} &ER &ER &ER &ER &ER \\%\hline
 RFS \cite{Bansal2010} &ER &ER &ER &ER &ER \\%\hline
 thSPR \cite{Lin2009} &969 &1006 &1975 &118.39 &5.5m  \\%\hline
 thTBR \cite{Lin2009} &969 &1006 &1975 &118.09 &4.5m \\%\hline
 Supertriplet \cite{Ranwez2010} & 125 & 2175 & 2300 & ER & 59s \\%\hline
 COSPEDTree &510 &1001 &1511 &80.43 &11.7m \\%\hline
  \textbf{COSPEDTree-II} &\textbf{732} &\textbf{864} &\textbf{1566} &\textbf{95.2} &\textbf{2s + 1s} \\%\hline
  \textbf{COSPEDTree-II+B} &\textbf{1240} &\textbf{667} &\textbf{1907} &\textbf{102.18} &\textbf{2s+1s+43s} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_Cetartiodactyla}
\end{table}

\begin{table}\center\scriptsize
\caption{Results for Mammal \cite{Ranwez2007, Ranwez2010} dataset
($M$ = 12958, $N$ = 33)}
\begin{tabular}{|p{2.4cm}|p{0.6cm}|p{0.6cm}|p{0.6cm}|p{0.6cm}|p{1.4cm}|}\hline
 \textbf{Method} & \textbf{FP} & \textbf{FN} &
 \textbf{RF} & \textbf{MAST} & \textbf{Runtime} \\\hline
 PhySIC \cite{Ranwez2007} &17414 &254527 &271941 &968 &36s \\%\hline
 RFS \cite{Bansal2010} &ER &ER &ER &ER &ER \\%\hline
 thSPR \cite{Lin2009} & 272752 & 296159 & 568911 & 8378 & 7s  \\%\hline
 thTBR \cite{Lin2009} & 276104 & 301787 & 577891 & 8378 & 7s \\%\hline
 Supertriplet \cite{Ranwez2010} & 71117 & 105671 & 176788 & ER &6s \\%\hline
 COSPEDTree &35124 &141295 &176419 &4441.5 &5.3m \\%\hline
 \textbf{COSPEDTree-II} &\textbf{39079} &\textbf{134834} & \textbf{173913} &\textbf{4577.26} &\textbf{2m+0.1s} \\%\hline
 \textbf{COSPEDTree-II+B} &\textbf{104226} &\textbf{98407} & \textbf{202633} &\textbf{8365.57} &\textbf{2m+0.1s+1m} \\\hline
\end{tabular}
\label{tab:perf_cospedtree_Mammal}
\end{table}

\subsection{Computational complexity of COSPEDTree-II}
\label{subsec:complexity}

For $M$ input trees covering a total of $N$ taxa, both COSPEDTree
\cite{Sourya2014} and COSPEDTree-II incurs \BigO{MN^2} time complexity
for extracting the couplet based measures from the trees. These
methods differ in their subsequent steps.
COSPEDTree first resolves individual couplets in \BigO{N^2\lg{N}} time
(as shown in \cite{Sourya2014}), and subsequently partitions the taxa
set according to the relation $r_3$, to form a DAG containing
$N_C$ ($< N$) nodes (taxa clusters). Formation of a supertree from
this DAG involves \BigO{N_C^3} time complexity \cite{Sourya2014}.

COSPEDTree-II, on the other hand, first forms
the taxa clusters in \BigO{N^2} time (processing time for all
couplets). Subsequently, support scores for individual relations between each pair of
taxa clusters are placed in the max-priority queue $Q$.
Here, size of $Q$ is \BigO{N_C^2}, considering $N_C$ as the
number of taxa clusters. During each iteration, maintaining the
max-priority property of $Q$ requires \BigO{\lg{N_C}} time. So,
the complete iterative stage to resolve all pairs of clusters
(assigning connectivities between them) involves
\BigO{N_C^2\lg{N_C}} time complexity. As in general,
$N_C$ is considerably lower than $N$, this iterative step in
COSPEDTree-II is much faster than COSPEDTree.

Resolving individual pair of clusters, rather than the couplets,
enables COSPEDTree-II to achieve a significant speedup.
Suppose, $|X|$ denotes the cardinality of a taxa cluster $X$. So,
for a pair of taxa clusters $X$ and $Y$, COSPEDTree \cite{Sourya2014}
resolves all $|X|$ $\times$ $|Y|$ couplets, and maintains their
relations (and the transitive connectivities inferred
from these relations). But COSPEDTree-II resolves $X$ and $Y$
by processing only one relation between them. So, for this
cluster pair, speedup achieved by COSPEDTree-II is
$\approx$ $|X|$ $\times$ $|Y|$.
For a total of $N_C$ taxa clusters, number of cluster pairs
is $\binom{N_C}{2}$. Thus, overall speedup achieved by
COSPEDTree-II is $\approx$
$\sum_{X, Y \in \binom{N_C}{2}}$ $|X|$ $\times$ $|Y|$.

To derive the time complexity associated with the binary
refinement of COSPEDTree-II, suppose $m$ is the number
of internal nodes in \textbf{T} having degree $> 2$.
Further, suppose $n$ ($> 2$) denotes the maximum degree of
multi-furcation among all of these nodes. In such a case,
applying thTBR \cite{Lin2009} for a particular internal
node involves maximum \BigO{Mn^3} time complexity. So, overall
complexity of the binary refinement stage is \BigO{Mn^3m}.

COSPEDTree \cite{Sourya2014} involves a storage complexity
of \BigO{N^2}, to store the couplet based measures.
COSPEDTree-II uses additional storage space for storing
the set of excess taxa $U^{\mbox{\textbf{G}}}_{pq}$ for
individual couplets ($p,q$). As $0 \leq |U^{\mbox{\textbf{G}}}_{pq}| \leq (N - 2)$,
the space complexity of COSPEDTree-II is \BigO{N^3}.

\section{Experimental Results}
\label{sec:Results}

Both COSPEDTree and COSPEDTree-II are implemented in Python (version 2.7).
Tree topologies are processed by the
phylogenetic library Dendropy \cite{Sukumaran2010}. A desktop
having Intel\textsuperscript{\textregistered} Quad CoreIntel\textsuperscript{\texttrademark}
i5-3470 CPU, with 3.2 GHz processor and 8 GB RAM, is used to
execute these methods.

\subsection{Dataset}

COSPEDTree-II is tested with the datasets like
Marsupials (267 taxa and 158 input trees) \cite{Cardillo2004},
Placental Mammals (726 trees and 116 taxa) \cite{Beck2006},
Seabirds (121 taxa and 7 trees) \cite{Kennedy2002},
Temperate Herbaceous Papilionoid Legumes (THPL) (19 trees and
558 taxa) \cite{Wojciechowski2000}. Work in \cite{Swenson2011}
modified these datasets by removing duplicate taxon names and
few infrequent taxa information\footnote{Datasets are downloaded
from the link \url{http://www.cs.utexas.edu/~phylo/software/superfine/submission/.}}.
We have also experimented with Mammal dataset \cite{Ranwez2007, Ranwez2010}
consisting of 12958 trees and 33 taxa\footnote{Downloaded from the link
http://www.supertriplets.univ-montp2.fr/.}. In addition, the dataset
Cetartiodactyla (201 input trees and 299 taxa) \cite{Price2005} is also
tested\footnote{Maintained in TreeBASE \cite{Sanderson1994},
and is downloaded from the link
\url{https://treebase.org/treebase-web/search/study/summary.html?id=1271}.}.

\subsection{Performance measures}

Performance comparison between COSPEDTree-II and the reference approaches,
employs the following measures:

\begin{enumerate}
 \item \textbf{False positive distance} FP(\textbf{T}, $t_j$): Number of internal branches
 present in the supertree \textbf{T}, but not in the input tree $t_{j}$
 $(1 \leq j \leq M)$.
 \item \textbf{False negative distance} FN(\textbf{T}, $t_j$): Number of internal branches
 present in $t_{j}$ but not in \textbf{T}.
 \item \textbf{Robinson-Foulds distance} RF(\textbf{T}, $t_j$):
 Defined as FP(\textbf{T}, $t_j$) + FN(\textbf{T}, $t_j$).
 \item \textbf{Maximum agreement subtree} MAST(\textbf{T}, $t_j$):
 Let $N_1$ be the number of taxa contained in the maximum
 agreement subtree (MAST) common to $T$ and $t_{j}$. Then,
 MAST(\textbf{T}, $t_j$) = $\frac{N_1}{|L(t_j)|}$. This measure is
 computed using Phylonet \cite{Than2008}.
\end{enumerate}

Above measures are accumulated for all
the input trees $t_{j}$ $(1 \leq j \leq M)$, to be used as the final
performance measures. Supertree producing lower values of
the sum of FP, FN, and RF values is considered better. On the other hand,
supertree having higher sum of MAST score is considered superior.

\subsection{Performance comparison}

We have reported the results for the following two variations of COSPEDTree-II:

\begin{enumerate}
 \item \textbf{COSPEDTree-II}: Produces supertree with possible multi-furcations.
 \item \textbf{COSPEDTree-II + B}: Produces completely resolved binary supertrees,
 by applying the binary refinement suggested in section~\ref{subsec:refine_tree}.
\end{enumerate}

Tables~\ref{tab:perf_cospedtree_marsupials}
to \ref{tab:perf_cospedtree_Mammal} compare the performances
of both of these variants, and with the reference approaches as well.
Reference methods marked with a symbol `*', could
not be executed in all datasets, either due to the unavailability of
corresponding source code, or due to their very high computational complexity.
In such a case, we have used their results (both
topological performance and running time) published in
the existing studies \cite{Swenson2011}. The approaches MRP and
superfine require PAUP* \cite{Swofford2003} to execute, which is a
commercial tool and not available to us. So, these methods could not
be tested in all datasets. Missing entries are indicated by `-'.

The methods RFS \cite{Bansal2010} and
Supertriplet \cite{Ranwez2010} produced errors in parsing
few of the input datasets. Entries showing `ER'
indicate these errors. Supertrees generated by
Supertriplet \cite{Ranwez2010} could not be
parsed by Phylonet \cite{Than2008}. So, we could not compute the
MAST scores for these trees. Finally,
a symbol `F' indicates that corresponding method could not
produce a valid supertree for that dataset.

Results show that COSPEDTree-II produces better resolved
supertrees than COSPEDTree, as indicated by
lower FN, and mostly lower RF values for individual datasets.
COSPEDTree-II also achieves higher MAST scores for these datasets.
COSPEDTree-II+B produces completely resolved
binary supertrees. So, the number of FN branches reduces.
However, as the input trees
may not be fully resolved (may contain multi-furcating nodes),
number of FP branches increases considerably.
As COSPEDTree-II+B produces completely resolved
supertrees, corresponding MAST scores are much higher than COSPEDTree-II.

Comparison with reference approaches shows that only
RFS \cite{Bansal2010} produces supertrees with consistently lower RF
and higher MAST scores than COSPEDTree-II. The method Superfine \cite{Swenson2011}
performs better than COSPEDTree-II for the datasets Seabirds and
THPL, while our methods perform slightly better (in terms of lower RF and
higher MAST score) for the Marsupials and Placental Mammals dataset.
Superfine does not always generate strictly binary (completely resolved)
supertrees (for example, in the THPL dataset), unlike COSPEDTree-II+B.
Such a supertree exhibits much lower RF, but also much lower
MAST score (compared to COSPEDTree-II+B).

Matrix based methods like Minflip, SFIT, MMC, are outperformed by
COSPEDTree-II. Veto approaches like SCM, PhySIC, produce supertrees with
the lowest (mostly zero) FP branches, by not including any conflicting
clades. In such a case, the number of FN branches becomes very high,
and MAST scores of these trees also become much lower. COSPEDTree-II also
produces significantly better results than MRP PAUP for all the datasets
except Cetartiodactyla. Subtree decomposition based approaches like thSPR, thTBR,
produce slightly higher MAST score values than COSPEDTree-II, since these
methods directly synthesize input triplets, or in general, subtree topologies.
Considering the measure RF, on the other hand, these methods are mostly outperformed
by COSPEDTree-II.

\subsection{Runtime Comparison}

Tables~\ref{tab:perf_cospedtree_marsupials} to \ref{tab:perf_cospedtree_Mammal}
express the running time of COSPEDTree-II and COSPEDTree-II+B for different
datasets, in the formats (A+B) or (A+B+C), respectively, where:

\begin{enumerate}
 \item A = Time to extract the couplet based measures from the input trees.
 \item B = Time to process the couplets and cluster pairs, to produce
 a (possibly not binary) supertree.
 \item C = Time required to refine the non-resolved supertree into a
 strict binary tree.
\end{enumerate}

We observe that COSPEDTree-II incurs a significant fraction of its
running time in the stages A and C. The stage A depends on
the processing speed of the python based phylogenetic library Dendropy
\cite{Sukumaran2010}. On the other hand,
running time for the stage C depends both
on the construction of $t'_{j|X}$ from individual $t_j$
for all the multi-furcating nodes, and on the execution of
thTBR \cite{Lin2009}. Results show that COSPEDTree-II
incurs much lower running time than COSPEDTree.
Excluding the binary refinement stage, the running time is decreased by
a factor from 2 (for the dataset Mammal \cite{Ranwez2007, Ranwez2010}) to 135
(for the dataset Cetartiodactyla \cite{Price2005}).

When the number of taxa is high (such as Marsupials \cite{Cardillo2004},
Cetartiodactyla \cite{Price2005}), COSPEDTree-II exhibits much
lower running time than the triplet based methods \cite{Lin2009},
\cite{Ranwez2010}, due to its lower time complexity. For
datasets with large number of trees, COSPEDTree-II incurs
slightly higher running time than these methods, due to
the time associated in extracting the couplet based measures.

\section{Conclusion}

We have proposed COSPEDTree-II, an improved couplet based supertree construction
method (extending our earlier proposed method COSPEDTree).
COSPEDTree-II produces supertrees with lower topological errors,
and incurs much lower running time (compared to COSPEDTree). A
binary refinement to generate a fully resolved supertree, is also
suggested. Due to its high performance and much lower running time,
COSPEDTree-II can be applied in large scale biological datasets.

\section*{Executable}

Executable and the results of COSPEDTree-II are provided in the link
\url{http://www.facweb.iitkgp.ernet.in/~jay/phtree/cospedtree2/cospedtree2.html}.

\section*{acknowledgements}

The first author acknowledges Tata Consultancy Services (TCS) for providing the research
scholarship.

\bibliographystyle{ieeetr}


\section{introduction}
In our previous work \cite{Liu:2016mqv}, as an example, we used the beam dump experiment E137 \cite{Bjorken:1988as} and the production of a new scalar boson to demonstrate our technique for analyzing of beam dump experiments. In this paper, we further include all possible new spin-0 and spin-1 particles, which we denote $\phi$; they are pseudoscalar, vector, and axial-vector bosons.

Beam dump experiments have been aimed at searching for new particles, such as dark photons and axions (see, e.g. \cite{Essig:2013lka} and references therein) that decay to lepton pairs and/or photons. Electron beam dumps in particular have received a large amount of theoretical attention in recent years~\cite{Bjorken:2009mm,Andreas:2012mt}. The typical setup of an electron beam dump experiment is to dump an electron beam into a target, in which the electrons are stopped. The new particles produced by the bremsstrahlung-like process pass through a shield region and decay. These new particles can be detected by their decay products, electron and/or photon pairs, measured by the detector downstream of the decay region. Previous earlier work simplified the necessary phase space integral by using the Weizs\"{a}cker-Williams (WW) approximation \cite{vonWeizsacker:1934nji,Williams:1935dka} which, also known as method of virtual quanta, is a semiclassical approximation. The idea is that the electromagnetic field generated by a fast moving charged particle is nearly transverse which is like a plane wave and can be approximated by real photon. The use of the  WW approximation in bremsstrahlung processes was developed in Refs.~\cite{Kim:1973he,Tsai:1973py} and applied to beam dump experiments in Refs.~\cite{Bjorken:2009mm,Tsai:1986tx}. The WW approximation simplifies evaluation of the integral over phase space and approximates the 2 particle to 3 particle (2 to 3) cross section in terms of a 2 particle to 2 particle (2 to 2) cross section. For the WW approximation to work in a beam dump experiment, it needs the incoming beam energy to be much greater than the mass of the new particle, $m_\phi$, and electron mass $m_e$.

The previous work \cite{Bjorken:2009mm} used the following three approximations:
\begin{enumerate}
\item WW approximation;
\item a further simplification of the phase space integral, see Eq. (\ref{eq:tmin tmax});
\item $m_\phi\gg m_e$.
\end{enumerate}
The combination of the first two approximations has been denoted \cite{Kim:1973he} the improved WW (IWW) approximation. The name ``improved WW" might be somewhat misleading since the procedure reduces the computational time but does not improve accuracy). In this paper, we will focus on examining the validity of WW and IWW approximations for the production of axions, dark photons and new axial-vector bosons. The third approximation used to simplify the calculation of amplitude, however, is not in our scope because it is merely a special case by cutting off our results when $m_\phi\lesssim 2m_e$. Nevertheless, we should point out that without using the third approximation we can use beam dump experiments to explore a larger parameter space.

The outline of this paper is as follows. In Sec.~\ref{sec:dynamics}, we setup the dynamics, and then calculate the decay width of new particles and the squared amplitude for 2 to 3 and 2 to 2 processes. In Sec. \ref{sec:cross section}, we show the 2 to 3 cross sections in the lab frame without any approximation on phase space and WW approximation is discussed. In Sec.~\ref{sec:cross section comparison}, we derive and compare the cross sections with and without approximations. In Sec.~\ref{sec:particle production}, we discuss the number of new particles produced in beam dump experiments. In Sec.~\ref{sec:exclusion plots}, we compare the exclusion plots for different bosons with and without approximations. A discussion is presented in Sec.~\ref{sec:discussion}.

\section{dynamics}\label{sec:dynamics}
For simplicity, we assume that there is only one new boson $\phi$, which only couples to electron by a Yukawa interaction, i.e. the boson does not couple to other standard model fermions other than electron. The Lagrangian contains either one of the following interactions
\begin{align}
\mathcal{L}_P&=i e\epsilon_P\phi\bar\psi\gamma_5\psi\nonumber\\
\mathcal{L}_V&=e\epsilon_V\phi_\mu\bar\psi\gamma^\mu\psi\\
\mathcal{L}_A&=e\epsilon_A\phi_\mu\bar\psi\gamma_5\gamma^\mu\psi\nonumber
\end{align}
where the subscripts $P$, $V$, and $A$ correspond to pseudoscalar, vector, and axial-vector, respectively; $\epsilon=g/e$, $g$ is the coupling of the new boson, and $e$ is the electric charge; $\psi$ is the electron field; $\gamma_5=-\frac{i}{4!}\epsilon_{\mu\nu\rho\sigma}\gamma^\mu\gamma^\nu\gamma^\rho\gamma^\sigma$; we choose the convention that there is an extra $i$ in $\mathcal{L}_P$, such that $\epsilon_P$ can be a non-negative number.

If $m_\phi>2m_e$, the dominant new boson decay is to electron pairs
\begin{align}\label{eq:decay to electrons}
\Gamma_{P}(\phi\to e^+e^-)&=\epsilon_P^2\frac{\alpha}{2}m_\phi\left(1-\frac{4m_e^2}{m_\phi^2}\right)^{1/2}\nonumber\\
\Gamma_{V}(\phi\to e^+e^-)&=\epsilon_V^2\frac{\alpha}{3}m_\phi\left(1+\frac{2m_e^2}{m_\phi^2}\right)\left(1-\frac{4m_e^2}{m_\phi^2}\right)^{1/2}\\
\Gamma_{A}(\phi\to e^+e^-)&=\epsilon_A^2\frac{\alpha}{3}m_\phi\left(1-\frac{4m_e^2}{m_\phi^2}\right)^{3/2}\nonumber,
\end{align}
where $\alpha$ is the fine structure constant.

If $m_\phi<2m_e$, the dominant decay channel involves photons produced through the electron loop. For pseudoscalar, it decays to two photons
\begin{align}\label{eq:P decay to photons}
\Gamma_{P}(\phi\to\gamma\gamma)=\epsilon_P^2\frac{\alpha^3}{4\pi^2}\frac{m_\phi^3}{m_e^2}f_P\left(\frac{m_\phi^2}{4m_e^2}\right)
\end{align}
where $f_P(\tau)=\frac{1}{64\tau^2}\left|\ln\left[1-2\left(\tau+\sqrt{\tau^2-\tau}\right)\right]^2 \right|^2$. For spin-1 particles, however, the two photon decay channel is forbidden by Landau--Yang theorem \cite{Landau:1948kw,Yang:1950rg,Zhemchugov:2014dza}. Therefore, the dominant decay channel of the vector boson is 3 photon decay
\begin{align}
\Gamma(\phi\to\gamma_1+\gamma_1+\gamma_3)=\frac{1}{64S\pi^3 m_\phi}\int^\frac{m_\phi}{2}_0dE_1\int^\frac{m_\phi}{2}_{\frac{m_\phi}{2}-E1}dE_2|\mathcal{M}|^2
\end{align}
where $S$ is the symmetry factor accounting for identical particles in the final state and in this case $S=3!$; $E_1$ and $E_2$ are energy of $\gamma_1$ and $\gamma_2$, respectively; $\mathcal{M}$ is the amplitude containing 6 diagrams. We express the decay rate in term of $\frac{m_\phi}{m_e}$ expansion
\begin{align}\label{eq:V decay to photons}
\Gamma_{V}(\phi\to3\gamma)=\epsilon_V^2\frac{\alpha^4}{2^7 3^6 5^2 \pi^3}\frac{m_\phi^9}{m_e^8}\left[\frac{17}{5}+\frac{67}{42}\frac{m_\phi^2}{m_e^2}+\frac{128941}{246960}\frac{m_\phi^4}{m_e^4}+\mathcal{O}\left(\frac{m_\phi^6}{m_e^6}\right)\right].
\end{align}
The leading term of this result agrees with \cite{Pospelov:2008jk}, which used effective field theory.

For axial-vector, the 3 photon decay channel is further forbidden by the charge conjugation symmetry (similar with the argument of Furry's theorem). Thus the dominant decay channel of the axial-vector boson is 4 photon decay. There are 24 diagrams and the 4 body phase space integral of the decay rate is done in Refs. \cite{Anastasiou:2003gr,Asatrian:2012tp}. We express the result in term of $\frac{m_\phi}{m_e}$ expansion
\begin{align}\label{eq:A decay to photons}
\Gamma_{A}(\phi\to 4\gamma)=\epsilon_A^2\frac{127\alpha^5}{2^{11} 3^8 5^4 7^2 \pi^4}\frac{m_\phi^{13}}{m_e^{12}}+\mathcal{O}\left(\frac{m_\phi^{15}}{m_e^{14}}\right).
\end{align}

\subsection{2 to 3 production}
\begin{figure}
\centering
\includegraphics[scale=0.8]{2_to_3}
\caption{\label{fig:2 to 3} Lowest order 2 to 3 production process: $e(p)+A(P_i)\rightarrow e(p')+A(P_f)+\phi(k)$. $A$, $\gamma$, $e$, and $\phi$ stand for the target atom, photon, electron, and the new boson.}
\end{figure}

The leading production process is the bremsstrahlung-like radiation of the new particle from the electron, shown in Fig.~\ref{fig:2 to 3},
\begin{align}\label{eq:2 to 3 production process}
e(p)+A(P_i)\rightarrow e(p')+A(P_f)+\phi(k)
\end{align}
where $e$, $A$, and $\phi$ stand for electron, target atom, and the new particle, respectively. We define the following quantities using the mostly-plus metric
\begin{align}\label{eq:2 to 3 variables}
\tilde{s}&=-(p'+k)^2-m_e^2=-2p'\cdotp k+m_\phi^2\nonumber\\
\tilde{u}&=-(p-k)^2-m_e^2=2p\cdotp k+m_\phi^2\nonumber\\
t_2&=-(p'-p)^2=2p'\cdotp p+2m_e^2\\
q&=P_i-P_f\nonumber\\
t&=q^2\nonumber
\end{align}
which satisfy
\begin{align}
\tilde{s}+t_2+\tilde{u}+t=m_\phi^2.
\end{align}

For definiteness, we assume the atom is a scalar boson (its spin is not consequential here) so that the Feynman rule for the photon-atom vertex is
\begin{align}
ieF(q^2)(P_i+P_f)_\mu\equiv ieF(q^2)P_\mu
\end{align}
where $F(q^2)$ is the form factor which accounts for the nuclear form factor \cite{DeJager:1987qc} and the atomic form factor \cite{atomic form factor}. Here, we only include the elastic form factor since the contribution of the inelastic one is much smaller and can be neglected in computing the cross section. The amplitude of the process in Fig.~\ref{fig:2 to 3} using the mostly-plus metric is
\begin{align}
\mathcal{M}^{23}_P&=ie^2g_P\frac{F(q^2)}{q^2}\bar{u}_{p',s'}\left[\slashed{P}\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_5+\gamma_5\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\slashed{P}\right]u_{p,s}\nonumber\\
\mathcal{M}^{23}_V&=e^2g_V\frac{F(q^2)}{q^2}\tilde{\epsilon}^\mu_{k,\lambda}\bar{u}_{p',s'}\left[\slashed{P}\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_\mu+\gamma_\mu\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\slashed{P}\right]u_{p,s}\\
\mathcal{M}^{23}_A&=e^2g_A\frac{F(q^2)}{q^2}\tilde{\epsilon}^\mu_{k,\lambda}\bar{u}_{p',s'}\left[\slashed{P}\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_5\gamma_\mu+\gamma_5\gamma_\mu\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\slashed{P}\right]u_{p,s}\nonumber
\end{align}
where $P$, $V$, and $A$ stand for pseudo-scalar, vector, and axial-vector, respectively; $u_{p,s}$ is the electron spinor and $s=\pm 1$; $\tilde{\epsilon}$ is the polarization of the new spin-1 particle and $\lambda=0,\,\pm 1$. The polarization sum for the new massive spin-1 particle is
\begin{align}
\sum_\lambda\tilde{\epsilon}^\mu_{k,\lambda}\tilde{\epsilon}^{\nu*}_{k,\lambda}=g^{\mu\nu}+\frac{k^\mu k^\nu}{m_\phi^2}.
\end{align}
After averaging and summing over initial and final spins, we have
\begin{align}
\overline{|\mathcal{M}^{23}_P|^2}&=\left(\frac{1}{2}\sum_s\right)\sum_{s'}|\mathcal{M}_P^{23}|^2=e^4g_P^2\frac{F(q^2)^2}{q^4}\mathcal{A}^{23}_P\nonumber\\
\overline{|\mathcal{M}^{23}_{V,A}|^2}&=\left(\frac{1}{2}\sum_s\right)\sum_{s'}\sum_{\lambda}|\mathcal{M}_{V,A}^{23}|^2=e^4g_{V,A}^2\frac{F(q^2)^2}{q^4}\mathcal{A}^{23}_{V,A}
\end{align}
where
\begin{align}
\mathcal{A}^{23}_P=&-\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}\tilde{u}}P^2-\frac{4t}{\tilde{s}\tilde{u}}(P\cdotp k)^2-\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}^2\tilde{u}^2}m_\phi^2\left[P^2 t+4\left(\frac{\tilde{u}P\cdotp p+\tilde{s}P\cdotp p'}{\tilde{s}+\tilde{u}}\right)^2\right]\nonumber\\
\mathcal{A}^{23}_V=&-2\frac{\tilde{s}^2+\tilde{u}^2}{\tilde{s}\tilde{u}}P^2-\frac{8t}{\tilde{s}\tilde{u}}\left[(P\cdotp p)^2+(P\cdotp p')^2-\frac{t_2+m_\phi^2}{2}P^2\right]\nonumber\\
&-2\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}^2\tilde{u}^2}(m_\phi^2+2m_e^2)\left[P^2 t+4\left(\frac{\tilde{u}P\cdotp p+\tilde{s}P\cdotp p'}{\tilde{s}+\tilde{u}}\right)^2\right]\\
\mathcal{A}^{23}_A=&-2\frac{\tilde{s}^2+\tilde{u}^2}{\tilde{s}\tilde{u}}P^2-\frac{8t}{\tilde{s}\tilde{u}}\left[(P\cdotp p)^2+(P\cdotp p')^2-\frac{t_2-m_\phi^2}{2}P^2\right]-4m_e^2\frac{(\tilde{s}+\tilde{u})^2 P^2+4t(P\cdotp k)^2}{m_\phi^2\tilde{s}\tilde{u}}\nonumber\\
&-2\frac{(\tilde{s}-\tilde{u})^2}{\tilde{s}^2\tilde{u}^2}(m_\phi^2-4m_e^2)\left[P^2 t+4\left(\frac{\tilde{u}P\cdotp p+\tilde{s}P\cdotp p'}{\tilde{s}-\tilde{u}}\right)^2\right]\nonumber.
\end{align}

\subsection{2 to 2 production}
\begin{figure}
\centering
\includegraphics[scale=0.8]{2_to_2}
\caption{\label{fig:2 to 2}  Lowest order 2 to 2 production process: $e(p)+\gamma(q)\rightarrow e(p')+\phi(k)$. $\gamma$, $e$, and $\phi$ stand for photon, electron, and the new boson.}
\end{figure}

For the 2 to 2 process in Fig. \ref{fig:2 to 2}, a ``subprocess'' of the full 2 to 3 interaction,
\begin{align}\label{eq:2 to 2 production process}
e(p)+\gamma(q)\rightarrow e(p')+\phi(k).
\end{align}
With the same definition in Eq. (\ref{eq:2 to 3 variables}), $\tilde{s}$, $\tilde{u}$, and $t_2$ satisfy
\begin{align}
\tilde{s}+t_2+\tilde{u}&=m_\phi^2
\end{align}
and the amplitude in Fig. \ref{fig:2 to 2} is
\begin{align}
\mathcal{M}^{22}_P=&ieg_P\epsilon^\mu_{q,\lambda}\bar{u}_{p',s'}\left[\gamma_\mu\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_5+\gamma_5\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\gamma_\mu\right]u_{p,s}\nonumber\\
\mathcal{M}^{22}_V=&eg_V\epsilon^\mu_{q,\lambda}\tilde{\epsilon}^\nu_{k,\lambda'}\bar{u}_{p',s'}\left[\gamma_\mu\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_\nu+\gamma_\nu\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\gamma_\mu\right]u_{p,s}\\
\mathcal{M}^{22}_A=&eg_A\epsilon^\mu_{q,\lambda}\tilde{\epsilon}^\nu_{k,\lambda'}\bar{u}_{p',s'}\left[\gamma_\mu\frac{(\slashed{p}-\slashed{k})-m_e}{\tilde{u}}\gamma_5\gamma_\nu+\gamma_5\gamma_\nu\frac{(\slashed{p'}+\slashed{k})-m_e}{\tilde{s}}\gamma_\mu\right]u_{p,s}\nonumber
\end{align}
where $\epsilon$ is the photon polarization vector and $\lambda=\pm 1$. The polarization sum for photon is
\begin{align}
\sum_\lambda \epsilon^\mu_{q,\lambda}\epsilon^{\nu*}_{q,\lambda}=g^{\mu\nu}.
\end{align}

After averaging and summing over the initial and final spins and polarization,
\begin{align}\label{eq:2 to 2 M}
\overline{|\mathcal{M}^{22}|^2}_{P}&=\left(\frac{1}{2}\sum_s\right)\sum_{s'}\left(\frac{1}{2}\sum_\lambda\right)|\mathcal{M}^{22}_P|^2=e^2g_P^2\mathcal{A}^{22}_{P}\nonumber\\
\overline{|\mathcal{M}^{22}|^2}_{V,A}&=\left(\frac{1}{2}\sum_s\right)\sum_{s'}\left(\frac{1}{2}\sum_\lambda\right)\sum_{\lambda'}|\mathcal{M}^{22}_{V,A}|^2=e^2g_{V,A}^2\mathcal{A}^{22}_{V,A}
\end{align}
where
\begin{align}\label{eq:2 to 2 A}
\mathcal{A}^{22}_P=&-\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}\tilde{u}}+2m_\phi^2\left[\left(\frac{\tilde{s}+\tilde{u}}{\tilde{s}\tilde{u}}\right)^2m_e^2-\frac{t_2}{\tilde{s}\tilde{u}}\right]\nonumber\\
\mathcal{A}^{22}_V=&4-2\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}\tilde{u}}+4(m_\phi^2+2m_e^2)\left[\left(\frac{\tilde{s}+\tilde{u}}{\tilde{s}\tilde{u}}\right)^2m_e^2-\frac{t_2}{\tilde{s}\tilde{u}}\right]\\
\mathcal{A}^{22}_A=&4-\left(2+\frac{4m_e^2}{m_\phi^2}\right)\frac{(\tilde{s}+\tilde{u})^2}{\tilde{s}\tilde{u}}+4(m_\phi^2-4m_e^2)\left[\left(\frac{\tilde{s}+\tilde{u}}{\tilde{s}\tilde{u}}\right)^2m_e^2-\frac{t_2}{\tilde{s}\tilde{u}}\right]\nonumber.
\end{align}

\section{cross section and Weizs\"{a}cker-Williams approximation}\label{sec:cross section}
\subsection{2 to 3 cross section}
The cross section for the 2 to 3 process in the lab frame, see Fig. \ref{fig:2 to 3} and Ref. \cite{Liu:2016mqv} for more detail, is given by
\begin{align}\label{eq:2 to 3}
\frac{d\sigma}{dx d\cos\theta}=\epsilon^2\frac{\alpha^3}{8M^2}\frac{|\textbf{k}|E}{|\textbf{p}|V}\int^{t_{max}}_{t_{min}}dt\frac{F(t)^2}{t^2}\int_0^{2\pi}\frac{d\phi_q}{2\pi}\mathcal{A}^{23}
\end{align}
where $x\equiv E_k/E$; $M$ is the mass of the target atom; $\phi_q$ is azimuthal angles of \textbf{q} in the direction of $\mathbf{V}=\mathbf{k}-\mathbf{p}$; $V=|\textbf{V}|$ and $Q=|\mathbf{q}|$; $t(Q)=q^2=2M(\sqrt{M^2+Q^2}-M)$, $t_{max}=t(Q_+)$, $t_{min}=t(Q_-)$, and
\begin{align}
Q_\pm=\frac{V[\tilde{u}+2M(E'+E_f)]\pm(E'+E_f)\sqrt{\tilde{u}^2+4M\tilde{u}(E'+E_f)+4M^2V^2}}{2(E'+E_f)^2-2V^2}.
\end{align}

\subsection{Weizs\"{a}cker-Williams approximation}
It is explained in Ref.~\cite{Kim:1973he} that the WW approximation relies on the incoming electron energy being much greater than $m_\phi$ and $m_e$, such that the final state electron and the new boson are highly collinear. using WW approximation, the phase space integral can be approximated by
\begin{align}\label{eq:WW}
\frac{1}{8M^2}\int\frac{d\phi_q}{2\pi}\mathcal{A}^{23}\approx\frac{t-t_{min}}{2t_{min}}\mathcal{A}^{22}_{t=t_{min}}.
\end{align}
Following the discussion in Refs.~\cite{Liu:2016mqv,Bjorken:2009mm,Tsai:1986tx}, near $t=t_{min}$ (when $\mathbf{q}$ and $\mathbf{V}=\mathbf{k}-\mathbf{p}$ are collinear), we can approximate the following quantities
\begin{align}\label{eq:WW variables}
\tilde{s}&\approx-\frac{\tilde{u}}{1-x}\nonumber\\
\tilde{u}&\approx-xE^2\theta_\phi^2-m_\phi^2\frac{1-x}{x}-m_e^2 x\nonumber\\
t_2&\approx\frac{\tilde{u}x}{1-x}+m_\phi^2\\
V&\approx E(1-x)\nonumber\\
t_{min}&\approx\frac{\tilde{s}^2}{4E^2}\nonumber.
\end{align}
Using the above approximations to evaluated $\mathcal{A}^{22}$ at $t=t_{min}$, we have
\begin{align}\label{eq:2 to 2 A tmin}
\mathcal{A}^{22}_{P,t=t_{min}}\approx&\frac{x^2}{1-x}+2m_\phi^2\frac{\tilde{u}x+m_\phi^2(1-x)+m_e^2x^2}{\tilde{u}^2}\nonumber\\
\mathcal{A}^{22}_{V,t=t_{min}}\approx&2\frac{2-2x+x^2}{1-x}+4(m_\phi^2+2m_e^2)\frac{\tilde{u}x+m_\phi^2(1-x)+m_e^2x^2}{\tilde{u}^2}\\
\mathcal{A}^{22}_{A,t=t_{min}}\approx&\frac{4m^2x^2}{m_\phi^2(1-x)}+2\frac{2-2x+x^2}{1-x}+4(m_\phi^2-4m_e^2)\frac{\tilde{u}x+m_\phi^2(1-x)+m_e^2x^2}{\tilde{u}^2}\nonumber.
\end{align}

\section{cross section comparison}\label{sec:cross section comparison}

\begin{figure}
\centering
\subfigure[\;$d\sigma_P/dx$]{\includegraphics[scale=0.95]{pseudoscalar_cross_section}}
\subfigure[\;relative error of $d\sigma_P/(\epsilon_P^2 dx)$]{\includegraphics[scale=0.95]{pseudoscalar_cross_section_relative_error}}
\caption{\label{fig:pseudoscalar_cross_section} Cross section of a pseudoscalar boson production: the solid green, dashed red, and dotted blue lines correspond to the differential cross section with no, WW, and IWW approximation. The relative error of $\mathcal{O}$ is defined by $(\mathcal{O}_{\rm approx.}-\mathcal{O}_{\rm exact})/\mathcal{O}_{\rm exact}$.}
\end{figure}

\begin{figure}
\centering
\subfigure[\;$d\sigma_V/dx$]{\includegraphics[scale=0.95]{vector_cross_section}}
\subfigure[\;relative error of $d\sigma_V/(\epsilon_V^2 dx)$]{\includegraphics[scale=0.95]{vector_cross_section_relative_error}}
\caption{\label{fig:vector_cross_section} Cross section of a vector boson production: see caption of Fig. \ref{fig:pseudoscalar_cross_section} for detail.}
\end{figure}

\begin{figure}
\centering
\subfigure[\;$d\sigma_A/dx$]{\includegraphics[scale=0.95]{axial_vector_cross_section}}
\subfigure[\;relative error of $d\sigma_A/(\epsilon_A^2 dx)$]{\includegraphics[scale=0.95]{axial_vector_cross_section_relative_error}}
\caption{\label{fig:axial_vector_cross_section} Cross section of a axial-vector boson production: see caption of Fig. \ref{fig:pseudoscalar_cross_section} for detail.}
\end{figure}

To test approximations of the cross section for $\phi$ production, we examine three cases.
\begin{enumerate}
\item The complete calculation, Eq. (\ref{eq:2 to 3}),
\begin{align}\label{eq:d sigma dx 1}
\frac{d\sigma}{dx}=\epsilon^2\frac{\alpha^3}{8M^2}\frac{|\textbf{k}|E}{|\textbf{p}|}\int_0^{\theta_{max}} d\cos\theta\frac{1}{V}\int^{t_{max}}_{t_{min}}dt\frac{F(t)^2}{t^2}\int_0^{2\pi}\frac{d\phi_q}{2\pi}\mathcal{A}^{23},
\end{align}
where $\theta_{max}$ depends on the configuration of the detector. For beam dump E137, $\theta_{max}\approx 4.4\times10^{-3}$.

\item WW: using the WW approximation, Eq. (\ref{eq:WW}),
\begin{align}\label{eq:d sigma dx 2}
\left(\frac{d\sigma}{dx}\right)_{WW}=2\epsilon^2\alpha^3|\textbf{k}|E(1-x)\int_0^{\theta_{max}} d\cos\theta\frac{\mathcal{A}^{22}_{t=t_{min}}}{\tilde{u}^2}\chi,
\end{align}
where $\theta_{max}$ is the same as the first case and $\chi=\int^{t_{max}}_{t_{min}}dt\frac{t-t_{min}}{t^2}F(t)^2$. Note that the upper and lower limits of $\chi$ depend on $x$ and $\theta$.

\item Improved WW (IWW): If the upper and lower limits of the $t$-integral in $\chi$ in Eq. (\ref{eq:d sigma dx 2}) are not sensitive to $x$ and $\theta$; i.e., the integration limit can be set to be independent of $x$ and $\theta$, we can further approximate the integration limits of $t$. Similar to the argument in Ref.~\cite{Bjorken:2009mm}, we set
\begin{align}\label{eq:tmin tmax}
t_{min}=\left(\frac{m_\phi^2}{2E}\right)^2 {\rm\; and\;\;} t_{max}=m_\phi^2+m_e^2,
\end{align}
which is valid when the production cross section is dominantly collinear with $x$ close to 1. The difference in $t_{max}$ between \cite{Bjorken:2009mm} and our approach is because we do not assume $m_\phi\gg m_e$. Therefore, we can pull $\chi$ out of the integral over $\cos\theta$. Then, changing variables from $\cos\theta$ to $\tilde{u}$ and extending the lower limit of $\tilde{u}$ to $-\infty$,
\begin{align}\label{eq:d sigma dx 3-1}
\left(\frac{d\sigma}{dx}\right)_{IWW}&=\epsilon^2\alpha^3\chi\frac{|\textbf{k}|}{E}\frac{1-x}{x}\int^{\tilde{u}_{max}}_{-\infty}d\tilde{u}\frac{\mathcal{A}^{22}_{t=t_{min}}}{\tilde{u}^2}
\end{align}
using Eq. (\ref{eq:2 to 2 A tmin}) we have
\begin{align}\label{eq:d sigma dx 3-2}
\left(\frac{d\sigma_P}{dx}\right)_{IWW}=&\epsilon_P^2\alpha^3\chi\frac{|\textbf{k}|}{E}\frac{m_e^2x^2-2x \tilde{u}_{max}}{3\tilde{u}_{max}^2}\nonumber\\
\left(\frac{d\sigma_V}{dx}\right)_{IWW}=&2\epsilon_V^2\alpha^3\chi\frac{|\textbf{k}|}{E}\frac{m_e^2x(-2+2x+x^2)-2(3-3x+x^2)\tilde{u}_{max}}{3x\tilde{u}_{max}^2}\\
\left(\frac{d\sigma_A}{dx}\right)_{IWW}=&2\epsilon_A^2\alpha^3\chi\frac{|\textbf{k}|}{E}\left[\frac{m_e^2x(2-x)^2-2(3-3x+x^2)\tilde{u}_{max}}{3x\tilde{u}_{max}^2}+\frac{2m_e^2(1-x)}{\tilde{u}_{max}(\tilde{u}_{max}+m_e^2x)}\right]\nonumber
\end{align}
where $\tilde{u}_{max}=-m_\phi^2\frac{1-x}{x}-m_e^2 x$. We emphasize that the name ``improved" means reducing the computational time (because of one fewer integral than in the WW approximation above) and does not imply more accuracy.

\end{enumerate}

In Figs. \ref{fig:pseudoscalar_cross_section}--\ref{fig:axial_vector_cross_section}, we show the cross sections in each of the above three cases for five values of the new boson mass, setting the incoming electron beam energy to 20 GeV and the target to be aluminum. The cross sections for different bosons are different, as expected, because they have different dynamics; the relative errors with the same approximation between different bosons are similar, also as expected, because the approximation deals with phase space integral and the kinematics between different bosons are similar.

In both approximations, the cross section is of the same order of magnitude as that using the complete calculation. However, there are regions where there are ${\cal O}\left(1\right)$ relative errors. The WW approximation (dashed red lines in Figs.~\ref{fig:pseudoscalar_cross_section}--\ref{fig:axial_vector_cross_section}) can differ from the complete calculation by 100\% when $m_\phi\lesssim 1$ MeV; in the IWW case (dotted blue lines in Figs.~\ref{fig:pseudoscalar_cross_section}--\ref{fig:axial_vector_cross_section}), the approximation starts to fail when $m_\phi\gtrsim 100$ MeV.

\section{particle production}\label{sec:particle production}

There are two characteristic lengths which are crucial in beam dump experiments. The first is the decay length of the new particle in the lab frame,
\begin{align}
l_\phi=\frac{E_k}{m_\phi}\frac{1}{\Gamma_\phi},
\end{align}
where $\Gamma_\phi=\Gamma(\phi\to e^+e^-)+\Gamma(\phi\to{\rm photons})$, see Eqs. (\ref{eq:decay to electrons},\ref{eq:P decay to photons},\ref{eq:V decay to photons},\ref{eq:A decay to photons}). The new particle, after production, must decay after going through the target and shielding and before going through the detector in order to be observed. If the target is thick (much greater than a radiation length), most of the new particles will be produced in the first few radiation lengths. The production rate is approximately proportional to the probability $e^{-L_{sh}/l_\phi}(1-e^{-L_{dec}/l_\phi})$, where $L_{sh}$ is length of the target and shield and $L_{dec}$ is length for the new particle to decay into electron or photon pairs after the shield and before the detector.

The second characteristic length is the absorption length
\begin{align}
\lambda=\frac{1}{n_e\sigma_{abs}},
\end{align}
where $n_e$ is the number density of the target electrons and $\sigma_{abs}$ is the cross section of absorption process. The leading process of absorption is
\begin{align}\label{eq:absorption}
e(p)+\phi(k)\rightarrow e(p')+\gamma(q),
\end{align}
which is related to the 2 to 2 production process Eq. (\ref{eq:2 to 2 production process}) via crossing symmetry $\tilde{s}\leftrightarrow\tilde{u}$. Since Eq. (\ref{eq:2 to 2 A}) is symmetric in $\tilde{s}\leftrightarrow\tilde{u}$, the algebraic form of amplitude squared of absorption process is the same as Eq. (\ref{eq:2 to 2 A}) but differs by a factor $c$ from summing over final state instead of averaging over initial state in Eq. (\ref{eq:2 to 2 M})
\begin{align}
\mathcal{A}^{22}_{abs}=c\mathcal{A}^{22}
\end{align}
where $c=2$ for spin-0 and $c=\frac{2}{3}$ for spin-1 particles.

The cross section of the process (\ref{eq:absorption}) is
\begin{align}
\frac{d\sigma}{d\Omega}_{abs}&=\frac{1}{64\pi^2 m}\frac{|\mathbf{q}|}{|\mathbf{k}|}\frac{\overline{|\mathcal{M}^{22}_{abs}|^2}}{E_k+m-|\mathbf{k}|\cos\theta_\gamma}\\
\sigma_{abs}&=\epsilon^2\frac{c\pi\alpha^2}{2m|\mathbf{k}|}\int_{-1}^1 d\cos\theta_\gamma\frac{|\mathbf{q}|\mathcal{A}^{22}}{E_k+m-|\mathbf{k}|\cos\theta_\gamma}
\end{align}
where $\theta_\gamma$ is the angle between outgoing photon and incoming new particle. The new particle, after produced, must not be absorbed by the target and shield to be detected. If the target is thick (much greater than absorption length), the production rate will be approximately proportional to the probability $e^{-L_{sh}/\lambda}$.

The number of the new particles produced in terms of the cross section (without considering the absorption process) can be found in, e.g., Refs.~\cite{Bjorken:2009mm,Tsai:1986tx,Andreas:2012mt}. Using the thick target approximation and including the absorption process, we find
\begin{align}
N_\phi\approx\frac{N_eX}{M}\int_{E_{min}}^{E_0}dE\int_{x_{min}}^{x_{max}}dx\int_0^TdtI_e(E_0,E,t)\frac{d\sigma}{dx}e^{-L_{sh}\left(\frac{1}{l_\phi}+\frac{1}{\lambda}\right)}(1-e^{-L_{dec}/l_\phi})
\end{align}
where $M$ is the mass of the target atom (aluminum); $N_e$ is the number of incident electrons; $X$ is the unit radiation length of the target; $E_0$ is the incoming electron beam energy, $E_{min}=m_e+\max(m_\phi,E_{cut})$ and $x_{min}=\frac{\max(m_\phi,E_{cut})}{E}$ where $E_{cut}$ is the measured energy cutoff depending on the detectors; $x_{max}$, which is smaller  but very close to 1 ($x_{max}$ can be approximated to be $1-\frac{m_e}{E}$ if the new particle and electron initial and final state are collinear); $T=\rho L_{sh}/X$ where $\rho$ is the density of the target; $l_\phi$ is the decay length of the new particle in lab frame; $\lambda$ is the absorption length of the new particle passing through the target and shield; $I_e$, derived in Ref.~\cite{Tsai:1966js}, is the energy distribution of the electrons after passing through a medium of $t$ radiation length
\begin{align}
I_e(E_0,E,t)=\frac{\left(\ln\frac{E_0}{E}\right)^{bt-1}}{E_0\Gamma(bt)}
\end{align}
where $\Gamma$ is the gamma function and $b=4/3$. For beam dump E137 which we take as our prototypical setup, $E_0=20$ GeV and $E_{cut}=2$ GeV; $N_e=1.87\times 10^{{20}}$; $L_{sh}=179$ m and $L_{dec}=204$ m. The experiment has a null result which translates to 95\% C.L. of $N_\phi$ to be 3 events.

\section{exclusion plots}\label{sec:exclusion plots}

\begin{figure}
\centering
\includegraphics[scale=2]{E137all}
\caption{\label{fig:E137all} Exclusion (shaded region) plot for pseudoscalar (black), vector (dashed blue), and axial-vector (dotted red) bosons without approximation using the beam dump experiment E137.}
\end{figure}

\begin{figure}
\centering
\subfigure[\;exclusion plot (mass in linear scale)]{\includegraphics[scale=1]{E137P_zoom_linear}}
\subfigure[\;relative error of exclusion boundary]{\includegraphics[scale=1]{E137P_relative_error}}
\caption{\label{fig:E137P} Exclusion (shaded region) plot for $\epsilon_P$ using the beam dump experiment E137: (a) The solid black, dashed red, and dotted blue lines correspond to using the differential cross section with no, WW, and IWW approximation. (b) The solid red and dashed blue lines correspond to the relative error of the exclusion boundary of (a) for a fixed value of $m_\phi$ with WW and IWW approximation. The relative error of $\mathcal{O}$ is defined by $(\mathcal{O}_{\rm approx.}-\mathcal{O}_{\rm exact})/\mathcal{O}_{\rm exact}$. The thin and thick lines correspond to the upper and lower boundaries of the exclusion plot.}
\end{figure}

\begin{figure}
\centering
\subfigure[\;exclusion plot (mass in linear scale)]{\includegraphics[scale=1]{E137V_zoom_linear}}
\subfigure[\;relative error of exclusion boundary]{\includegraphics[scale=1]{E137V_relative_error}}
\caption{\label{fig:E137V} Exclusion (shaded region) plot for $\epsilon_V$: see caption of Fig. \ref{fig:E137P} for detail.}
\end{figure}

\begin{figure}
\centering
\subfigure[\;exclusion plot (mass in linear scale)]{\includegraphics[scale=1]{E137A_zoom_linear}}
\subfigure[\;relative error of exclusion boundary]{\includegraphics[scale=1]{E137A_relative_error}}
\caption{\label{fig:E137A} Exclusion (shaded region) plot for $\epsilon_A$: see caption of Fig. \ref{fig:E137P} for detail.}
\end{figure}

In Fig.~\ref{fig:E137all}, using Eq. (\ref{eq:d sigma dx 1}), we show regions of coupling and mass excluded by the lack of a signal at E137 for different bosons. In the region where $m_\phi>2m_e$ the exclusion plots are similar with each other, however, in the region where $m_\phi<2m_e$ the exclusion plots are very different because the the decay widths for different bosons are fundamentally different.

In Figs.~\ref{fig:E137P}--\ref{fig:E137A}, using Eq. (\ref{eq:d sigma dx 1},\ref{eq:d sigma dx 2},\ref{eq:d sigma dx 3-2}), we show the exclusion regions using the three different ways to calculate the differential cross section. Because of the exponential factor from decay and absorption lengths, the error in the exclusion plot due to making approximations to the cross section is smaller along the upper boundary, which is mainly determined by whether $\phi$ lives long enough to make it to the detector. With the WW approximation, the 100\% error in cross section causes an error of less than 20\% along the lower boundary, and in a log-log plot across several scales, a 20\% error is almost indistinguishable by eyesight. On the other hand, with the IWW approximation, the difference is clearly visible when $m_\phi\gtrsim 100$ MeV. In the region where $m_\phi>2m_e$, the relative errors of the exclusion plots boundary for different bosons are similar based on the same reason which causes the similar relative errors of the cross section: the approximations deal with the phase space integral and the kinematics for different bosons are similar.

In Fig.~\ref{fig:E137all}, we see that the absorption process, Eq. (\ref{eq:absorption}), cuts off the exclusion plot around $\epsilon\sim\mathcal{O}(1)$ where the coupling of $\phi$ to electrons is of same order of the electromagnetic coupling. Therefore, in this region, there is another significant process to consider for beam dump experiments. This is the trapping process due to the rescattering
\begin{align}
e(p)+\phi(k)\rightarrow e(p')+\phi(k').
\end{align}
The trapping process is expected to be as important as the absorption process in this example (new bosons and beam dump E137), and also cuts off the exclusion plot around $\epsilon\sim\mathcal{O}(1)$. However, in Fig.~\ref{fig:E137all} the region where $\epsilon\sim\mathcal{O}(1)$ has been excluded by other experiments, such as electron $g-2$ \cite{Pospelov:2008zw,Bouchendira:2010es} and hydrogen Lamb shift \cite{Eides:2000xc}, which are discussed in Ref.~\cite{Liu:2016qwd} as well as astrophysical processes \cite{Essig:2013lka}. Therefore we do not include the trapping process, but it might be crucial for other experiments.

\section{discussion}\label{sec:discussion}
In the region where $m_\phi>2m_e$, while the production amplitude, decay length, and the absorption length can differ in detail for particles with different quantum numbers, they are qualitatively similar. The approximations that we have examined deal with the phase space integral and coupling to electromagnetism of the target nucleus. Therefore, as we expected, the exclusion plots for different bosons are similar. On the other hand, where $m_\phi<2m_e$, the decay channels, which are very different for different bosons, result in very different exclusion regions. New results for vector decaying to 3 photons, Eq. (\ref{eq:V decay to photons}), and axial-vector decaying to 4 photons, Eq. (\ref{eq:A decay to photons}), are presented.

Including a coupling to the muon may change the situation for $m_\phi>2m_\mu$~\cite{Liu:2016qwd} due to the opening of a new channel with typically a substantial partial width. A study of the production of vector particles in electron beam dumps that deals with some of the issues we have addressed can be found in Ref.~\cite{Beranek:2013yqa}.

There are some other beam dump experiments using a Cherenkov detector, such as E141 \cite{Riordan:1987aw} and Orsay \cite{Davier:1989wz}. Therefore, their exclusion plots do not extend to the region where $m_\phi<2m_e$. We show the results of the beam dump experiments E141 and Orsay for the scalar boson in Ref.~\cite{Liu:2016qwd}.

We need to consider the LPM effect \cite{Landau:1953um,Landau:1953gr,Migdal:1956tc,Anthony:1995fs} which suppresses particle production cross section below a certain (produced particle) energy. For E137, this energy is about 12 MeV which is much smaller than the energy cutoff of the detector. Therefore we do not consider the LPM effect in our discussion. However, for other experiments (depending on the apparatus), the LPM effect may need to be taken into account.

In this work, we present a complete analysis of beam dump experiments. We show that a brute-force analytical calculation is possible. Software exists using Monte-Carlo simulations, such as \textsc{MadGraph/MadEvent}~\cite{Alwall:2007st} as used in, e.g.,~\cite{Essig:2010xa}, that can calculate the cross section without using approximations. Our work can be used as a consistency check for Monte-Carlo simulations. We show that using the WW approximation can be trusted to an order of magnitude in cross sections and exclusion plots. Additionally our work  allows us to understand the errors introduced by the various common approximations. In certain regions of parameter space different errors partially cancel against each other, leading to results that are accidentally sometimes more accurate than one might be expected. However, in our previous work, we illustrated with several pseudoexperiments that in the event of a nonzero signal, a complete calculation is necessary. This work could be useful given the possibility of future beam dump experiments or beam dump like experiments~\cite{future}.

\section*{acknowledgement}
We acknowledge M. McKeen and A. E. Nelson for invaluable discussions and suggestions. The work of G. A. M. and Y.-S. L. was supported by the U. S. Department of Energy Office of Science, Office of Nuclear Physics under Award Number DE-FG02-97ER-41014.