# The Longest Subsequence-Repeated Subsequence Problem

Manuel Lafond111Department of Computer Science, Université de Sherbrooke,
Sherbrooke, Quebec J1K 2R1, Canada. Email<EMAIL_ADDRESS>Wenfeng Lai 222College of Computer Science and Technology, Shandong
University, Qingdao, China. Email<EMAIL_ADDRESS>Adiesha Liyanage
333Gianforte School of Computing, Montana State University, Bozeman, MT 59717,
USA. Email<EMAIL_ADDRESS>Binhai Zhu 444Gianforte School of Computing,
Montana State University, Bozeman, MT 59717, USA. Email<EMAIL_ADDRESS>
###### Abstract

Motivated by computing duplication patterns in sequences, a new fundamental
problem called the longest subsequence-repeated subsequence (LSRS) is
proposed. Given a sequence $S$ of length $n$, a letter-repeated subsequence is
a subsequence of $S$ in the form of $x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots
x_{k}^{d_{k}}$ with $x_{i}$ a subsequence of $S$, $x_{j}\neq x_{j+1}$ and
$d_{i}\geq 2$ for all $i$ in $[k]$ and $j$ in $[k-1]$. We first present an
$O(n^{6})$ time algorithm to compute the longest cubic subsequences of all the
$O(n^{2})$ substrings of $S$, improving the trivial $O(n^{7})$ bound. Then, an
$O(n^{6})$ time algorithm for computing the longest subsequence-repeated
subsequence (LSRS) of $S$ is obtained. Finally we focus on two variants of
this problem. We first consider the constrained version when $\Sigma$ is
unbounded, each letter appears in $S$ at most $d$ times and all the letters in
$\Sigma$ must appear in the solution. We show that the problem is NP-hard for
$d=4$, via a reduction from a special version of SAT (which is obtained from
3-COLORING). We then show that when each letter appears in $S$ at most $d=3$
times, then the problem is solvable in $O(n^{4})$ time.

##  1 Introduction

Finding patterns in long sequences is a fundamental problem in string
algorithms, combinatorial pattern matching and computational biology. In this
paper we are interested in long patterns occurring at a global level, which
has also been considered previously. One prominent example is to compute the
longest square subsequence of a string $S$ of length $n$, which was solved by
Kosowski in $O(n^{2})$ time in 2004 [6]. The bound is conditionally optimal as
any $o(n^{2-\varepsilon})$ solution would lead to a subquadratic bound for the
traditional Longest Common Subsequence (LCS) problem, which is not possible
unless the SETH conjecture fails [2]. Nonetheless, a slight improvement was
presented by Tiskin [18]; and Inoue et al. recently tried to solve the problem
by introducing the parameter $M$ (which is the number of matched pairs in $S$)
and $r$ (which is the length of the solution) [5].

In biology, it was found by Szostak and Wu as early as in 1980 that gene
duplication is the driving force of evolution [17]. There are two kinds of
duplications: arbitrary segmental duplications (i.e., an arbitrary segment is
selected and pasted at somewhere else) and tandem duplications (i.e., in the
form of $X\rightarrow XX$, where $X$ is any segment of the input sequence). It
is known that the former duplications occur frequently in cancer genomes [4,
13, 16]. On the other hand, the latter are common under different scenarios;
for example, it is known that the tandem duplication of 3 nucleotides CAG is
closely related to the Huntington disease [12]. In addition, tandem
duplications can occur at the genome level (acrossing different genes) for
certain types of cancer [14].

As duplication is common in biology, it was not a surprise that in the first
sequenced human genome around 3% of the genetic contents are in the form of
tandem repeats [10]. In 2004, Leupold et al. posed a fundamental question
regarding tandem duplications: what is the complexity to compute the minimum
tandem duplication distance between two sequences $A$ and $B$ (i.e., the
minimum number of tandem duplications to convert $A$ to $B$). In 2020, Lafond
et al. answered this open question by proving that this problem is NP-hard for
an unbounded alphabet [7]. Later in [8], Lafond et al. proved that the problem
is NP-hard even if $|\Sigma|\geq 4$ by encoding each letter in the unbounded
alphabet proof with a square-free string over a new alphabet of size 4
(modified from Leech’s construction [11]), which covers the case most relevant
with biology, i.e., when $\Sigma=\\{{\tt A},{\tt C},{\tt G},{\tt T}\\}$ or
$\Sigma=\\{{\tt A},{\tt C},{\tt G},{\tt U}\\}$ [8]. Independently, Cicalese
and Pilati showed that the problem is NP-hard for $|\Sigma|=5$ using a
different encoding method [3].

Besides duplication, another driving force in evolution is certainly mutation.
As a simple example, suppose we have a toy singleton genome ${\tt ACGT}$ (note
that a real genome certainly would have a much larger alphabet) and it evolves
through two tandem duplications ${\tt ACGT}\cdot{\tt ACGT}\cdot{\tt ACGT}$
then another one on the second ${\tt GTA}$ to have $H={\tt ACGT}\cdot{\tt
AC}\cdot{\tt GTA}\cdot{\tt GTA}\cdot{\tt CGT}$. If in $H$ some mutation
occurs, e.g., the first $G$ is deleted and the second $G$ is changed to $T$ to
have $H^{\prime}={\tt ACT}\cdot{\tt AC}\cdot{\tt TTA}\cdot{\tt GTA}\cdot{\tt
CGT}$, then it is difficult to retrieve the tandem duplications from
$H^{\prime}$. Motivated by the above applications, Lai et al. [9] recently
proposed the following problem called the Longest Letter-Duplicated
Subsequence: Given a sequence $S$ of length $n$, compute a longest letter-
duplicated subsequence (LLDS) of $S$, i.e., a subsequence of $S$ in the form
$x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots x_{k}^{d_{k}}$ with $x_{i}\in\Sigma$, where
$x_{j}\neq x_{j+1}$ and $d_{i}\geq 2$ for all $i$ in $[k]$, $j$ in $[k-1]$ and
$\sum_{i\in[k]}d_{i}$ is maximized. A simple linear time algorithm can be
obtained to solve LLDS. But some constrained variation, i.e., all letters in
$\Sigma$ must appear in the solution, is shown to be NP-hard.

In this paper, we extend the work by Lai et al. by looking at a more general
version of LLDS, namely, the Longest Subsequence-repeated Subsequence (LSRS)
problem of $S$, which follows very much the same definition as above except
that each $x_{i}$ is a subsequence of $S$ (instead of a letter). As a
comparison, for the sequence $H^{\prime}$, one of the optimal LLDS solutions
is ${\tt AATTTT}={\tt A}^{2}{\tt T}^{4}$ while the LSRS solution is ${\tt
ACAC}\cdot{\tt TAGTAG}=({\tt AC})^{2}({\tt TAG})^{2}$ which clearly gives more
information about the duplication histories. This motivates us studying LSRS
and related problems in this paper. Let $d$ be the maximum occurrence of any
letter in the input string $S$, with $|S|=n$. Let _LSDS+_ $(d)$ be the
constrained version that all letters in $\Sigma$ must appear in the solution,
and the maximum occurrence of any letter in $S$ is at most $d$. We summarize
the results of this paper as follows.

  1. 1.

We show that the longest cubic subsequences of all substrings of $S$ can be
solved in $O(n^{6})$ time, improving the trivial $O(n^{7})$ bound.

  2. 2.

We show that LSRS can be solved in $O(n^{6})$ time.

  3. 3.

When $d\geq 4$, _LSRS+_ $(d)$ is NP-complete.

  4. 4.

When $d=3$, _LSRS+_ $(3)$ can be solved in $O(n^{4})$ time.

Note that the parameter $d$, i.e., the maximum duplication number, is
practically meaningful in bioinformatics, since whole genome duplication is a
rare event in many genomes and the number of duplicates is usually small. For
example, it is known that plants have undergone up to three rounds of whole
genome duplications, resulting in a number of duplicates bounded by 8 [19].

It should also be noted that our LSRS and LSRS+ problems seem to be related to
the recently studied problems Longest Run Subsequence (LRS) [15], which is NP-
hard; and Longest (Sub-)Periodic Subsequence [1], which is polynomially
solvable. But these two problems are different from our LSRS and LSRS+
problems. For instance, in an LRS solution a letter can appear in at most one
run while in our LSRS and LSRS+ solutions, say ${\tt ACAC}\cdot{\tt TAGTAG}$
for the input string $H^{\prime}$, a substring (e.g., AC) can appear many
times, hence a letter (e.g., A) could appear many times but non-consecutively
in LSRS and LSRS+ solutions. On the other hand, in the Longest (Sub-)Periodic
Subsequence problem one is very much only looking for the repetition of a
single subsequence of the input string, while obviously in our LSRS and LSRS+
problems we need to find the repetitions of multiple subsequences of the input
string (e.g., AC and TAG).

This paper is organized as follows. In Section 2 we give necessary
definitions. In Section 3 we give an $O(n^{6})$ time algorithm for computing
the longest cubic subsequences of all substrings of $S$, as well as the
solution for LSRS. In Section 4 we prove that $\emph{LSRS+}(4)$ is NP-hard and
then we show that $\emph{LSRS+}(3$) can be solved in polynomial time. We
conclude the paper in Section 5.

##  2 Preliminaries

Let $\mathbb{N}$ be the set of natural numbers. For $q\in\mathbb{N}$, we use
$[q]$ to represent the set $\\{1,2,...,q\\}$ and we define
$[i,j]=\\{i,i+1,\ldots,j\\}$. Throughout this paper, a sequence $S$ is over a
finite alphabet $\Sigma$. We use $S[i]$ to denote the $i$-th letter in $S$ and
$S[i..j]$ to denote the substring of $S$ starting and ending with indices $i$
and $j$ respectively. (Sometimes we also use $(S[i],S[j])$ as an interval
representing the substring $S[i..j]$.) With the standard run-length
representation, $S$ can be represented as $y_{1}^{a_{1}}y_{2}^{a_{2}}\cdots
y_{q}^{a_{q}}$, with $y_{i}\in\Sigma,y_{j}\neq y_{j+1}$ and $a_{j}\geq 1$, for
$i\in[q],j\in[q-1]$. Finally, a subsequence of $S$ is a string obtained by
deleting some letters in $S$. Specifically, a square subsequence of $S$ is a
subsequence of $S$ in the form of $X^{2}$, where $X$ is also a subsequence of
$S$; and a cubic subsequence of $S$ is a subsequence of $S$ in the form of
$X^{3}$, where $X$ is a also subsequence of $S$. One is certainly interested
in the longest ones in both cases.

A subsequence $S^{\prime}$ of $S$ is a subsequence-repeated subsequence (SRS)
of $S$ if it is in the form of $x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots
x_{k}^{d_{k}}$, with $x_{i}$ being a subsequence of $S$, $x_{j}\neq x_{j+1}$
and $d_{i}\geq 2$, for $i\in[k],j\in[k-1]$. We call each $x_{i}^{d_{i}}$ in
$S^{\prime}$ a subsequence-repeated block (SR-block, for short). For instance,
let $S={\tt ACGAGCGCAGCGA}$, then $S_{1}={\tt AGAG}\cdot{\tt CGCGCG}$,
$S_{2}={\tt ACGACG}\cdot{\tt CGCG}$ and $S_{3}={\tt ACGACG}\cdot{\tt CACA}$
are multiple solutions for the longest subsequence-duplicated subsequence of
$S$, where any maximal substring in $S_{i}$ separated by $\cdot$ forms a SR-
block. As a separate note, given this $S$, the longest square subsequence is
${\tt CAGCG\cdot CAGCG}=({\tt CAGCG})^{2}$ and the longest cubic subsequence
is ${\tt CGACGACGA}=({\tt CGA})^{3}$.

##  3 A Polynomial-time Solution for LSRS

In this section we proceed to solve the LSRS problem. Firstly, as a
subroutine, we need to compute the longest cubic subsequences of all
$O(n^{2})$ substrings of $S$ in $O(n^{6})$ time. Assuming that is the case, we
have a way to solve LSRS as follows.

###  3.1 Solution for the LSRS Problem

With Kosowski’s quadratic solution for the longest square subsequence (even
though we could achieve our goal without using it, see Section 3.2) and our
$O(n^{6})$ time solution for the longest cubic subsequence (details to be
given in Section 3.2), we solve the LSRS problem by dynamic programming. We
first have the following observation.

###### Observation 3.1

Suppose that there is an optimal LSRS solution for a given sequence $S$ of
length $n$, in the form of $x_{1}^{d_{1}}x_{2}^{d_{2}}\ldots x_{k}^{d_{k}}$.
Then it is possible to decompose it into a generalized SR-subsequence in the
form of $y_{1}^{e_{1}}y_{2}^{e_{2}}\ldots y_{p}^{e_{p}}$, where

  * •

$2\leq e_{i}\leq 3$, for $i\in[p]$,

  * •

$p\geq k$,

  * •

$y_{j}$ does not have to be different from $y_{j+1}$, for $j\in[p-1]$.

The proof is straightforward: For any natural number $\ell\geq 2$, we can
decompose it as $\ell=\ell_{1}+\ell_{2}+\ldots+\ell_{z}\geq 2$, such that
$2\leq\ell_{j}\leq 3$ for $1\leq j\leq z$. Consequently, for every $d_{i}>3$,
we could decompose it into a sum of 2’s and 3’s. Then, clearly, given a
generalized SR-subsequence, we could easily obtain the corresponding SR-
subsequence by combining $y_{i}^{e_{i}}y_{i+1}^{e_{i+1}}$ when
$y_{i}=y_{i+1}$.

We now design a dynamic programming algorithm for LSRS. Let $L(i)$ be the
length of the optimal LSRS solution for $S[1..i]$. Let $Q2[i,j]$ and $Q3[i,j]$
store the longest square and cubic subsequences of $S[i..j]$ respectively. The
recurrence for $L(i)$ is as follows.

$\displaystyle L(0)$ $\displaystyle=0,$ $\displaystyle L(1)$
$\displaystyle=0,$ $\displaystyle L(i)$
$\displaystyle=\max\begin{cases}L(j)+Q2[j+1,i],&j<i-1\\\
L(j)+Q3[j+1,i],&j<i-2\end{cases}$

Computing all the cells $Q2[j,k]$ takes $O(n^{4})$ time as there are
$O(n^{2})$ cells and each can be computed using Kosowski’s algorithm in
quadratic time. (As we will show right after Theorem 1, the $O(n^{4})$ time
bound can also be obtained without using Kosowski’s algorithm.) Computing all
$Q3[j,k]$ takes $O(n^{7})$ time: there are $O(n^{2})$ cells, each can be
computed in $O(n^{5})$ time using the only known brute-force solution.
However, in the next subsection we show that the longest cubic subsequences of
all substrings of $S$, i.e., all $Q3[j,k]$ can be computed in $O(n^{6})$ time.
Therefore, after $Q2[-,-]$ and $Q3[-,-]$ are all computed, it takes $O(n^{2})$
time to update and fill the whole table $L(-)$. The value of the optimal LSRS
solution for $S$ can be found in $L(n)$. Consequently, we have a running time
of $O(n^{6})$. To make the solution complete, we next show the algorithm for
computing the longest cubic subsequences of all substrings of $S$.

###  3.2 An $O(n^{6})$ Time Bound for the Longest Cubic Subsequences of All
Substrings of the Input String

First of all, notice that an $O(n^{5})$ time brute-force solution for the
longest cubic subsequence problem is trivial: just enumerate in $O(n^{2})$
time all the cuts cutting $S$ into three substrings, and then compute the
longest common subsequence over this triple of substrings in $O(n^{3})$ time.
The longest of all would give us the solution. Then, to compute all $Q3[j,k]$
it takes $O(n^{7})$ time since there are $O(n^{2})$ cells. To improve this
bound, a different idea is needed.

The idea is that when one computes the longest common subsequence of three
sequences $A,B$ and $C$, one would use dynamic programming to compute, for
each triple of $i,j,k$, the longest common subsequence of $A[1..i],B[1..j]$
and $C[1..k]$. When $i,j$ are fixed this dynamic programming algorithm can in
fact compute the longest common subsequences of $A[1..i],B[1..j]$ and all
$C[1..k^{\prime}]$, with $1\leq k^{\prime}\leq k$. Therefore, by enumerating
$i$ and $j$, in $O(n^{2}\cdot n^{3})=O(n^{5})$ time, we can compute all
longest cubic subsequences of a prefix $A\cdot B\cdot C$ of $S$. To compute
the longest cubic subsequences of all substrings of $S$, it suffices to run
the above algorithm on every suffix of $S$. Hence, in $O(n)\cdot
O(n^{5})=O(n^{6})$ time we can compute the longest cubic subsequences of all
substrings of $S$.

###### Theorem 3.1

The longest cubic subsequences of all substrings of an input string of length
$n$ can be computed in $O(n^{6})$ time and $O(n^{3})$ space.

Note that we can use this idea to compute the longest square subsequences for
all substrings of the input string $S$ in $O(n^{4})$ time, without using
Kosowski’s algorithm at all. In this case, using the standard dynamic
programming for computing the longest common subsequence of $A$ and $B$, we
compute all longest square subsequences of a prefix $A\cdot B$ of the input
sequence $S$ in $O(n^{3})$ time. Then we run this algorithm on all suffix of
$S$, giving a total running time of $O(n^{4})$. In this process, there is no
need to use Kosowski’s algorithm.

Finally, together with the algorithm in Section 3.1, we have the following
theorem.

###### Theorem 3.2

The longest subsequence-repeated subsequence problem can be solved in
$O(n^{6})$ time.

##  4 The Variants of LSRS

In this section, we focus on the following variations of the LSRS problem.

###### Definition 4.1

_Constrained Longest Subsequence-Repeated Subsequence_
($\emph{LSRS}+$ for short)

Input: A sequence $S$ with length $n$ over an alphabet $\Sigma$ and an integer
$\ell$.

Question: Does $S$ contain a subsequence-repeated subsequence $S^{\prime}$
with length at least $\ell$ such that all letters in $\Sigma$ appear in
$S^{\prime}$?

###### Definition 4.2

_Feasibility Testing_ (FT for short)

Input: A sequence $S$ with length $n$ over an alphabet $\Sigma$.

Question: Does $S$ contain a subsequence-repeated subsequence
$S^{\prime\prime}$ such that all letters in $\Sigma$ appear in
$S^{\prime\prime}$?

For LSRS+ we are really interested in the optimization version, i.e., to
maximize $\ell$. Note that, though looking similar, FT and the decision
version of LSRS+ are different: if there is no feasible solution for FT,
certainly there is no solution for LSRS+; but even if there is a feasible
solution for FT, computing an optimal solution for LSRS+ could still be non-
trivial.

Finally, let $d$ be the maximum number of times a letter in $\Sigma$ appears
in $S$. Then, we can represent the corresponding versions for LSRS+ and FT as
_LSRS+_ $(d)$ and $FT(d)$ respectively.

It turns out that (the decision version of) _LSRS+_ $(d)$ and $FT(d)$ are both
NP-complete when $d\geq 4$, while when $d=3$ both _LSRS+_ $(3)$ and $FT(3)$
can be solved in $O(n^{4})$ time. We present the details below.

###  4.1 LSRS+(4) is NP-hard

We first show that $(3^{+},1,2^{-})$-SAT is NP-complete; in this version of
SAT all variables appear positively in 3-CNF clauses (i.e., clauses containing
exactly 3 positive literals) and each variable appears exactly once in total
in these 3-CNF clauses; moreover, the negation of the variables appear in
2-CNF clauses (i.e., clauses containing 2 negative literals), possibly many
times. A valid truth assignment for an $(3^{+},1,2^{-})$-SAT instance $\phi$
is one which makes $\phi$ true; moreover, each 3-CNF clause has exactly one
true literal.

A folklore reduction was discussed in the internet at some point; here we give
a formal sketch of the proof.

###### Theorem 4.1

$(3^{+},1,2^{-})$-SAT is NP-complete.

_Proof._ As the problem is easily seen to be in NP, let us focus more on the
reduction from 3-COLORING. In 3-COLORING, given a graph $G=(V,E)$, one needs
to assign one of the 3 colors to each of the vertex $u\in V$ such that for any
edge $(u,v)\in E$, $u$ and $v$ are given different colors.

For each vertex $u$, we use $u_{1},u_{2}$ and $u_{3}$ to denote the 3 colors,
then, obviously, we have the 3-CNF clause $(u_{1}\vee u_{2}\vee u_{3})$.
Therefore, the positive 3-CNF formulae are

$C^{+}=\bigwedge_{u\in V}(u_{1}\vee u_{2}\vee u_{3}).$

We have 2 kinds of 2-CNF clauses. First, for each $u\in V$, we have a type-1
2-CNF clause which demands that one cannot select two colors $i$ and $j$ for
$u$ at the same time:

$\overline{u_{i}\wedge u_{j}}=(\bar{u}_{i}\vee\bar{u}_{j}),$

for $1\leq i\neq j\leq 3$. Then, for each edge $(u,v)\in E$, we have a type-2
2-CNF clause which demands that $u$ and $v$ cannot have the same color $i$:

$\overline{u_{i}\wedge v_{i}}=(\bar{u}_{i}\vee\bar{v}_{i}),$

for $i=1,2,3$.

Let $C^{-}$ be the conjunction of these 2-CNF clauses. Then $\phi=C^{+}\wedge
C^{-}$, and it is clear that $G$ has a 3-coloring if and only if $\phi$ has a
valid truth assignment. The reduction obviously takes linear time. Hence the
theorem is proven. $\sqcap$$\sqcup$

Figure 1: An illustration of the proof of Theorem 4.1. In this case,
$C^{+}=(u_{1}\vee u_{2}\vee u_{3})\wedge(v_{1}\vee v_{2}\vee
v_{3})\wedge(w_{1}\vee w_{2}\vee w_{3})\wedge(y_{1}\vee y_{2}\vee y_{3})$.

In Fig. 1, we show an example for the proof of Theorem 4.1. The example will
be used in the following paragraphs.

We next reduce $(3^{+},1,2^{-})$-SAT to FT(4). Let the input $\phi$ for
$(3^{+},1,2^{-})$-SAT be constructed directly from a 3-COLORING instance;
moreover, let $\phi$ have $3n$ variables $x_{1},x_{2},\cdots$, $x_{3n}$ and
$m$ 2-CNF clauses. We label its 3-CNF clauses as
$F^{+}_{1},F^{+}_{2},\cdots,F^{+}_{n}$ and its 2-CNF clauses as
$F^{-}_{1},F^{-}_{2},\cdots,F^{-}_{m}$. (For the example in Fig. 1, we can
take as $u_{1},u_{2},u_{3},\cdots,y_{1},y_{2},y_{3}$ alphabetically as
$x_{1},x_{2},\cdots,x_{12}$.)

In the example in Fig. 1, the type-1 2-CNF clauses on $u$ are

$(\bar{u}_{1}\vee\bar{u}_{2})\wedge(\bar{u}_{1}\vee\bar{u}_{3})\wedge(\bar{u}_{2}\vee\bar{u}_{3})=F^{-}_{1}\wedge
F^{-}_{2}\wedge F^{-}_{3},$

the type-2 2-CNF clauses on edge $(u,v)$ are

$(\bar{u}_{1}\vee\bar{v}_{1})\wedge(\bar{u}_{2}\vee\bar{v}_{2})\wedge(\bar{u}_{3}\vee\bar{v}_{3})=F^{-}_{4}\wedge
F^{-}_{5}\wedge F^{-}_{6},$

and the type-2 clauses on edge $(u,w)$ are

$(\bar{u}_{1}\vee\bar{w}_{1})\wedge(\bar{u}_{2}\vee\bar{w}_{2})\wedge(\bar{u}_{3}\vee\bar{w}_{3})=F^{-}_{7}\wedge
F^{-}_{8}\wedge F^{-}_{9}.$

For each variable $x_{i}$, let $L(x_{i})$ be the list of type-1 2-CNF clauses
containing $\bar{x}_{i}$ followed with the list of type-2 2-CNF clauses
containing $\bar{x}_{i}$, each repeating twice consecutively. (For the example
in Fig. 1, $L(x_{1})=L(u_{1})=F^{-}_{1}F^{-}_{1}F^{-}_{2}F^{-}_{2}\cdot
F^{-}_{4}F^{-}_{4}F^{-}_{7}F^{-}_{7}$.) For each $F^{+}_{i}$ we also define
three unique letters $1_{i},2_{i}$ and $3_{i}$. Hence, the alphabet we use to
construct the final sequence $H$ is

$\Sigma=\\{F^{-}_{j}|j\in[m]\\}\cup\\{1_{i},2_{i},3_{i}|i\in[n]\\}\cup\\{g_{k},g^{\prime}_{k}|k\in[n-1]\\},$

where $g_{k}$ and $g^{\prime}_{k}$ are used as separators.

Let $F^{+}_{i}=(x_{i,1}\vee x_{i,2}\vee x_{i,3})$. We construct

$H_{i}=2_{i}\cdot L(x_{i,1})\cdot 1_{i}2_{i}1_{i}\cdot L(x_{i,2})\cdot
2_{i}\cdot L(x_{i,3})\cdot 3_{i}2_{i}3_{i},$

where $2_{i}$ and all the 2-CNF clauses each appear 4 times in $H_{i}$, while
$1_{i}$ and $3_{i}$ each appears twice. Finally we construct a sequence $H$ as

$H=H_{1}\cdot g_{1}g^{\prime}_{1}g_{1}g^{\prime}_{1}\cdot H_{2}\cdot
g_{2}g^{\prime}_{2}g_{2}g^{\prime}_{2}\cdot H_{3}\cdots\cdot
g_{n-1}g^{\prime}_{n-1}g_{n-1}g^{\prime}_{n-1}\cdot H_{n},$

where $g_{j}$ and $g^{\prime}_{j}$ each appears twice. We claim that $\phi$
has a valid truth assignment if and only if $H$ induces a feasible SRS which
contains all $1_{i},2_{i},3_{i}$ ($i=1..n$), all $F^{-}_{j}$ ($j=1..m$) and
all $g_{k}g^{\prime}_{k}g_{k}g^{\prime}_{k}$ ($k=1..n-1$).

The forward direction, i.e., when $\phi$ has a valid truth assignment, is
straightforward. In this case, suppose exactly one of $x_{i,1}$, $x_{i,2}$ and
$x_{i,3}$ (say $x_{i,j}$, $1\leq j\leq 3$) is assigned TRUE, then we delete
$L(x_{i,j})$ for $j=1,2$ or $3$ in $H_{i}$. Finally we delete some
$1_{i},2_{i}$ and $3_{i}$ to obtain a feasible solution $H^{\prime}_{i}$ as
follows.

  1. 1.

If $j=1$, we have $H^{\prime}_{i}=2_{i}1_{i}2_{i}1_{i}\cdot L(x_{i,2})\cdot
L(x_{i,3})\cdot 3_{i}3_{i}$.

  2. 2.

If $j=2$, we have $H^{\prime}_{i}=L(x_{i,1})\cdot 1_{i}2_{i}1_{i}2_{i}\cdot
L(x_{i,3})\cdot 3_{i}3_{i}$.

  3. 3.

If $j=3$, we have $H^{\prime}_{i}=L(x_{i,1})\cdot 1_{i}1_{i}\cdot
L(x_{i,2})\cdot 2_{i}3_{i}2_{i}3_{i}$.

It is noted that exactly one $L(x_{i,j})$ is deleted in all three cases. (We
focus on $j=1$ next.) Hence, the deleted letters (2CNF clauses in the form of
$F^{-}_{k}$) in $L(x_{i,1})$ would still appear in the claimed feasible
solution, even after the deletion of $L(x_{i,1})$. For example, if $F^{-}_{k}$
is type-1 which contains $\bar{x}_{i,1}$ and $\bar{x}_{i,2}$, then
$F^{-}_{k}F^{-}_{k}$ must appear in $L(x_{i,2})$, which is not deleted.
Similarly, if $F^{-}_{k}$ is type-2 which contains $\bar{x}_{i,1}$ and
$\bar{x}_{\ell,1}$, where $(x_{i},x_{\ell})$ is an edge in the graph $G$, then
$F^{-}_{k}F^{-}_{k}$ appears in $L(x_{\ell,1})$ which must be kept — if
$L(x_{\ell,1})$ were also deleted, it would imply that both $x_{i}$ and
$x_{\ell}$ are colored with color-1. Therefore, all the 2CNF clauses appear in
the claimed feasible solution.

The reverse direction is slightly more tricky. We first show the following
lemma.

###### Lemma 4.1

If $H$ admits a feasible (SRS) solution, then exactly two (non-empty
subsequences) of $L(x_{i,1}),L(x_{i,2})$ and $L(x_{i,3})$ appear in the
feasible solution $H^{\prime}$ (or, exactly one of the three is completely
deleted from $H$).

_Proof._ Due to the type-1 2-CNF clauses constructed on $x_{i,1}$, $x_{i,2}$
and $x_{i,3}$, if exactly one (non-empty subsequence) of the three lists
$L(x_{i,1})$, $L(x_{i,2})$ and $L(x_{i,3})$, say $L(x_{i,1})$, appears in a
feasible SRS solution $H^{\prime}$, then the type-1 2-CNF clause involving
$x_{i,2}$ and $x_{i,3}$ would be missing in $H^{\prime}$, contradicting the
definition of a feasible solution.

On the other hand, due to the construction of $H_{i}$, we claim that one
cannot leave all three (non-empty subsequences) of the lists $L(x_{i,1})$,
$L(x_{i,2})$ and $L(x_{i,3})$ in a feasible SRS solution $H^{\prime}$ (we only
need to look at the part obtained from $H_{i}$, e.g., $H^{\prime}_{i}$).
Suppose it is not the case, we consider six cases: (1) if $1_{i}1_{i}$ and
$3_{i}3_{i}$ are substrings of $H^{\prime}_{i}$, (2) if $2_{i}X\cdot 2_{i}X$
is a substring of $H^{\prime}_{i}$ with the first $X$ being a substring in
$L(x_{i,1})$ and the second $X$ being a substring in $L(x_{i,2})$, (3) if
$2_{i}X\cdot 2_{i}X$ is a substring of $H^{\prime}_{i}$ with the first $X$
being a substring in $L(x_{i,2})$ and the second $X$ being a substring in
$L(x_{i,3})$, (4) if $X2_{i}\cdot X2_{i}$ is a substring of $H^{\prime}_{i}$
with the first $X$ being a substring in $L(x_{i,1})$ and the second $X$ being
a substring in $L(x_{i,2})$, (5) if $X2_{i}\cdot X2_{i}$ is a substring of
$H^{\prime}_{i}$ with the first $X$ being a substring in $L(x_{i,2})$ and the
second $X$ being a substring in $L(x_{i,3})$, and (6) $XX$ is a substring of
$H^{\prime}_{i}$ where the first $X$ is a subsequence of $L(x_{i,1})$ or
$L(x_{i,1})\cdot L(x_{i,2})$ or $L(x_{i,1})\cdot L(x_{i,2})\cdot L(x_{i,3})$.
We claim that all these six cases are not possible:

  * •

Case 1: It is impossible as $2_{i}$’s would not appear in a feasible solution.

  * •

Cases 2-4: It is impossible as $1_{i}$’s would not appear in a feasible
solution.

  * •

Case 5: It is impossible as $3_{i}$’s would not appear in a feasible solution.

  * •

Case 6: It is impossible as $1_{i}$’s and $2_{i}$’s would not appear in a
feasible solution.

$\sqcap$$\sqcup$

Let $L^{\prime}(x_{i,j})$ be a non-empty subsequence of $L(x_{i,j})$. With the
above lemma, the reverse direction can be proved as follows.

  1. 1.

If $H^{\prime}_{i}=2_{i}1_{i}2_{i}1_{i}\cdot L^{\prime}(x_{i,2})\cdot
L^{\prime}(x_{i,3})\cdot 3_{i}3_{i}$, then assign $x_{i,1}\leftarrow{TRUE}$,
$x_{i,2}\leftarrow{FALSE}$, $x_{i,3}\leftarrow{FALSE}$.

  2. 2.

If $H^{\prime}_{i}=L^{\prime}(x_{i,1})\cdot 1_{i}2_{i}1_{i}2_{i}\cdot
L^{\prime}(x_{i,3})\cdot 3_{i}3_{i}$, then assign $x_{i,1}\leftarrow{FALSE}$,
$x_{i,2}\leftarrow{TRUE}$, $x_{i,3}\leftarrow{FALSE}$.

  3. 3.

If $H^{\prime}_{i}=L^{\prime}(x_{i,1})\cdot 1_{i}1_{i}\cdot
L^{\prime}(x_{i,2})\cdot 2_{i}3_{i}2_{i}3_{i}$, then assign
$x_{i,1}\leftarrow{FALSE}$, $x_{i,2}\leftarrow{FALSE}$,
$x_{i,3}\leftarrow{TRUE}$.

Clearly, this gives a valid truth assignment for $\phi$ — as all the 2-CNF
clauses $(\bar{x}_{i,j}\vee\bar{x}_{k,\ell})$ must appear in
$L^{\prime}(x_{i,j})$ or $L^{\prime}(x_{k,\ell})$ in $H^{\prime}$, and at
least one of $x_{i,j}$ and $x_{k,\ell}$ is assigned FALSE. We thus have the
following theorem.

###### Theorem 4.2

FT(4) is NP-complete.

Since FT(4) is NP-complete, the optimization problem $\emph{LSRS+}(4)$ is
certainly NP-hard.

###### Corollary 4.1

The optimization version of $\emph{LSRS+}(4)$ is NP-hard.

Note that the above proof implies that the optimization version of
$\emph{LSRS+}(4)$ does not admit any polynomial-time approximation (regardless
of the approximation) as any such approximate solution would form a feasible
solution for FT(4). In fact, using a similar argument as in [9], even finding
a good bi-criteria approximation, i.e., approximating the optimal length as
well as the maximum number of letters covered, for $\emph{LSRS+}(4)$ is not
possible (unless P=NP). On the other hand, we show next that $\emph{LSRS+}(3)$
is polynomially solvable.

###  4.2 LSRS+(3) is Polynomially Solvable

We now try to solve LSRS+(3), where the input is a sequence $S$ of length $n$
where each letter appears at most three times and at least twice. As a matter
of fact, an optimal solution must be in the form of $x_{1}^{d_{1}}\cdots
x_{k}^{d_{k}}$, where $x_{i}$ is a subsequence of $S$ and $d_{i}\in\\{2,3\\}$
for $i\in[k]$. Throughout this subsection we assume that all letters in $S$
appear at least twice and at most three times — if a letter appears only once
in $S$ then there is no solution for the corresponding LSRS+(3) instance.

Our idea is again dynamic programming, based on the above observation that in
an optimal solution each SR-block is either a square or a cube. Define 6
tables, $S_{2}[i,j],C_{2}[i,j],S_{3}[i,j]$, $C_{3}[i,j]$, $L[i,j]$ and
$C[i,j]$, with $1\leq i<j\leq n$. The first 4 are only used to initialize
$L[i,j]$’s.

  * •

$C_{2}[i,j]$ is the set of letters that all appear at least twice in $S[i..j]$
if at least one letter appears exactly twice in $S[i,j]$; otherwise
$C_{2}[i,j]$ is empty.

  * •

$S_{2}[i,j]$ is the length of a longest square subsequence in $S[i,j]$
containing all the letters in $C_{2}[i,j]$. If such a local feasible solution
does not exist, set $S_{2}[i,j]\leftarrow-1$; otherwise, we say that this
local feasible solution is 2-feasible.

  * •

$C_{3}[i,j]$ is the set of letters that all appear three times in $S[i..j]$ if
no letter in $S[i,j]$ appears exactly twice; otherwise $C_{3}[i,j]$ is empty.

  * •

$S_{3}[i,j]$ is the length of a longest cubic subsequence (if exists) in
$S[i,j]$ containing all the letters in $C_{3}[i,j]$; otherwise $S_{3}[i,j]$ is
the length of a longest square subsequence containing all the letters in
$C_{3}[i,j]$. If such a local feasible solution (cube or square) does not
exist, set $S_{3}[i,j]\leftarrow-1$; otherwise, we say that this local
feasible solution is 3-feasible or 2-feasible respectively (depending on
whether the local solution is cubic or square).

  * •

$C[i,j]$ is the set of letters appearing at least twice in $S[i..j]$. The
$C[i,j]$’s can be computed, each with a linear scan, in a total of $O(n^{3})$
time. $C[i,j]$’s are only used to enforce the coverage condition.

  * •

$L[i,j]$ is the length of a feasible solution of $S[i..j]$ which covers all
the letters in $C[i,j]$.

The initial values of $L[i,j]$, for $i<j$, can be set as follows.

$\displaystyle L[i,j]$
$\displaystyle=\begin{cases}S_{3}[i,j]&\text{if~{}}S_{3}[i,j]>0\\\
S_{2}[i,j]&\text{else if~{}}S_{2}[i,j]>0\\\ -1&\text{otherwise.}\end{cases}$

Note that the initialized solution might not be final. For example,
$S[1..9]=ababbcacc$, then $S_{3}[1,9]=S_{2}[1,9]=-1$ and $L[1,9]=-1$, i.e.,
there is no local 3-feasible (cubic) or 2-feasible (square) solution that
covers all the letters in $C[1..9]$. But obviously an optimal solution, i.e.,
$(ab)^{2}c^{3}$, exists. Hence we need to proceed to update $L[i,j]$.

Then we update the general case for $L[i,j]$ recursively as follows. This is
done bottom-up, ordered by the ascending length of $S[i..j]$.

$\displaystyle L[i,j]$
$\displaystyle=\begin{cases}\max\\{\max_{i<k<j}\\{L[i,k]+L[k+1,j]\\},L[i,j]\\}&\text{if~{}}L[i,k]>0,L[k+1,j]>0\text{~{}and~{}}\\\
&C[i,j]==C[i,k]\cup C[k+1,j]\\\ -1&\text{otherwise.}\end{cases}$

Two examples can be used to illustrate the update step. In the first example,
$S[1..9]=abacbabcc$, $L[1,9]$ is initially assigned with $S_{3}[1,9]=6$ (which
corresponds to $(abc)^{2}$). After the update step $L[1,9]=8$ (i.e.,
corresponds to $(ab)^{3}(cc)$). In the second example, $S[1..9]=abacabccb$,
$L[1,9]$ is also initialized with $S_{3}[1,9]=6$ (which corresponds
$(abc)^{2}$). After the update step $L[1,9]=6$ (which corresponds to
$(ab)^{2}(cc)$ or $(abc)^{2}$ — in the actual implementation, there is no need
to perform an explicit update for this example; but such a piece of
information cannot be known before the update step, as shown in the first
example).

Note that the condition $C[i,j]==C[i,k]\cup C[k+1,j],$ is to ensure that
$L[i,j]$ is updated only when all the letters in $C[i,j]$ are covered. Then,
the maximum of $L[i,k]+L[k+1,j]$, if greater than $L[i,j]$, replaces (the
previous) $L[i,j]$.

An optimal solution is computed if $L[1,n]>0$, and its solution value is
stored in $L[1,n]$. Clearly, with an additional table, one can easily retrieve
such an optimal solution, if exists.

Regarding the correctness of our algorithm, we have several simple lemmas.

###### Lemma 4.2

$C_{2}[i,j]\cap C_{3}[i,j]=\emptyset$.

_Proof._ This is obvious, as, by definition, $C_{2}[i,j]$ is non-empty only
when there is a letter appearing exactly twice in $S[i,j]$. On the other hand,
$C_{3}[i,j]$ is non-empty when there is no letter appearing exactly twice in
$S[i,j]$. The two conditions are complementary. $\sqcap$$\sqcup$ Regarding
$S_{3}[i,j]$, the following lemma says that if a 3-feasible solution does not
exist then any of those 2-feasible solutions could be stored.

###### Lemma 4.3

If a 3-feasible solution for $S_{3}[i,j]$ does not exist, then any 2-feasible
solution for $S[i,j]$ can be stored (without changing the optimal solution
value).

_Proof._ By definition, $C_{3}[i,j]$ contains all the letters in $S[i,j]$
which appear exactly three times; moreover, there is no letter $x$ which
appears exactly twice in $S[i,j]$. Hence, if a letter $y$ appears exactly once
in $S[i,j]$ it would never appear as a local feasible solution for
$S_{3}[i,j]$.

Therefore, if a 3-feasible solution does not exist, by definition, we would
consider only a 2-feasible solution for $S[i..j]$ which covers all the letters
in $C_{3}[i,j]$. The length of such a 2-feasible solution is exactly
$2\cdot|C_{3}[i,j]|$. $\sqcap$$\sqcup$

An example for this lemma is $S[1..6]={\tt baabab}$. There is no 3-feasible
solution. On the other hand, either abab or baba would make a valid 2-feasible
solution, to be stored in $S_{3}[1,6]$. On the other hand, aabb could also
make a final solution via the update of $L[i,j]$, made of two 2-feasible
solutions aa and bb, for $S_{2}[1,3]$ and $S_{2}[4,6]$ respectively. But aabb
itself is not considered as a 2-feasible solution in, say, $S[1..6]$.

###### Theorem 4.3

Given a string $S$ of length $n$, where each letter appears at most three
times, the problem of LSRS+(3) can be solved in $O(n^{4})$ time.

_Proof._ Regarding the correctness of the update of $L[i,j]$, it is noted that
when $L[i,j]$ is updated by $L[i,k]+L[k+1,j]$ the condition that
$C[i,j]==C[i,k]\cup C[k+1,j]$ is enforced, i.e., the maximum length of
$L[i,j]$ is achieved on the condition that all letters in $S[i,j]$ appear in
the corresponding solution. Note also that $C[i,k]\cap C[k+1,j]=\emptyset$ as
each letter can appear at most three times in $S[i,j]$, if a letter appears
two or three times in $S[i,k]$ it cannot appear two or three times in
$S[k+1,j]$ again — by the definition of $C_{2}[-,-]$ and $C_{3}[-,-]$.

The cost of the algorithm is dominated by filling and updating $S_{2}[i,j]$
and $S_{3}[i,j]$ as the update of $L[i,j]$’s takes $O(n^{3})$ time.
$S_{3}[-,-]$ has $O(n^{2})$ cells, each can be initially filled in $O(n)$ time
as a longest cubic subsequence containing all the letters in $C_{3}[i,j]$, if
exists, must be unique — all these letters appear exactly three times hence we
just cut the sequence of these letters in three segments, each with length
$|C_{3}[i,j]|$, to have a 3-feasible solution (if it is). Checking whether all
the letters in $C_{3}[i,j]$ are covered by this cubic subsequence
corresponding to $S_{3}[i,j]$ takes linear time. If a 3-feasible solution for
$S_{3}[i,j]$ does not exist, then we need to find a longest square subsequence
of $S[i,j]$ and check if it has a length $2\cdot|C_{3}[i,j]|$. (Remember that
if both of these two tests fail then we need to update $S_{3}[i,j]$ as $-1$.)
Hence the total time for filling and updating all $S_{3}[i,j]$ is $O(n^{4})$ —
there are $O(n^{2})$ cells each can be filled in $O(n^{2})$ time using
Kosowski’s algorithm (or using the method outlined right after Theorem 1
without using Kosowski’s algorithm) in the worst case. Similarly, the filling
of $S_{2}[i,j]$ takes $O(n^{4})$ time as well. $\sqcap$$\sqcup$

Clearly, LSRS+(3) has a solution (i.e., $L[1,n]>0$) if and only if FT(3) has a
feasible solution.

##  5 Concluding Remarks

In this paper, we present an $O(n^{6})$ time algorithm for computing the
longest cubic subsequences of all substrings of an input string $S$ of length
$n$. On top of that, we compute the longest subsequence-repeated subsequence
of $S$ in $O(n^{6})$ time as well. We then consider the constrained longest
subsequence-repeated subsequence (LSRS+) and the corresponding feasibility
testing (FT) problems in this paper, where all letters in the alphabet must
occur in the solutions. We parameterize the problems with $d$, which is the
maximum number of times a letter appears in the input sequence. For
convenience, we summarize the results one more time in Table 1. Obviously, the
most prominent open problem is to decide if it is possible to compute the
longest cubic subsequence in $o(n^{5})$ time. Note that besides the trivial
brute-force method, using our alignment graph a different $O(n^{5})$ time
algorithm can be obtained (see Section 3.2).

Table 1: Summary of results on LSRS+ and FT. $d$ |  _LSRS+_ $(d)$ | $FT(d)$ | Approximability of  _LLDS+_ $(d)$
---|---|---|---
$d\geq 4$ | NP-hard | NP-complete | No Approximation
$d=3$ | P | P | Not Applicable

## Acknowledgments

We thank anonymous reviewers for some insightful comments.

## References

  * [1] Hideo Bannai, Tomohiro I, and Dominik K¨oppl.  Longest (sub-)periodic subsequence.  arXiv:2202.07189, 2022.
  * [2] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79–97. IEEE Computer Society, 2015.
  * [3] Ferdinando Cicalese and Nicolo Pilati.  The tandem duplication distance problem is hard over bounded alphabets.  In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms - 21st International Workshop, IWOCA 2021, Ottawa, Canada, July 5-7, 2021, volume 12757 of Lecture Notes in Computer Science, pages 179–193. Springer, 2021.
  * [4] Giovanni Ciriello, Martin L Miller, Bülent Arman Aksoy, Yasin Senbabaoglu, Nikolaus Schultz, and Chris Sander.  Emerging landscape of oncogenic signatures across human cancers.  Nature Genetics, 45:1127–1133, 2013.
  * [5] Takafumi Inoue, Shunsuke Inenaga, and Hideo Bannai.  Longest square subsequence problem revisited.  In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 147–154. Springer, 2020.
  * [6] Adrian Kosowski.  An efficient algorithm for the longest tandem scattered subsequence problem.  In Alberto Apostolico and Massimo Melucci, editors, String Processing and Information Retrieval, 11th International Conference, SPIRE 2004, Padova, Italy, October 5-8, 2004, Proceedings, volume 3246 of Lecture Notes in Computer Science, pages 93–100. Springer, 2004.
  * [7] Manuel Lafond, Binhai Zhu, and Peng Zou.  The tandem duplication distance is NP-hard.  In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 15:1–15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020\.
  * [8] Manuel Lafond, Binhai Zhu, and Peng Zou.  Computing the tandem duplication distance is NP-hard.  SIAM Journal on Discrete Mathematics, 36(1):64–91, 2022.
  * [9] Wenfeng Lai, Adiesha Liyanage, Binhai Zhu, and Peng Zou.  Beyond the longest letter-duplicated subsequence problem.  In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 7:1–7:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [10] E.S. Lander, et al., and International Human Genome Sequencing Consortium.  Initial sequencing and analysis of the human genome.  Nature, 409(6822):860–921, 2001.
  * [11] John Leech.  A problem on strings of beads.  The Mathematical Gazette, 41(338):277–278, 1957.
  * [12] Marcy Macdonald, et al., and Peter S. Harper.  A novel gene containing a trinucleotide repeat that is expanded and unstable on huntington’s disease.  Cell, 72(6):971–983, 1993.
  * [13] The Cancer Genome Atlas Research Network.  Integrated genomic analyses of ovarian carcinoma.  Nature, 474:609–615, 2011.
  * [14] Layla Oesper, Anna M. Ritz, Sarah J. Aerni, Ryan Drebin, and Benjamin J. Raphael.  Reconstructing cancer genomes from paired-end sequencing data.  BMC Bioinformatics, 13(Suppl 6):S10, 2012.
  * [15] Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau.  Using the longest run subsequence problem within homology-based scaffolding.  Algorithms Mol. Biol., 16(1):11, 2021.
  * [16] Andrew J. Sharp, et al., and Even E. Eichler.  Segmental duplications and copy-number variation in the human genome.  The American J. of Human Genetics, 77(1):78–88, 2005.
  * [17] Jack W. Szostak and Ray Wu.  Unequal crossing over in the ribosomal dna of saccharomyces cerevisiae.  Nature, 284:426–430, 1980.
  * [18] Alexander Tiskin.  Semi-local string comparison: algorithmic techniques and applications.  arXiv:0707.3619, 2013.
  * [19] Chunfang Zheng, P Kerr Wall, James Leebens-Mack, Claude de Pamphilis, Victor A Albert, and David Sankoff.  Gene loss under neighborhood selection following whole genome duplication and the reconstruction of the ancestral populus genome.  Journal of Bioinformatics and Computational Biology, 7(03):499–520, 2009.