\documentclass{beamer}
\usepackage{calc}
\usepackage{adjustbox}
\newcommand{\negphantom}[1]{\settowidth{\dimen0}{#1}\hspace*‌​{-\dimen0}}
\usepackage{tikz}

\begin{document}
\begin{frame}
  \frametitle{Coalescing crossover}
  \begin{overprint}
  We perform this on two randomly-selected permutations $P, Q$ in the
  population:

  % I need these two to not 'bounce' and stay in the same place
  % The idea being that, as the slides transition, the second replaces the first
  % What should I use instead of 'only' here?
  \setlength{\dimen0}{1pt}
  \uncover<2->{\[
    \begin{array}{cccccc}
      P & = & \begin{tikzpicture}[anchor=base, baseline]
        \node<2> at (0,0) {{\uncover<2>{a}}};
        \uncover<3>{\node at (0,0) {\boxed{a}};}
      \end{tikzpicture} & b & c & d\\
      Q & = & d & a & c & b\\
      R & = &   &   &   &  \\
    \end{array}
  \]}
  \end{overprint}
\end{frame}

\end{document}