text:
\section{Introduction}
\label{sec:intro}

Comparative genomics is nowadays a classical field in computational
biology, and one of its typical problems is to cluster sets of
orthologous genes that have virtually the same function in several
genomes. A very strong paradigm is that groups of genes which remain
``close'' during evolution work together (see for instance \citet{galperin2000s}, \citet{lathe2000gene}, \citet{tamames2001evolution}).
Thus, a widely  used approach
to obtain interesting clusters is to try to cluster genes or other
biological units (for instance unique contigs of protein domains)
according to their common proximity on several genomes.  For this
goal, many different cluster models have been proposed, like common
intervals in \citet{UnoYagura}, conserved intervals in \citet{BergeronBCC04},
$\pi$-patterns in \citet{Parida06}, gene teams in \citet{BealBCR04}, domain
teams in \citet{Pasek2005}, approximate common intervals in \citet{AmirGS07}
and so on, considering different chromosome models (permutations,
signed permutations, sequences, graphs, etc.) or
different distance models (accepting gaps, distance modeled as
weighted graphs, etc.)

Among all those models, the first proposed, and still
one of the most used in practice, is the concept of \emph{common
  interval} on genomes represented by permutations. A set of genes
form a common interval of $K$ genomes if it appears as a segment on
each of the $K$ unsigned permutations that represent the genomes. The orders
inside the segments might be totally different.  The model of
conserved interval is close to the model of common interval but
considers signed permutations.

Recently, nested common intervals (easily extensible to nested
conserved intervals) were introduced in \citet{HD05} based on real data
observation by \citet{The10}. A common interval $I$ of size $|I|$ is nested
if $|I|=1$ or if it contains at least one  nested common interval of size $|I|-1$.
\citet{HD05} pointed that
the nestedness assumption can strengthen the significance of detected
clusters since it reduces the probability of observing them randomly.
An $O(n^2)$ time algorithm to compute all nested common intervals
between two permutations has been presented in \citet{BlinFS10} while
between $K$ permutations a recent $O(Kn+\mbox{\em nocc})$ algorithm is
proposed in \citet{IR}, where \emph{nocc} is the number of solutions.

In this paper, we exhibit two simple algorithms to easily compute
nested common and conserved intervals of $K$ permutations from their
natural tree representations. Also, with the same simplicity, we
propose to deal with a generalization of nested common intervals,
called $b$-nested common intervals, and with its variant for conserved
intervals (which are a signed version of common intervals), called
$b$-nested conserved intervals.  These new classes allow - as $b$
grows - for a less constraint containment between the intervals in the
family. Indeed, a nested interval $I$ must contain a nested interval
of size $|I|-1$ or be a unit interval. A $b$-nested common
(resp. conserved) interval must contain a $b$-nested common
(resp. conserved) interval of size at least $|I|-b$ or be a unit
interval. Nested intervals are indead $1$-nested.
From a biological point of view, this is equivalent to modeling
clusters with a larger variability in gene content and gene order,
thus allowing algorithms to deal with annotation errors. However, the
study and validation of this new interval model is deferred to
further applied studies. In this paper we focus on the algorithmic
aspects.

Given a set $\mathcal{P}$ of $K$ permutations on $n$ elements representing
genomes with no duplicates, our simple algorithms
for finding all $b$-nested common or conserved intervals of $\mathcal{P}$ run in
$O(Kn+\mbox{nocc})$-time and need $O(n)$ additional space, where
\emph{nocc} is the number of solutions. In this way, our algorithm for
common intervals performs as well as the algorithm in \citet{IR} for the case
of $K$ permutations, and proposes an efficient approach for the new classes of
$b$-nested intervals.

Moreover, a slight modification of our approach allows us to count the number
of $b$-nested common or conserved intervals  of $K$ permutations in $O(Kn)$ time.
Efficiently counting the number of $b$-nested common intervals without enumerating
them is very usefull when one needs to compute similarity functions between genomes that
are expressed in terms of number of intervals.  See for instance \citet{FR}.

The paper is organized as follows. In Section \ref{sect:Generalities}
we present the main definitions for common and conserved intervals, and
precisely state the problem to solve. In Section \ref{sect:PQ} we
focus on $b$-nested common intervals, recalling the data structure called a
$PQ$-tree, giving a characterization of $b$-nested common intervals and showing
how $PQ$-trees can be used to find all $b$-nested common intervals.
In Section \ref{sect:conservedtree} we adopt a similar approach for
conserved intervals, with the difference that another tree structure must
be  used in this case. In Section \ref{sect:conclusion} we eventually conclude.

\section{Generalities on common and conserved intervals}\label{sect:Generalities}
A {\em permutation} $P$ on $n$ elements is a complete linear order on the set
of integers $\{1, 2, \ldots, n\}$. We denote $Id_n$ the identity
permutation $(1, 2, \ldots, n)$. An {\em interval} of a permutation
$P = (p_1, p_2, \ldots, p_n)$ is a set of consecutive elements of the
permutation $P$. An interval of a permutation will be denoted
by  giving its first and last positions, such as $[i,j]$. Such
an interval is also said {\it delimited} by $p_i$ (left) and $p_j$ (right).
An interval $[i,j] = \{i, i+1, \ldots, j\}$ of the identity permutation
will be simply denoted by $(i .. j)$.

\begin{definition}[\citet{UnoYagura}]
  \label{def:common-intervals}
  Let $\mathcal{P} = \{P_1, P_2, \ldots, P_K\}$ be a set of $K$ permutations
  on $n$ elements.
  A {\em common interval} of  $\mathcal{P}$
  is a set of integers that
  is an interval in each permutation of  $\mathcal{P}$.
\end{definition}

The set $\{1, 2, \ldots, n\}$ and all singletons (also called unit
intervals) are common intervals of any non-empty set $\mathcal{P}$ of
permutations.  Moreover, one can always assume that one of the permutations,
say $P_1$, is the identity permutation $Id_n$. For this, it is sufficient
to renumber the elements of $P_1$ so as to obtain $Id_n$, and then
to renumber all the other permutations accordingly. Then the common
intervals of $\mathcal{P}$ are of the form $(i..j)$ with $1\leq i\leq j\leq n$.

Define now a {\it signed} permutation as a permutation $P$ whose elements have an associated sign among
 $+$ and $-$, making each element to be respectively {\em positive} or {\em negative}.
Negative elements are denoted $-p_i$ while positive elements are simply denoted $p_i$, or $+p_i$ for emphasizing positivity. A permutation is then a signed permutation containing only  positive elements.

\begin{definition}[\citet{BS06}]
Let $\mathcal{P} =\{P_1, P_2,$ $\ldots,$ $P_K\}$ be
a set of signed permutations over $\{1, 2, \ldots, n\}$, with first element $+1$ and last element $+n$,
for each $k\in\{1, 2, \ldots, K\}$. Assume $P_1=\mbox{\it Id}_n$.
A {\em conserved interval} of $\mathcal{P}$ is either a unit interval or a common interval $(a..c)$ of $\mathcal{P}$
(ignoring the signs) which is delimited, in each $P_k$, either by $a$ (left) and $c$ (right),
or by   $-c$ (left) and $-a$ (right).
\label{def:conserved}
\end{definition}

\begin{remark}
In the subsequent, we assume that $\mathcal{P} =\{P_1, P_2,$ $\ldots,$ $P_K\}$ with $P_1=Id_n$. Moreover,
when we deal with conserved intervals, the permutations are assumed to satisfy the hypothesis in
Definition \ref{def:conserved}.
\end{remark}

Now, we are ready to introduce the new classes of intervals.

\begin{definition}
  \label{def:bnested-intervals}
  Let $\mathcal{P} = \{P_1, P_2, \ldots, P_K\}$ be a set of $K$ permutations
  on $n$ elements and let $b$ be a positive integer.
  A common  (respectively conserved) interval of  $\mathcal{P}$
  is {\em $b$-nested} if either $|I|=1$ or $I$ strictly contains a common (resp. conserved)  interval of size at
  least $|I|-b$.
\end{definition}

We are interested in efficient algorithms for finding and counting all
$b$-nested common  (resp. conserved)
intervals of $\mathcal{P} = \{P_1, P_2, \ldots, P_K\}$, without redundancy.
Obviously,
unit intervals are, by definition, $b$-nested common (resp. conserved) intervals.
As a consequence, from now on and without any subsequent specification, we
focus on finding $b$-nested common (resp. conserved)  intervals of size at
least 2.
The following notions will be very useful in the subsequent.

\begin{definition}
 Let $\mathcal{P} = \{P_1, P_2, \ldots, P_K\}$ be a set of $K$ permutations
  on $n$ elements and let $b$ be a positive integer.
  A common  (resp. conserved) interval of  $\mathcal{P}$
  is {\em $b$-small} if its size does not exceed $b$. Otherwise, the interval is {\em $b$-large}.
\end{definition}

Notice that all $b$-small intervals are $b$-nested, by definition and since unit intervals are $b$-nested.

\section{On  $b$-nested common intervals}\label{sect:PQ}

This section is divided into three parts. The first one recalls a tree structure that we associate
to common intervals of permutations, the $PQ$-trees. The second one discusses the properties of
$b$-nested common intervals. Finally, we give the algorithms for efficiently computing and counting
the $b$-nested common intervals.

\subsection{$PQ$-trees and common intervals}

\begin{definition} Let $\mathcal{F}$ be a family of intervals from $Id_n$ containing the interval $(1..n)$.
A {\em PQ-tree representing the family $\mF$} is a tree $T(\mF)$ satisfying:

\begin{itemize}
\item[1.] its nodes are in bijection with a subset $S(\mF)$ of intervals from $\mF$, the root corresponding to $(1..n)$
\item[2.] its arcs represent all the direct (not obtained by transitivity) inclusions between intervals in $S(\mF)$
\item[3.] each node is labeled $P$ ou $Q$, and an order is defined for the children of each $Q$-node
\item[4.] an interval $I$ of $Id_n$ belongs to $\mF$ iff either it corresponds to a node, or there
exists a unique $Q$-node $z$ such that $I$  is the union of intervals corresponding to
successive children of $z$, according to the order defined for $z$.
\end{itemize}
\label{def:PQ}
\end{definition}

Note that the size of the tree is in $O(|S(\mF)|)$, thus allowing to drastically reduce the memory
space needed to store all the intervals in $\mF$. When labels $P$ and $Q$ are forgotten, the tree $T(\mF)$
is called the {\em inclusion tree} of $S(\mF)$.

Given the $PQ$-tree representing a family $\mF$, we denote by $Int(x)$ the interval from $S(\mF)$ corresponding
to a node $x$. We also denote, for each interval $I$ from $\mF$, by $D(I)$ the {\it domain} of $I$ defined
as follows. If $I\in S(\mF)$, then $D(I)$ is the set of its children. If $I\not\in S(\mF)$, then by condition
4. in Definition \ref{def:PQ}, let $x_l, x_{l+1}, \ldots, x_r$ be the children of the $Q$-node $z$ such
that $I=\cup_{i\in(l..r)}Int(x_i)$. Then $D(I)=\{x_l, x_{l+1}, \ldots, x_r\}$.

Fundamental results on $PQ$-trees involve {\it closed} families of intervals.

\begin{definition}
A {\em closed} family $\mathcal F$ of intervals of the permutation $Id_n$ is a family that contains all singletons as well
as the interval $(1..n)$, and that in addition has the following property:
if $(i..k)$ and $(j..l)$, with $i\le j \le k \le l$, belong to $\mathcal F$, then
$(i..j-1)$, $(j..k)$, $(k+1..l)$  and $(i..l)$ belong to $\mathcal{F}$.
\end{definition}

The construction of a $PQ$-tree for a closed family of intervals relies on strong
intervals:

\begin{definition}
Let $\mF$ be a family of closed intervals from $Id_n$. An interval $(i..j)$ is said to \emph{overlap} another interval
$(k..l)$ if they intersect without inclusion,  \emph{i.e.} $i<k\le j<l$ or $k<i\le l<j$.
An interval $I$ of $\mathcal F$ is {\em strong} if it does not overlap any other  interval of $\mF$,
and  is {\em weak} otherwise.
\label{def:strong}
\end{definition}

Notice that  $(1..n)$ and the unit intervals are always strong. Also,  the family
of strong  intervals of $\mF$ is \emph{laminar} (that is,
every two distinct intervals are either disjoint or included in each other)
and, as $(1..n)$ belongs to the family, it is possible to define for them an inclusion tree.
Then it can be shown that:

\begin{theorem}[\citet{landau2005using}]
\label{th1}
Given a closed family ${\mF}$ of  intervals of $Id_n$, let $S(\mF)$ be the set of strong intervals from $\mF$ and let
$T(\mF)$ be the inclusion tree of $S(\mF)$. Then the $PQ$-tree obtained by the following rules
represents the family $\mF$:
\begin{itemize}
\item[1.] label with $P$ each node $x$ of $T(\mF)$ such that $\cup_{z\in D'}Int(z)\not\in\mF$ for all
$D'\subset D(Int(x))$  with $2\leq |D'|<|D|$.
\item[2.] label with $Q$ each node $y$ of $T(\mF)$ not labeled $P$, and define the order $y_1, y_2, \ldots, y_r$
of its children such that $max(Int(y_i))<min(Int(y_{i+1}))$ for all $i<r$.
\end{itemize}

\end{theorem}

Common intervals of permutations (including those of size 1) are obviously a closed family of intervals from $Id_n$, thus
Theorem \ref{th1} applies.
Moreover, the $PQ$-tree for common intervals (hereafter simply denoted $T$) may be computed in linear time:

\begin{theorem}\citet{BCMR05}
The construction of the $PQ$-tree $T$ of common  intervals of a set $\mathcal{P}$ of
$K$ permutations on $n$ elements may be done in $O(Kn)$ time.
\end{theorem}

It is easy to note here that the leaves of $T$ are the singletons. Also,  the intervals
$Int(y_i)$, $i=1, 2, \ldots, r$, associated to the children of a $Q$-node are contiguous,
i.e. $max(Int(y_i))+1=min(Int(y_{i+1}))$. This is due to condition 4 in the definition of a
$PQ$-tree and to the assumption, that the reader must keep in mind, that $P_1=Id_n$ (thus
all the common intervals are of the form $(i..j)$). An example is given in Fig. \ref{figtotal2b}.

\begin{figure}[t]
 \begin{center}
\begin{tabular}{p{4cm}lp{4cm}}
\vspace {-.8 cm}\includegraphics[height=3cm]{TotPQ.pdf}&
\phantom{xxxxxxxx} &
\mbox{  Let $\mathcal{P}   = \{Id_9,P_2,P_3\}$,}\hfill \linebreak \centerline{$P_2=(4,2,3,1,7,8,9,6,5)$} \centerline{$P_3=(5,6,1,3,2,4,9,8,7)$}
 The $PQ$-tree for the set of common intervals of $\mathcal{P}$ is shown on the left.
\\
\end{tabular}
 \end{center}\vspace{-.3cm}
\caption{Example of PQ-tree}
 \label{figtotal2b}
\end{figure}

\subsection{Properties of $b$-nested common intervals}\label{sect:main}

Let $\mathcal{P}=\{P_1, P_2, \ldots, P_K\}$ be a set of permutations on $n$ elements such that $P_1=Id_n$, and
let $T$ be the $PQ$-tree representing the common intervals of $\mathcal{P}$.
Say that a common interval $I$ is a {\em $P$-interval} if it is strong and there is a $P$-node $x$ with $Int(x)=I$.
Otherwise, $I$ is a  {\em $Q$-interval}.

With the aim of identifying the particular structure of $b$-nested common  intervals
among all common  intervals, we first prove that:

\begin{lemma}\label{lemma:nonnested}
Let $I$ be a $b$-nested common  interval with $D(I)=\{x_1, x_2, \ldots,
x_r\}$, $r\geq 1$. Then each of the intervals $Int(x_i)$, $1\leq i\leq r$,  is either a $b$-small
or a $b$-nested common interval.
\end{lemma}
\begin{preuve}
Assume a contrario that some $Int(x_i)$ is of size $u\geq b+1$ and is not $b$-nested.
Let $I'\subseteq I$ be a $b$-nested common  interval with the property
that $x_i\in D(I')\subseteq D(I)$ and $D(I')$ is minimal with this property. Now,
since $I'$ is $b$-nested, we have that $I'$ strictly contains $Int(x_i)$ and thus
$|I'|>1$. Then $I'$ must contain some $b$-nested common  interval $J$ with
 $|I'|>|J|\geq|I'|-b$. Furthermore, $J$ and $Int(x_i)$ are disjoint since $Int(x_i)$ is strong
 and by the minimality of $I'$
we have that $J$ cannot contain $Int(x_i)$. But then $|I'|\geq |J|+|Int(x_i)|\geq |I'|-b + b+1=|I'|+1$,
a contradiction.
\end{preuve}

It is easy to see that:

\begin{remark}\label{rem:inclusion}
{\em Let $I, L, J$ be common  intervals such that $J\subseteq L\subseteq I$ and
$J$ is $b$-nested with $|J|\geq |I|-b$. Then  $L$ is $b$-nested, since
$|J| \geq |I|-b\geq |L|-b$.}
\end{remark}

Now, the characterization of $b$-nested intervals corresponding to a $P$-node is obtained as follows.

\begin{lemma}\label{lemma:round}
 Let $I$ be a $P$-interval with $D(I)=\{x_1, x_2, \ldots, x_r\}$. Then $I$ is a $b$-nested common
 interval if and only if there is some $i, 1\leq i\leq r$, such that $Int(x_i)$ is
a $b$-nested common  interval of size at least $|I|-b$.
\end{lemma}

\begin{preuve}
Since $I$ is a $P$-interval, its maximal common  subintervals are $Int(x_i)$,
$1\leq i\leq r$. The ''$\Leftarrow$'' part  follows directly from the definition. For the
''$\Rightarrow$'' part, assume by contradiction that the affirmation does not hold. Then none of
the intervals $Int(x_i)$, $1\leq i\leq r$, is $b$-nested of size at least $|I|-b$, but
since $T$ is $b$-nested we deduce that some interval $Int(x_i)$ exists
containing a $b$-nested common  interval $J$ of size at least $|I|-b$. But
this is impossible according to Remark \ref{rem:inclusion}.
\end{preuve}

The structure of $b$-nested common intervals given by consecutive children of a $Q$-node is more
complex. In the next lemmas we show that at most one of the intervals $Int(x_i)$ composing
such an interval may be $b$-large (see also Fig. \ref{bstruct}).

\begin{lemma}\label{lemma:firstlast}
 Let $I$ be a $Q$-interval with $D(I)=\{x_1, x_2, \ldots, x_r\}$. Then $I$ is a $b$-nested common
 interval if and only if
 $Int(x_1)$ is  $b$-small and $I-Int(x_1)$ is a $b$-nested common  interval, or $Int(x_r)$ is
 $b$-small and $I-Int(x_r)$ is a $b$-nested common  interval.
\end{lemma}

\begin{preuve}
Recall that for a $Q$-interval $I$, the order $x_1, x_2, \ldots, x_r$ implies that the equation
$max(Int(x_i))+1=min(Int(x_{i+1}))$ holds
for all $i$ with $1\leq i<r$.

$\Rightarrow$: Since $I$ is $b$-nested, it contains some $b$-nested interval $J$ such that $|I|>|J|\geq |I |-b$.
Choose $J$ as large as possible. Now, $J$ cannot be strictly included in some non $b$-nested $Int(x_i)$ by Remark \ref{rem:inclusion}, thus
$D(J)=\{x_p, x_{p+1}, \ldots, x_s\}$ with $p\geq 1, s\leq r$, and $p\neq 1$ or $s\neq r$.
Assume w.l.o.g. that $p>1$. Then $Int(x_1)$ is $b$-small (since $|J|\geq |I |-b$)
and $I-Int(x_1)$ is $b$-nested by Remark \ref{rem:inclusion} since it contains $J$ or is
equal to $J$.

$\Leftarrow$: Let $j=1$ or $j=r$ according to which proposition holds. We have that $|I-Int(x_j)|=|I|-|Int(x_j)|\geq |I|-b$ since $|Int(x_j)|\leq b$.
Then $I$ is $b$-nested.
\end{preuve}

\begin{lemma}\label{lemma:not2large}
 Let $I$ be a $Q$-interval with $D(I)=\{x_1, x_2, \ldots, x_r\}$ which is a $b$-nested common
interval. Then at most one of the intervals $Int(x_i)$, $1\leq i\leq r$, is $b$-large, and in
this case this interval is a $b$-nested common  interval.
\end{lemma}

\begin{preuve}
By contradiction, assume there exist $b$-nested common $Q$-intervals that contain at least two
$b$-large intervals of type $Int(x_i)$, and let $I$ be a smallest  such interval
w.r.t. inclusion. Let $x_u$ (resp. $x_v$), with $1\leq u,v\leq r$, be such that
$Int(x_u)$ (resp. $Int(x_v)$) is $b$-large and $u$ (resp. $v$) is minimum (resp. maximum) with this
property. Then $u=1$ and $v=r$, otherwise by Lemma \ref{lemma:firstlast} the minimality of
$I$ is contradicted. But now Lemma \ref{lemma:firstlast} is contradicted, since $Int(x_1)$ and
$Int(x_r)$ are both $b$-large.

Then, at most one of the intervals $Int(x_i)$, $1\leq i\leq r$, is $b$-large. To finish the proof,
assume that $Int(x_i)$ (for some fixed $i$), is the unique $b$-large interval and
apply Lemma \ref{lemma:nonnested} to $Int(x_i)$ to deduce that $Int(x_i)$ is $b$-nested.
\end{preuve}

\begin{figure}[t]
\vspace{-0.3cm}
  \centering
\includegraphics[width=5cm]{bnested.pdf}
\caption{Structure of a $b$-nested $Q$-interval. }
 \label{bstruct}
\vspace{-0.3cm}
\end{figure}
We are able now to prove the theorem characterizing $b$-nested common  intervals.

\begin{theorem}\label{th:all}
Let $I$ be a common  interval of $\mathcal{P}$.  $I$ is $b$-nested if and only if:
\begin{enumerate}
\item[(a)] either $I$ is a $P$-interval and there exists $x_h\in D(I)$ such that $Int(x_h)$ is a $b$-nested
common  interval of size at least $|I|-b$.
\item[(b)] or $I$ is a $Q$-interval with the property that all intervals $Int(x_i)$ with $x_i\in D(I)$ are
 $b$-small, with one possible exception which is a $b$-large $b$-nested interval.

\end{enumerate}
\end{theorem}

\begin{preuve}
Lemma \ref{lemma:round} proves the theorem in the case where $I$ is a $P$-interval. When
$I$ is a $Q$-interval, Lemma \ref{lemma:not2large} proves affirmation $(b)$.\end{preuve}

\subsection{Computing and counting all $b$-nested common intervals}\label{sect:algo}

Consider Algorithm \ref{algo:bnested1}, which computes all $b$-nested common intervals.
For a node $x_c$, the  notations $min(c)$ and $max(c)$ respectively indicate the minimum and the maximum
value in $Int(x_c)$.
Figure \ref{fig:algo} illustrates our algorithm.

\begin{algorithm}[h]
\label{algo:bnested1}
\dontprintsemicolon
\caption{The $b$-NestedCommonSearch algorithm}
\KwIn{The PQ-tree $T=(V,E)$ of $\mathcal{P}$ for common  intervals, a positive integer $b$}
\KwOut{All $b$-nested common  intervals of $\mathcal{P}$}
Perform a post-order traversal of $T$ \;
\For{each node $x$ of $T$ encountered during this traversal}{
  \eIf{$x$ is a leaf}{output $Int(x)$ as $b$-nested\;}{
     let $x_1, x_2, \ldots, x_p$ be the children of $x$ \;
     \eIf{$x$ is a $P$-node}{
      \If{$\exists$ $i$ such that $Int(x_i)$ is $b$-nested and $|Int(x_i)|\geq |Int(x)|-b$}{output $Int(x)$ as $b$-nested}
      }{
      \For{$c\leftarrow 1$ to $p$}{
           $\it large\leftarrow 0$ \hfill{//  number of $b$-large intervals already included}\;
           $d\leftarrow c$ \hfill{// considers all children starting with $x_c$}\;
           \While{$d\leq p$ and ($|Int(x_d)|\leq b$ or $Int(x_d)$ is $b$-nested) and $\it large\leq 1$}{
             \lIf{$|Int(x_d)|>b$}{$\it large\leftarrow \it large+1 {\bf endif}$\;}
             \If{$c<d$ and $\it large\leq 1$}{
                output $(min(c)..max(d))$ as $b$-nested\;
                }
             $d\leftarrow d+1$\;
            }
         }
     }
}
}

\end{algorithm}

\begin{theorem}

Algorithm \ref{algo:bnested1} correctly computes all the $b$-nested common  intervals,
assuming the $PQ$-tree is already built, in $O(n+nocc)$ time, where $nocc$ is the
number of $b$-nested common intervals in $\mathcal{P}$.
\end{theorem}

\begin{preuve} To show the algorithm correctness, note first that
all the leaves are output in step 4, and they are $b$-nested common
intervals. Moreover, all $b$-nested common intervals corresponding to
$P$-nodes are correctly output in step 9 according to Theorem
\ref{th:all}$(a)$. Next, $Q$-intervals corresponding to a $Q$-node $x$
are generated in steps 12-22 by starting with each child $x_c$ of $x$,
and successively adding right children $x_d$ as long as condition
$(b)$ in Theorem \ref{th:all} is satisfied (step 15).

Let us analyze now the running time. The $PQ$-tree has size $O(n)$, and the traversal considers
every node $x$ exactly once. Working once on the children of each node
takes $O(n)$. The test in line 8 considers every child of a $P$-node
one more time, so that the $O(n)$ time is ensured when the $Q$-interval
generation is left apart. Now, during the generation of the
$Q$-intervals, a node $x_d$ that belongs to no $b$-nested common
interval is uselessly included in some interval candidate at most once
by left initial positions for the scan (beginning line 12), which is
in total bounded by $n$ since there exists a linear number of initial
positions in the $PQ$-tree. At each iteration of
the loop line 15, a unique distinct $b$-nested interval is output, or
$c=d$ (that happens once for each node since $d$ is incremented at
each iteration), or $large = 2$ (that also happens once for each node
since it ends the loop). The total number of iterations is thus
$O(n+\mbox{\em nocc})$, each iteration taking $O(1)$. The overall running
time is thus in $O(n+\mbox{\em nocc}),$ where {\em nocc} is the
total number of $b$-nested common intervals.
\end{preuve}

\begin{figure}[t]
\vspace{-0.3cm}
  \centering
\includegraphics[width=9cm]{bqnode.pdf}
\caption{Computing all $b$-nested intervals of a $Q$-interval, where
  $bS$ (resp. $bL$) means $b$-small (resp. $b$-large). The algorithm
  considers all positions from left to right and expands the $b$-nested
  interval while it is possible.}
 \label{fig:algo}
\vspace{-0.3cm}
\end{figure}

The previous approach can be modified to count the $b$-nested common
intervals instead of enumerating them, by simply analyzing more
precisely the structure of the $Q$-nodes. The goal is to count the $b$-nested
common intervals in a time proportional to the number of children instead of the
number of $b$-nested common intervals. To perform the count, we assume that the traversal is post-order, that it marks each
vertex as $b$-nested or not, and that it computes the cardinality of each $Int(x_i)$.

{\bf $P$-nodes.} Obviously, a $P$-node (including the leaves) counts for 1 if the associated interval is $b$-nested, and for 0 otherwise.

{\bf $Q$-nodes.} To make the computation for a $Q$-node with children $\{x_1, x_2, \ldots,$ $x_p\}$, the algorithm looks for
the $b$-large $b$-nested intervals $Int(x_d)$  and counts\\
1)~the $b$-nested common intervals containing each $Int(x_d)$,
and\\
2)~the $b$-nested common intervals generated by maximal sets of consecutive $b$-small common intervals
$Int(x_i)$.  To this end, the vertices $x_i$ are considered from left to right in order to identify
both the $b$-large $b$-nested common intervals $Int(x_d)$,
and the maximal sets of consecutive $b$-small common intervals
$Int(x_i)$. Then:

To solve 1), each encountered $b$-large $b$-nested interval $Int(x_d)$ has the following treatment. We
count the number of consecutive $b$-small nodes $x_i$ on its right (resp. left), denoted by
$r(d)$ (resp. $l(d)$).  Then we compute the number of $b$-nested common intervals
which contain child $x_d$ as $$l(d)*(r(d)+1)+r(d).$$

To solve 2),  for each maximal set of consecutive $b$-small common intervals
$Int(x_i)$, assuming it has size $h$, we count $$h*(h-1)/2.$$

One may easily decide whether the interval corresponding
to the $Q$-node itself is $b$-nested or not, and compute its size.

All these operations may be performed in $O(k)$ time, where $k$ is the number of sons of the $Q$-node.
\bigskip

{\bf Example.} On the
example in Fig. \ref{fig:algo}, we count (from left to right): (a)
for the first $b$-large strong child to the left: $3*(2+1)+2=11$ $b$-nested common
intervals; (b) for the $b$-large second strong child: $2*(1+1)+1=5$ $b$-nested common
intervals; (c) for the last $b$-large strong child: $1*(0+1)=1$ $b$-nested common
intervals. We sum up to obtain $17$ $b$-nested common intervals containing one $b$-large $b$-nested
interval $Int(x_i)$. Now we add the nested intervals generated between the $b$-large intervals:
$3+1=4$. Altogether, the $Q$-node of Figure \ref{fig:algo} generates $21$ $b$-nested intervals.

\paragraph{Complexity} The time complexity of the counting procedure is obviously $O(n),$ the size of the underlying $PQ$-tree. The time needed to get the PQ-tree itself given $K$ permutations is however $O(Kn)$, as indicated before.

\section{On $b$-nested conserved intervals}
\label{sect:conservedtree}

As stated before, we assume the set $\mathcal{P}$ of permutations has the properties required in
Definition \ref{def:conserved}. As conserved
intervals are common intervals, one may be tempted to follow the same approach using $PQ$-trees.
Unfortunately, the inclusion tree of strong conserved intervals does not define a $PQ$-tree representing
the family of conserved intervals, due to the fact that a  conserved interval  cannot be
written as a disjoint union of strong conserved intervals. The resulting
{\em ordered tree} has been used in the literature \citet{BergeronBCC04}, but its underlying
properties have not been clearly stated. We do it here, before using these properties.

\subsection{Structure of conserved intervals}

We start by an easy property about intersection of conserved intervals:

\begin{lemma}\label{lemstru2}
Let $I=(u..v)$ and $J=(c..d)$ be two conserved intervals of $\mathcal{P}$  with $u<c\le
v<d$. Then the intervals $(u..c)$, $(c..v)$, $(v..d)$ and
$(u..d)$ are conserved intervals.
\end{lemma}

\begin{preuve}
As an element $x$ from $I$ fulfills $u\le x\le v$ and an element $y$
from $J$ fulfills $c\le y \le d$ then an element $z$ from $I\setminus
J$ fulfills $u\le z < c$. These elements are exactly those between $u$
and $c$ and $(u..c)$ is thus a conserved interval. Similarly,
$J\setminus I=(v..d)$.The elements from $I\cap J$ are all the elements
not lower than $v$ and not larger than $c$,  so $(c..v)$ is a conserved interval.
Finally, the elements from $I\cup J$ are
all elements greater than $u$  and smaller than $d$, so $(u..d)$ is a conserved
interval.
\end{preuve}

The notions of strong/weak intervals and of a frontier are essential in our study.

\begin{definition}
A conserved interval $I$ of $\mathcal{P}$ is {\rm strong} if it has cardinality at least two, and does not overlap
other conserved intervals. Otherwise, it is {\em weak}.
\end{definition}

Notice that unit conserved intervals are not strong.

\begin{definition}
Let $I=(a..c)$ be a  conserved interval.  A set
$\{f_1, \ldots, f_k\}$ of elements satisfying $a=f_1<f_2<\ldots <f_k=c$ is a
\emph{set of frontiers} of $I$ if $(f_i..f_j)$ is a conserved
interval, for all $i,j$ with $1\le i < j \le k$. An element of $I$ is
a \emph{frontier} of $I$ if it occurs in at least one set of frontiers
of $I$.
\end{definition}

The two following properties are easy ones:

\begin{lemma}\label{lemstru1}
Let $I=(a..c)$ be a conserved interval and $F$ be a set of frontiers of $I$.
 The elements of $F$  are either all positive or all negative.
\end{lemma}
\begin{preuve}
 By the definition of a conserved interval, its two endpoints have the
 same sign. By the definition of a set on frontiers, any two frontiers
 are the extremities of some conserved interval.
\end{preuve}

\begin{lemma}
\label{unionfrontier}
Let $I=(a..c)$ be a conserved interval, and  let $F=\{f_1, \ldots, f_k\}$ and
$F'=\{f'_1, \ldots, f'_l\}$ be two sets of frontiers of $I$. Then $F \cup F'$ is
also a set of frontiers of $I$.
\end{lemma}
\begin{preuve}
We show that any interval between two elements of $F\cup F'$
is conserved. Let
$f_i\in F$ and $f'_j\in F'$, and suppose that $f_i<f'_j$. If $f_i=a$, then we have
$(f_i..f'_j)=(f'_1..f'_j)$ and we are done.  If $f'_j=c$, then
$(f_i..f'_j)=(f_i..f_k)$ and we are also done. If $f_i\ne a$ and $f'_j\ne
c$,
then Lemma \ref{lemstru2} allows to conclude.
The same proof holds if $f_i>f'_j$.
\end{preuve}

Let now $T$ be the inclusion tree of strong intervals from $\mathcal{P}$, in which
every node $x$ corresponds to a strong interval denoted $Int(x)$, and
node $x$ is the parent of node $y$ iff $Int(x)$ is the  smallest strong
conserved interval strictly containing $Int(y)$. Then $T$
contains two types of nodes: those corresponding to strong conserved
intervals with no internal frontier, and those corresponding to strong
conserved intervals with at least one internal frontier. We will show that
weak conserved  intervals are the conserved strict subintervals of the latter ones, defined by two frontiers.
Overall, we have a structure working pretty much as a $PQ$-tree, but which
cannot be mapped to a $PQ$-tree. This is proved in the next theorem.

Given a conserved interval, denote by $\mbox{Container}(I)$
the smallest strong conserved interval such that $I \subseteq J$.

\begin{theorem}
\label{theostruc2}
Each conserved interval $I$ of $\mathcal{P}$ admits a unique maximal
(w.r.t. inclusion) set of frontiers denoted $F_I$.
Moreover, each conserved
interval $I$ of $\mathcal{P}$ satisfies one of the following
properties:
\begin{itemize}
\item[1.] $I$ is strong
\item[2.] $I$ is weak and there exists a unique strong conserved interval $J$ of
  $\mathcal{P}$, and two frontiers $f_i, f_j\in F_J$ with $f_i<f_j$, such that
  $I=(f_i..f_j)$. Moreover  $F_I = F_J\cap I$ and $J = \mbox{Container}(I).$
\end{itemize}
\end{theorem}

\begin{preuve}
Let us first prove the uniqueness of the maximal set of frontiers. By contradiction, assume
two distinct maximal sets of frontiers $F=\{f_1,\ldots,f_k\}$ and $F'=\{f'_1,\ldots,f'_l\}$ exist
for a conserved interval  $I$. Using Lemma \ref{unionfrontier}, we deduce that
$F\cup F'$ is a larger set of frontiers of $I$, a contradiction.

Let us now prove that if $I$ is not strong, then  there exists a unique strong conserved interval
$J$, and two frontiers $f_i, f_j\in F_J$ with $f_i<f_j$, such that $I=(f_i..f_j)$.

{\em Existence of $J$.} Let $I_1=I=(a_0..a_1)$ be a weak conserved interval of $\mathcal{P}$.
Then there is another interval $I_2$ overlapping it, either on its left
(i.e. $I_2=(a_2..x_2)$ with $a_2<a_0\le x_2 < a_1$)
or on its right (i.e. $I_2=(x_2..a_2)$ with $a_0<x_2\le a_1 <
a_2$). According to Lemma~\ref{lemstru2}, $J_2=I_1\cup I_2$ is a
conserved interval, and $F_2=\{a_0, a_1, a_2, x_2\}$ is a set of frontiers
for $J_2$ (not necessarily all distinct). If $J_2$ is not strong then it is overlapped by
another interval $I_3$.  We build an increasing sequence of intervals
$J_1=I_1,J_2,\ldots,J_k$, with $J_i$ overlapped by $I_{i+1}$, and
$J_{i+1} = J_i \cup I_{i+1}$, until we find a strong conserved
interval $J_k$ (the process ends since $(1..n)$ is strong). Each time
Lemma~\ref{lemstru2} ensures that $J_{i+1}$ is a conserved interval,
and $F_{i+1}=F_i\cup\{a_{i+1},x_{i+1}\}$ is a set of frontiers for $J_{i+1}$
(where $a_{i+1},x_{i+1}$ are the
endpoins of  $I_{i+1}$). But then $F_{k}$ is a subset of the maximal set of
frontiers $F_{J_{k}}$ of $J_k$ and the two frontiers of  $J_k$ defining
$I_1$ are $a_0, a_1$, since $\{a_0,a_1\}\subseteq F_2\subseteq F_3\subseteq  \ldots\subseteq F_k\subseteq F_{J_k}$.

{\em Uniqueness of $J$.} Assume a contrario that two strong intervals $J_1$ and $J_2$ exist with
$F_{J_1}=\{f_1, \ldots, f_p\}$, $F_{J_2}=\{f'_1, \ldots, f'_r\}$ and
such that $I=(f_i..f_j)=(f'_k..f'_l)$ with $1\leq i<j\leq p$ and
$1\leq k<l\leq r$.  Then, clearly, $f_i=f'_k$ and this is the left
endpoint of $I$, whereas $f_j=f'_l$ and this is the right endpoint of
$I$.  Since $J_1$ and $J_2$ are both strong, they cannot
overlap. Assume then w.l.o.g. that $J_1$ is strictly included in
$J_2$, and more precisely that $f_p\neq f'_r$ (then $f_p<f'_r$ due to
inclusion). Now, $(f'_k..f'_r)$ overlaps $J_1$ (which is forbidden) unless $i=1$, in which
case we have $f_1=f_i=f'_k$ and this is the left endpoint of $I$. Now,
since $I$ is strictly included in $J$, we deduce $j<p$ and
$(f'_l..f'_r)$ overlaps $J_1$. This contradiction proves the
uniqueness of the strong interval $J$ satisfying condition~2.

Let us prove that $F_I = F_J\cap I$. Suppose by contradiction that $F_I$
contains a frontier $f$ not in $F_J$. Recall that $I=(a_0..a_1)$ and
$a_0$, $a_1$ belong to $F_J$. Now, for each $f_l\in F_J$ with $f_l < f$, we have that
$(f_l..f)$ is a conserved interval either by Lemma~\ref{lemstru2} applied
to $(a_0..f)$ and $(f_1..f_l)$ (when $f_l\geq a_0$) or since it is the union
of the two conserved intervals $(f_l..a_0)$ and $(a..f)$ (when $f_l<a_0$).
Symmetrically, $(f..f_l)$ is also a conserved interval when $f_l\in F_J$, $f_l > f$.
But then $F_J \cup \{f\}$ is a set of frontiers of $J$ larger than $F_J$,
which contradicts the maximality of $F_J.$

Eventually, let us prove that $J = \mbox{Container}(I).$ Assume that
$F=\{f_1, f_2, \ldots,$ $f_k\}$, that $I=(f_i..f_j)$ and that, by contradiction, there
is a smallest strong conserved interval $J'=(a..c)$ which contains
$I$. Then $J' \subsetneq J$ since otherwise $J$ and $J'$ would
overlap. W.l.o.g. assume that $f_j\neq c$. Then $(f_i..f_k)$
overlaps $J'$, and this contradicts the assumption that $J'$ is strong.
\end{preuve}

We only need three more results before dealing with $b$-nested conserved
intervals.

\begin{lemma}\label{memecontainer}
Let $I$ and $J$ be two conserved intervals. If there exists a frontier $f\in F_I \cap F_J$,
then $\mbox{Container}(I)$ $=$ $\mbox{Container}(J).$
\end{lemma}

\begin{preuve}
Since both $\mbox{Container}(I)$ and $\mbox{Container}(J)$ are strong,
and since they share a common element, one contains the other. Now, suppose
w.l.o.g. that $\mbox{Container}(I)\subseteq \mbox{Container}(J)$.  By contradiction,
assume that $\mbox{Container}(I)\subsetneq \mbox{Container}(J)$ and let
$\mbox{Container(J)}=(a..c)$. Since $f\in F_J$ and that by Theorem
\ref{theostruc2} we have $F_J=F_{(a..c)}\cap J$, we deduce that $f \in F_{(a..c)}$ and thus
$(a..f)$ and $(f..c)$ are conserved intervals. Now, one of them necessarily
overlaps $\mbox{Container}(I)$, since at least one of $a,c$ is not an endpoint of
$\mbox{Container}(I)$. But this is impossible. Therefore $\mbox{Container}(I)$ $=$
$\mbox{Container}(J).$
\end{preuve}

\begin{lemma}
\label{coro1}
Let $I$ be a (weak or strong) conserved interval with frontier set
$F_I=\{f_1, \ldots, f_k\}$ and let $(a..c)\subseteq I$ be a conserved interval. Then
exactly one of the following cases occurs for the interval $(a..c)$:
\begin{enumerate}
\item either there exists $l$ such that $f_l\in (a..c)$, and then
there exist $i$ and $j$ such that $(a..c)=(f_i..f_j)$.
\item or $(a..c)$ contains no frontier of $F_I$, and then there exists $i$ such that
$f_i < a \le c < f_{i+1}$.
\end{enumerate}
\end{lemma}

\begin{preuve} Obviously, the two cases cannot hold simultaneously. Moreover,
in case 2., the deduction is obvious.

Let us focus now on the case 1. Let $(a..c)$ contain some frontier $f_l \in F_I$.
Consider now the two intervals $(f_1..f_l)$ and $(f_l..f_k).$ Then
either {\em (i)} $(a..c)=(f_1..f_k)=I$, or {\em (ii)}
$(a..c)=(f_l..f_l)$, or {\em (iii)} $l=1$ or $l=k$, or {(iv)} $(a..c)$ overlaps
$(f_1..f_l)$ or $(f_l..f_k)$. The two first cases are trivial, let us
consider the two last cases.

In case {\em (iii)} assume w.l.o.g. that $l=1$ (the case $l=k$ is
symmetric). Then $a= f_1$ since $(a..c)\subseteq I$.  Since $(a..c)$
contains the elements of $I$ that are smaller or equal to $c$, then
$(c..f_k)$ is a conserved
interval. Thus $\{f_1,c,f_k\}$ is a frontier set of $I$. If $c\not\in
F_I$ then according to Lemma~\ref{unionfrontier} we have that $\{f_1,c,f_k\}\cup
F_I$ is a frontier-set of $I$ contradicting the maximality of
$F_I$. We deduce that there exists $j$ such that $c=f_j$.
Now we are done, since $(a..c)=(f_1..f_j)$.

In case {\em (iv)}, $(a..c)$ is necessarily weak since it overlaps another
conserved interval. W.l.o.g. we assume that $(f_1..f_l)$ overlaps $(a..c).$
Let us first prove that $f_l$ is also a frontier of $(a..c)$.  Indeed,
assume {\em a contrario} that $f_l\not \in F_{(a..c)}$, and denote
$F_{(a..c)}=\{f^*_1, \ldots , f^*_p\}$. With $h\in\{1, 2, \ldots, p\}$,
we have either $f^*_h<f_l$ and by Lemma \ref{lemstru2} for $(f_1..f_l)$ and
$(f^*_h..c)$ we deduce that $(f^*_h..f_l)$ is conserved, or $f_l<f^*_h$ and then
Lemma \ref{lemstru2} for $(a..f^*_h)$ and $(f_l..c)$ we deduce that $(f_l..f^*_h)$
is conserved. Then
$F_{(a..c)} \cup \{f_l\}$ is a set of frontiers of $(a..c)$, which
contradicts the maximality of $F_{(a..c)}$.
Now, by Lemma \ref{memecontainer} for $\mbox{Container}((a..c))$ (whose
frontier set contains $f_l$ by Theorem \ref{theostruc2}) and $\mbox{Container}(I)$
we deduce that $\mbox{Container}((a..c))=\mbox{Container}(I)$. Thus using
Theorem \ref{theostruc2}, we conclude that $(a..c)=(f'_i..f'_j)$ for
some $f'_i,f'_j\in F_{{\mbox{Container}(I)}}$. But since $(a..c)\subseteq I$
and $F_I=F_{{\mbox{Container}(I)}}\cap I$, we are done.
\end{preuve}

The following theorem ensures that in the inclusion tree $T$ of the strong conserved intervals
of $\mathcal{P}$, weak intervals are exactly the intervals extending between two frontiers
of a strong interval. Moreover, each weak interval is uniquely represented in
such a way. In addition, the computation of the tree and of all the frontier sets
is linear.

\begin{theorem}
Let $T$ be the inclusion tree $T$ of strong conserved intervals of a set $\mathcal{P}$ of permutations.
Then:
\begin{enumerate}
\item  a conserved interval $I$ of $\mathcal{P}$ is weak if and only if there exists
a strong interval $J$ of $\mathcal{P}$ and two frontiers $f_i, f_j\in F_J$ such
that $I=(f_i..f_j)$. Moreover, in this case $J$ is unique.
\item for each strong conserved interval $I$ of $T$ with parent $J$ in $T$, there is a unique conserved
interval $L(I)=(f_i.. f_{i+1})$ defined by
successive frontiers  in $F_J$ such that $I\subsetneq (f_i..f_{i+1})$.
\item the tree $T$, the maximal set of frontiers $F_J$ of each strong conserved interval $J$
and the interval $L(I)$ of each strong conserved interval $I\neq (1..n)$ may be computed
in global $O(n)$ time and $O(n)$ space.
\end{enumerate}
\label{th:arbreT}
\end{theorem}

\begin{preuve}
Concerning affirmation 1, the ''$\Rightarrow$'' part is deduced directly from Theorem~\ref{theostruc2},
whereas the ''$\Leftarrow$'' part is ensured by the definition of a set of frontiers.
Again by Theorem \ref{theostruc2}, we deduce the uniqueness of $J$.

Affirmation 2 results from Lemma \ref{coro1}. According to affirmation 1 in this lemma, $I$ cannot contain
a frontier of $J$, since otherwise $I$ would be of the form $(f_i..f_j)$, with $f_i,f_j\in F_J$,
and thus would not be strong. Thus, by affirmation 2 in Lemma \ref{coro1}, we deduce the existence of $L(I)$,
which is necessarily unique by the definition of the frontiers.

We focus now on affirmation 3. In \citet{BS06}, a conserved interval is called {\it irreducible} if it cannot
be written as the union
of smaller conserved intervals. It is easy to notice that the set of irreducible intervals of
size at least two is exactly composed of the intervals $(f_i..f_{i+1})$, where
$f_i,f_{i+1}$ are two consecutive frontiers of a strong conserved interval of $\mathcal{P}$.
Indeed, affirmation 1 shows that the only irreducible weak conserved intervals $I=(f_i..f_j)$
are those for which $j=i+1$, and obviously the only irreducible strong intervals $I$ are those
with $|F_I|=2$, which are of the form $(f_1..f_2)$, with $F_I=\{f_1,f_2\}$.

To show affirmation 3, we notice that the number of irreducible intervals is in $O(n)$ [\citet{BS06}],
and that they may be computed in $O(n)$ time and space for an arbitrary number $K$ of permutations using
generators from \citet{IRconserved}.  Knowing irreducible conserved intervals, the computation of
strong intervals, of their set of frontiers, as well as that of the tree is quite easy. First, one
must plot on the identity permutation the $O(n)$ irreducible intervals of size at least two, by marking the left and
right endpoint of each such irreducible interval. Notice that each element $p$ of the permutation $Id_n$
has at most two marks, the equality occurring only when $p$ is an internal (that is, different from
an endpoint) frontier of a strong interval. We assume the right mark of $p$ (when it exists)
always precedes the element $p$ whereas the left mark (when it exists) always follows the element $p$,
so that a left-to-right traversal of $Id_n$ allows to close the interval with right endpoint
$p$ before opening the interval with left endpoint $p$.

Replacing left and right marks with respectively (square) left and right brackets indexed by their corresponding
element $p$ on $Id_n$, we obtain an expression $E$ which has correctly nested brackets,
since irreducible intervals may only overlap on one element. Moreover,  if $I$ and $J$ are strong
intervals such that $J$ is the parent of $I$, then $I\subsetneq L(I)\subseteq J$ and thus these
intervals are closed exactly in this order during a left-to-right traversal of the expression $E$.
The expression $E$ then allows, during a left-to-right traversal, to discover the strong intervals
according to a post-order traversal of $T$, which is built on the fly. A strong conserved interval $J$
is obtained by chaining as long as possible neighboring irreducible intervals, i.e. such that the
right bracket of an interval is followed by the endpoint $p$  of the interval and by the left bracket
of the next interval. Its frontiers  are given by the endpoints of the chained irreducible intervals.
Also, since $I\subsetneq L(I)$ for all strong intervals $I$, it is easy to identify $L(I)$ since it is
the interval which closes immediately after $I$ during the traversal.
\end{preuve}

{\bf Example.} Let $\mathcal{P}=\{Id_9,P_2\}$, where $P_2=(1,-3,-2,4,5,-8,-7,-6,9)$. The strong intervals
are $(1..9)$ (with frontier set $\{1, 4, 5, 9\}$), $(2..3)$ (with frontier set $\{2,3\}$) and
$(6..8)$ (with frontier set $\{6,7,8\}$). To build $T$, we first plot the irreducible intervals, i.e.
$(1..4), (2..3), (4..5), (5..9), (6..7)$ and  $(7..8)$ on $P_1$, and we obtain the expression:
$$E=1\,\,[_1\,\, -3\,\, [_3\,\,\, ]_2\,\, -2\,\, ]_4\,\ 4\,\, [_4 \,\,\,]_5\,\, 5\,\, [_5\,\, -8\,\, [_8 \,\,\,]_7\,\, -7\,\, [_7 \,\,\,]_6\,\, -6\,\, ]_9\,\, 9\,.$$

\noindent A left-to-right traversal of $E$ allows to find first the interval $(2..3)$ which is included in $(1..4)$,
and thus the node $(2..3)$ of $T$ is built, and a node $x$ starting with $(1..4)$ is created and defined as the parent
of $(2..3)$. Next, the interval $(1..4)$ in $x$ is continued with $(4..5)$ (just change the interval inside
the already existing node), and continued with another interval $(5..t)$, where $t$ is not yet known.
Still,  $(7..8)$ is discovered as a subinterval of $(5..t)$, and it may be continued with $(6..7)$,
thus creating together the interval $(6..8)$ which is another child of $x$. Once this is done, we read
$9$ which indicates that $t=9$. Thus $T$ has three nodes, the root $(1..9)$ (with frontier set $\{1, 4, 5, 9\}$
discovered during the traversal), and its two children $(2..3)$ (with frontier set $\{2,3\}$) and
$(6..8)$ (with frontier set $\{6,7,8\}$ discovered during the traversal).

\subsection{Properties of $b$-nested conserved intervals}
\label{sect:conservedproperties}

Recall that by definition all $b$-small conserved
intervals are $b$-nested conserved intervals. The
characterization below of $b$-nested conserved intervals has some
similarities with that of $b$-nested common intervals represented in
the $PQ$-tree as $Q$-intervals (see affirmation $(b)$ in Theorem
\ref{th:all}).

 Let $J$ be a conserved interval and let $F_J=\{f_1, f_2, \ldots,
 f_k\}$ be its maximal set of frontiers. We say that $J$ {\em contains a
 $b$-\emph{gap} at position $l$} if $(f_l..f_{l+1})$ is $(b+1)$-large.
 Furthermore, we say that a conserved interval $(a..c)$ {\em falls in the
 gap} between $f_l$ and $f_{l+1}$ of $J$ if $f_l<a\leq c<f_{l+1}$ and
 $\mbox{Container}((a..c))$ has the parent $\mbox{Container}(J)$. In other
 words, $J$ is represented in $T$ by the node $\mbox{Container}(J)$
 and $(a..c)$ is  represented by the node $\mbox{Container}((a..c))$,
 in such a way that the former node is the parent of the latter one.

A $b$-gap at position $l$ is said \emph{good} if it contains at least one
$b$-nested strong conserved interval $I$ with $|I|\geq |(f_l..f_{l+1})|-b$,
or equivalently $|I|\geq f_{l+1}-f_l+1-b$. Then a good $b$-gap is
a $b$-nested conserved interval.

\begin{theorem}\label{thgap}
A conserved interval $J$ of $\mathcal{P}$ is $b$-nested if and only if it contains no
$b$-gap, or if it contains exactly one good $b$-gap $f_l..f_{l+1}$.
\end{theorem}

\begin{preuve}

We first prove the ''$\Leftarrow$'' part.  Let $J$ be a conserved
interval with maximal set of frontiers $F_J=\{f_1, f_2, \ldots,
f_k\}$. If $J$ contains exactly one $b$-gap, let it be at position
$l$. Otherwise, let us fix arbitrarily $l=1$.  In both cases, $(f_l..f_{l+1})$ is a
conserved $b$-nested interval: either because it is $b$-small, or because
it is a good $b$-gap. Now, for all $j>l+1$ in increasing order, we deduce by
induction that  $(f_l..f_j)$ is a conserved interval (by definition of the set of
  frontiers) containing $(f_l..f_{j-1})$, and thus it is
  $b$-nested. Thus $(f_l..f_k)$ is a conserved $b$-nested interval.
  Similarly, we deduce by induction that $(f_u..f_k)$ is a conserved
  $b$-nested interval, for all decreasing values of $u=l-1, l-2,
  \ldots, 1$. Thus $J=(f_1..f_k)$ is $b$-nested.

Now let us prove the ''$\Rightarrow$'' part, by proving (a) that an
conserved interval with two $b$-gaps or more is not $b$-nested, and (b) that if
a $b$-nested conserved interval contains one $b$-gap then this $b$-gap is good.

{\sf Proof of (a). } Assume by contradiction that $J$ with $F_{J}=\{f_1, f_2, \ldots, f_k\}$ is
conserved $b$-nested and contains two $b$-gaps at initial positions $l$ and $r$
($l < r$). The $b$-nestedness of $J$ implies the existence of a $b$-nested
conserved interval $J'\subsetneq J$ such that $|J'|\geq |J|-b$. Now,
$|J'\cap (f_l..f_{l+1})|\geq 2$, otherwise $J'$ misses at least $b+1$
elements from $(f_l..f_{l+1})$ (which is $(b+1)$-large) and thus
$|J'|\leq |J|-(b+1)$, a contradiction. Similarly, $|J'\cap (f_r..f_{r+1})|\geq 2$.
We deduce that $J'$ contains both $f_{l+1}$ and $f_{r}$, as well as at least one
additionnal element on the left of $f_{l+1}$ and one additionnal element on the right of
$f_{r}$. By Lemma \ref{coro1} with $I=J$ and $(a..c)=J'$ we have that $J'=(f_u..f_v)$
with $u\leq l$ and $r+1\leq v$. Thus the existence of the $b$-nested interval
$J$ containing the two $b$-gaps implies the existence of a smaller $b$-nested
interval $J'$ still containing the two $b$-gaps.

Now assume a maximal size series $J_0=J, J_1=J', \ldots$ of $b$-nested conserved
intervals has been built similarly, each interval being strictly included in the previous one, all containing
the two $b$-gaps. Such a series ends with $(f_l..f_{r+1})$, since
otherwise (if the last interval is larger)  it is possible to construct a smaller $b$-nested interval
included in the last interval and containing $(f_l..f_{r+1}).$ Thus
$(f_l..f_{r+1})$ is $b$-nested. But this is not possible, as it cannot
strictly contain another $b$-nested common interval of size at least
$(|f_l..f_{r+1})|-b$. As before, such an interval needs to contain the two gaps, and
it is therefore not strictly included in $(f_l..f_{r+1}).$

{\sf Proof of (b).}  Assume now that $J$ with $F_{J}=\{f_1, f_2, \ldots, f_k\}$ is
conserved $b$-nested and has a unique $b$-gap situated at position $l$. As before,
$J$ must contain a $b$-nested conserved interval $J'$ with $|J'|>|J|-b$ and then
$|J'\cap (f_l..f_{l+1})|\geq 2$ implying by Lemma \ref{coro1} that $J'$ must contain
$(f_l..f_{l+1})$. The smallest interval obtained following the same reasoning is then
$(f_l..f_{l+1})$ itself, which must be $b$-nested. As this interval has no internal frontiers
(otherwise $F_{J}$ would not be maximal), any $b$-nested common interval $I=(a..c)$ of size at
least $f_{l+1}-f_l+1-b$ it contains satisfies $f_l<a<c<f_{l+1}$. If $I$ is strong
then we are done, otherwise $\mbox{Container}(I)$ is strong and has all the required
properties.
\end{preuve}

\subsection{Computing and counting all $b$-nested conserved intervals}
\label{sect:computingconserved}

Theorem \ref{th:arbreT} allows to count and to enumerate efficiently all
$b$-nested conserved intervals. The computation may be performed, as was
the case for common intervals, in a single post-order traversal of the inclusion tree $T$,
focusing on each strong conserved interval $I$ of $\mathcal{P}$. First compute the $b$-gaps of $I$.
Mark $I$ as $b$-nested if it contains no $b$-gap or one $b$-gap $(f_l..f_{l+1})$, with $f_l,f_{l+1}\in F_I$,
that is a good one. The latter verification assumes that during the treatment of each child $I'$ of
$I$, if $I'$ is detected as $b$-nested, then $L(I')$ (which is an interval $(f_j..f_{j+1})$ with
$f_j,f_{j+1}\in F_I$) is marked as good if and only if $L(I')$ is a $b$-gap and $|I'|\geq |L(I')|-b$
(otherwise, $L(I')$ is not marked at all). Now, if $I$ is $b$-nested and $I\neq (1..n)$,
the same type of mark is performed on $L(I)$ if the conditions are fulfilled.

Then, applying Algorithm~\ref{alg2} on each strong conserved interval
$I$ allows to enumerate all the $b$-nested conserved intervals generated by the
frontiers of  $I$, according to Theorem \ref{th:arbreT}. Affirmation 1 in Theorem \ref{th:arbreT}
ensures that each interval is output exactly once.
The running time of Algorithm~\ref{alg2} is clearly linear in the number of intervals output plus
the numbers of children of $I$, yielding a global $O(n+nocc)$ time.

\begin{algorithm}[h!]
\dontprintsemicolon
\caption{Conserved $b$-nested intervals \label{alg2}}
\KwIn{A strong conserved interval $I$, its frontier set $F_I$, the children of $I$ in $T$ marked as nested or not}
\KwOut{The conserved $b$-nested intervals generated by the frontiers of $I$ and strictly included in $I$}
\For{$i$ from $1$ to $|F_I|$}{
$j\gets i+1$\;
goodgaps $\gets$ 0 \hfill{// counts the good $b$-gaps between $f_i$ and $f_j$}\;
stop $\gets false$\;
\Repeat{{\rm stop} and ($j=|F_I|+1$ or ($i=1$ and $j=|F_i|$))}{
  \If{$f_j - f_{j-1} > b+1$}{
 // Found a  $b$-gap at $j$\;
    \eIf{$(f_j,f_{j+1})$ is a good gap and {\rm goodgaps} $=0$}
        {goodgaps $\gets$ 1\;}
        {stop $\gets true$\;}
   }
   \lIf{not {\rm stop}}{output $(f_i..f_j)$ {\bf end if}}  \hfill{// notice $(f_1..f_{|F_I|})$ is not output}\;
   $j\gets j+1$\;
}
}

\end{algorithm}

To simply count the number of $b$-nested conserved intervals in $I$, we must follow the same
approach as for common intervals. Good and not good $b$-gaps are identified during a search
among the intervals $(f_l..f_{l+1})$, where $F_I=\{f_1, f_2, \ldots,$ $f_k\}$. Then, for
each good $b$-gap we compute the number $l$ (respectively $r$) of successive
$(b+1)$-small intervals $(f_i..f_{i+1})$ on its left (respectively right). We count
the number of $b$-nested conserved intervals containing the good $b$-gap as
$$l*(r+1)+r.$$ Next, for each maximal set of successive $(b+1)$-small intervals
$(f_i..f_{i+1})$ we add
$$h*(h-1)/2$$
$b$-nested common intervals, where $h$ is the number of $(b+1)$-small intervals in the set.

All these operations  obvisously take $O(n)$ time and space.

\section{Conclusion}\label{sect:conclusion}
In this paper we introduced the family of $b$-nested common intervals
of $K$ permutations, and showed that it may be computed in time
proportional to its cardinality. This approach extends to any
closed family of intervals that is represented by a $PQ$-tree. We also
show that our approach can be applied to conserved intervals, whose
structure and properties are close but still different from those of common
intervals. The interest of our generalization of common/conserved intervals
for finding conserved clusters of genes should be attested by further experiments.
Also, other applications may be devised, such as helping the identification of
orthologs/paralogs or defining distances between genomes in an
evolutionary approach. These are the close perspectives of our work.

\bibliographystyle{plainnat}

redpajama_set_name: RedPajamaArXiv


text:
Home > Reality Tv > CBS
Broken 'Bones'? David Boreanaz To Leave Hit FOX Show After Current Season
By:Radar Staff
Oct. 7 2013, Published 7:12 a.m. ET
First comes love, then comes marriage, then comes cancellation?
Bones stars David Boreanaz and Emily Deschanel will wed on-screen on the October 21 episode of the Fox series, but production sources say their love won't last for long because Boreanaz is planning to quit when the season ends in May 2014!
After nine seasons on the show, "David is telling friends that it's his last season," a source says.
And according to the insider, it's not a negotiating tactic.
Indeed, Boreanaz has been itching to leave for at least the past year. In June 2012, he Tweeted, "I'm a free agent after this season Season8. So the Bones farewell tour is in full-swing. You must always keep your options open and ready for new challenges. The fear is the unknown and that's exciting."
By January 2013, however, he agreed to stay on "at least through season nine," creator Hart Hanson said at the time.
CBS News Boss Who Feuded With Norah O'Donnell Facing Internal Review, Subject Of Months-Long HR Probe After 'Micromanaging' Complaints
CBS News Confirms Authenticity Of Content Found On Hunter Biden's 'Laptop From Hell'
'Without A Trace' Star Poppy Montgomery's Ex-Housekeeper Demands $100k In Court Over Alleged Unpaid Wages
And while Boreanaz is unlikely to return for Season 10, says the source, Deschanel is committed to keeping the show going with or without her co-star.
Fox, however, may not agree.
"The show makes a lot of money, but re-casting a lead is always a challenge," the source explains. "The network could throw in the towel if David can't be signed for more seasons after this one."
Bones' ratings, meanwhile, took a slight hit with a move from Thursdays to Mondays last year. According to the most recent Nielsen TV ratings, it currently sits at fourth in its timeslot with 7.26 million viewers against The Voice on NBC, with 14.12 million viewers, Dancing with the Stars on ABC with 13.1 million, and CBS' How I Met Your Mother, with 7.87 million viewers.
More from RadarOnline
Celebrity Cheaters
Emily Deschanel Promotes Bones At The International TV Festival In Monte Carlo

redpajama_set_name: RedPajamaCommonCrawl


text:
Ryk Brink would love your feedback! Got a few minutes to write a review?
Ladies Close Your Eyes
Ryk Brink 12 stories
'Women in Fridges'
It's cold, he awakes from his dream to the sound of running water. Cool night air brushes his cheek and he opens his eyes to see the bank of a stream leading into a larger river. He seemed to recognise it but couldn't quite place it.
He was sitting on the bank of a stream under an overpass, but he couldn't hear any cars going by. It was a cloudless night with a few stars tossed up into that mess of a sky. The moon was nowhere to be seen.
His back was against concrete. He was under one of the arches, his head felt heavy, it was hard to lift. He realised after some blank staring and heavy blinking that he was in a storm drain not on the bank of a river. He was lying on a raised embankment on the far side under the bridge. It was just cool dull yellow concrete lit by the ambient glow of the night as far as the eye could see. A trickle of a stream flowing under his feet. He saw a few whisks of grass in the distance beyond a chain link fence on the other side of the bridge.
His back felt wet as he leant against the wall. His legs splayed out in front of him in his work clothes, his black shoes covered in a film of light brown dust. His head felt dry and taught and it hurt to move his neck. He sat there for a minute trying to collect himself.
He leaned forward and pulled himself onto his knees. Crawling like a baby over to the small body of water running through the storm drain.
He splashed his face a couple of times and put a cold wet hand down the back of his neck. It felt dirty, the dry sweat made his clothes itch and hang heavy. He felt starched and sickly.
James looked down at his reflection. He looked tired he could taste blood. He bore his teeth, his gums were raw and dirty looking. He sucked his gums and spat a wad of blood into the trickle of water running through the storm drain.
It spread out fast. A brown and deep red viscous liquid hitting the water hard and dispersing as the stream started to pick up.
James stood up, stumbling. His flat shoes scraping away out from under his feet on the slick raised concrete under the overpass. He slipped back down to his knees with a bone jarring jolt. The fall sending questions all over his body, where is all this pain coming from?
The stream started to get faster and thicker and he didn't know why, the sky hadn't changed. Maybe a dam or sluice-gate opened. Were there any dams in California? Was he even still in California? He had to get out of there one way another. His heart started to pound, his mind rushing by trying to find answers to questions it hadn't settled on.
Then a noise.
Plinking and then something larger, a splash and a hollow plonking sound. He walked out from under the overpass and looked up at the bridge. It was well lit with deco lamps lining either side only three or four feet apart. A waist high guard rail along the footpath. There were no cars pulled up along the side of the road, there were no cars going by. He waited thirty seconds but nothing came.
The stream was a black and dark brown like his blood now. Probably some filthy rain water from a storm drain higher up.
He squinted up and down the stream for what broke the water. Then he saw it, it was white which made it easy to pick out against the murk. It bobbed on the surface on the water like a fishing lure. It looked light but also hard and slick reflecting some dull twinge of moonlight from somewhere.
It crept closer to him bobbing in and out playfully. Before he could feel it. He was standing in the now knee high water. He stood unmoving watching it approach, taking shape in front of him. It was long and thin, delicate looking, it's subtle curvature giving way to long thin fingers.
He bent down to pick it up.
It was the left forearm of a female mannequin. He starred at it quizzically, turning it around in his hands trying to discern its origin. He turned it over, there were scratches on the underside. Scratched on to its wrist were the words "SHE HAS DYED HER HAIR RED".
He dropped the arm into the stream and it bobbed off down into the distance.
A torso, legs, hip, arms, hands, and a head, all the pieces, maybe more than one mannequin he couldn't tell. He couldn't know why just yet. They were blank, featureless, pale white parts. Perfect, only for the leaves and the debris that surrounded them in the vile manmade river.
He breathed in and out slow. The chill getting up his back, his shoes squelched full of water and silt, listening to the night music.
The fan beat down with steely wings, his legs exposed, the cool air freezing the sweat on them.
James lay on his back, he felt cold and wet, a thin layer of sweat soaking into the white sheets.
He was alone.
The phone beside the bed was off the hook and making an annoying noise.
He couldn't summon enough thoughts in his head to work out what the noise was. It was just annoying.
He tried to move, his body was like a coffin. It creaked with a frail rigidity.
Pain rushing in from all over, his ribs felt tender and it hurt to breathe too deep.
He tried to sit up and a sharp pain in his neck sent him reeling back into his soggy pillow.
His eyes rolled around in his skull and he felt like he might throw up.
Taking shallow breathes he stared at the fan on the ceiling, waiting for it to stop spinning.
He closed his eyes and tried to centre himself and then he heard that annoying noise again. He turned on his side trying to move his neck as little as possible. He slid towards the edge of the bed and sat up facing the window.
He was home in his own bed; it was night but he couldn't remember how he got home. He put the phone back on the hook and looked at his alarm clock which just flashed four zeroes over and over. It must have come unplugged somehow.
Only moments after putting the phone back into the cradle it started to ring.
James paused, groggy.
He thought it could be work since he couldn't tell what time it was and the nights were getting longer.
He picked up the phone and placed it to his ear, clearing his throat. He paused for a moment waiting for them to say something and then he started to gather up his best phone voice in his head to speak.
"Hello, who is this?"
An exhale of breath was all that followed.
"Happy birthday to you-
Happy birthday to you" A man's voice started to sing. The voice seemed forced and high pitch, in an attempt to conceal who, it was.
"…" The phone disconnected and James was left listening to that same annoying noise.
He put the phone back into the cradle and tried to think it away. He sat for a moment and rubbed his eyes and leant forward on his knees looking out the window. He leaned a little too far and the pain in his neck came back. A rigid jolt of pain pulled him back upright.
The street outside was empty. There was a single street lamp in front of the basketball courts but other than that it was pitch black and still. So still it seemed like a picture. He got a sinking feeling that the night would never end like he was stuck in a videogame. It wouldn't progress until he found something to propel the story and he never would.
He stood up from the bed with a laboured sigh, an almost laugh.
He was just wearing a set of striped loosing fitting boxer shorts and nothing else. He walked and the wind on his legs made him aware of soft spots on his shins. A feeling he remembered from playing soccer. A hobby he'd given up when he stopped having friends outside of work.
He got up not sure what he intended to do. But now he was up the thought of sleep seemed more painful than waking. Fearful that the mugginess would follow him into his dreams. His head felt heavy and swollen. He thought he should be a cliché and get a glass of milk or water or something to reduce the swelling in his brain and tongue.
He paced his bedroom a few times, remembering she wasn't there again. Her spot was empty but the bed had been made since then and her indentation had gone.
Did she leave a note and he forgot, was that her calling, did he dream that? Was it a woman's voice or a man's? What month was it? Was it his birthday today?
Something like that seemed like it could slip his mind. He stopped celebrating his birthday after he turned thirty and all his friends moved away or were working. Bridges don't so much burn as they pull apart or fade away. All his friends from college were unreachable. In their own little worlds of babies and travelling. And jobs that seemed fulfilling from the outside but were probably just as dehumanizing as his. He told himself.
He sighed and crossed the room into the hall past the sitting room on his right into the kitchen at the back of the house. The moon was waiting there, he didn't need to turn on the light, spare his eyes some.
His bare feet on the linoleum was jarring enough.
The fridge was on the wall on the left as he came in. In the breakfast nook of the kitchen overlooking the meagre but neat backyard. The low hum of the fridge reassuring him that it was even on.
He put his hand on the handle. Looking down at himself in the moonlight. He could see what looked like recent scratches, scabs of some sort. He tried to remember where he got them. Or if he'd been to the store to buy food recently. Everything seemed a blur, one-day melting into the other or overlapping completely. Trying to put things in the correct order hurt his head and seemed more or less pointless.
He opened the fridge with a galumphing popping sound. It was a large fridge; a sort of an off-green colour. The realtor described it as "seafoam" or "sea-something". Needless to say he didn't really care but it was something Laura had complained about. It looked old fashion but James' assumed that was the point. A vaguely deco fridge seemed appealing in some small way.
Nothing could have prepared him for the bright glow of the fridge.
The fridge was almost empty. Just a few boxes of leftover Chinese food he couldn't remember how long had been there. A jar of olives, a slice of cold pizza and a clear plastic carafe filled with water in the door.
He stood glazed in front of the fridge for a moment, enjoying the cool buzz on his damp skin.
Returning to the breakfast bar that was almost like a large ironing board covered in Bakelite. It protruded out into the middle of the kitchen with a few wire framed stool chairs scattered around it.
He put down the slice of cold pizza, ham and pineapple. He set the carafe down next to it and turned to his left to root around in the cupboard for a glass.
He found one and poured himself an ice cold glass of water which he drank too fast for his teeth. Without sitting he laid into the cold pizza and it was gone in a few hurried bites. He could already feel it going down to his love handles as he threw the small white plate into the sink.
He poured himself another glass of ice cold water and put the carafe back in the door of the fridge and closed it.
He walked back through his house and into his bedroom, his head feeling a few sizes smaller now. He set the glass of water down on the bedside table closest to the door. Which was her side. He crossed the room to the ensuite bathroom on his left.
The door was open, but that was normal.
He turned the light on, one of those old pull strings that made a double clicking sound. Which he thought was a little unusual in such a new house.
The light came on and filled the small bathroom with warm yellowish light.
It wasn't much to look at, the toilet was on the right a little too close to the wall.
The bath slash shower on the left, the curtain drawn all the way around so it didn't bunch up and mould. The sink was between the two directly opposite the door. A white porcelain hanging sink which stuck out of the wall. A small medicine cabinet above it. The room was all white tile with the occasional seafoam tile to break it up.
He ran the water in the sink and splashed some in his face. It cleared a little more mugginess out of his head. He smiled at himself in the mirror, the water droplets beading off a two-day old stubble. He must have forgotten to shave again.
There was a cut above his right eye he didn't remember getting and then he heard it.
A dripping sound.
The sink was empty and the drops of water falling off his face made muted tapping sounds, this was different.
A definitive plodding sound.
As if large drop of water were falling into a large puddle.
He closed his eyes and took a deep inhale of breath through his nose. He leant on the sink with both hands either side of the bowl. He stepped away from the sink launching himself off the sides of the basin.
His feet made light splashing sounds on the tiled floor. Was there a leak? Was the floor wet when he came in? Did he do that just now? The bathroom was windowless and each splashing noise echoed. The extractor fan made a laboured buzzing sound.
The dripping sound seemed to get louder, keeping a steady beat.
James turned his head to look at the shower curtain, it moved and his heart raced only for a second. The dripping noise was coming from the bath; it must be loose.
He craned forward over the turned out lip of the bath and pulled the curtain back.
There she was.
He must have known she was there all along.
The water rippled with the steady dripping into the rusty brown water.
One coffin white knee poked out from the surface.
She was naked.
One arm, her right, draped over the side of the tub.
Her head was back and to the right, her eyes were open, fixed on a certain tile on the wall. Her mouth was open slightly, the air smelled stale and sweet like a doctor's office. Her eyes glazed over.
Her face frozen into a perfect mask of fleeting still beauty.
She'd never been as beautiful as this and she'd never be ever again.
Before he knew it he was kneeling by the tub. All the strength from his knees had drained and he used the porcelain altar to rest his tired frame. His hands in the water touching her cold body, her skin was still soft but she'd become a monument to herself.
He was so weak now, his body drained and tired. He propelled himself towards her head using the side of the bath and the sheer force of will to touch her face.
There was something in her hand.
He swayed back on his knees and took her small hand in his. His left cupping her hand gently, the other slid up her elbow to turn her palm over.
Her arm so white it didn't look real. Along her wrist was a cut from the top of her elbow leading vertically down her wrist. The wound was dry and clean but deep and mortal.
The cut stopped before the hand and then there were two cuts either side forming a crude 'V' shape.
It was an arrow pointing to her hand.
With her hand cupped in his, he opened her hand.
A matchbox fell on the damp tiled floor.
4. 'Women in Fridges'
1 'Crazy Clown Time'
2 'I Want You'
3 'Strange and Unproductive Thinking'
4 'Women in Fridges'
5 'Hole in the Silk'
6 'Call from the Past'
7 'Sinnerman'
8 'The Rabbit'
9 'White Noiz'
10 'Dance of the Dream Man'
11 'Ashes and Ghosts'
12 'Silent Circus'
13 'Confinement'
14 'You're not here'
15 'A World of Madness'
16 'Until Death'
Death Note Fanfiction
Books Similar to 'The Jungle Book'
Books Similar to 'The Lord of the Rings'
Percy Jackson Fanfiction
Books Similar to 'A Court of Thorns and Roses'
Buffy Fanfiction
Books Similar to 'Dracula'


The artist was out with a friend when she zipped up her hood to cover her face. Amused, he took photos and used them as the basis for a copper etching. As he worked, however, he began seeing the triple image as "a mirror" reflecting his own feelings and his struggle revealing them. "I was thinking about relationships and how difficult I find them—how hard it is to understand other people's thoughts," even when you know them very well.


Thank you to Tiux Compression Socks for sponsoring today's post. I received a free product to review. This post may contain affiliate links.
Compression socks make my long run legs happy.
Hobble up the stairs carrying everything I could possibly need for the rest of the afternoon so I only have to make the trip once.
Drink the protein smoothie that my husband makes and leaves in the fridge for me.
Take a hot bubble/Epsom salt bath.
Put on a t-shirt and compression socks, get into bed, and take a nap.
If I'm really lucky, my husband will keep the kids out of the house all afternoon so that I can sleep, rest, and recover.
A lot of my friends run in their compression socks and sleeves, but I only wear mine for recovery (just a personal preference). There are a lot of benefits to wearing compression socks (click HERE to learn more), but I just love the way they feel on my tired, sore legs.
But compression gear can be cost-prohibitive. Calf sleeves can cost $40+, and over-the-calf socks (my favorites) can go for as much as $70! I don't know about you, but it's hard for me to justify that expense when I'm already spending over $100 on running shoes every few months.
That's the #1 thing that makes Tiux Performance Compression Socks different from other brands – the price. Tiux Compression Socks are $35 and are delivered with free shipping.
Wide top band for comfort.
Achilles tendon protection to prevent blistering and irritation.
"Y" heel for contoured perfect fit.
Padded footbed provides cushion and shock absorption.
Seamless toe for maximum comfort.
Breathable mesh instep to keep your feet cool and dry.
Graduated compression (20-25 mmHg) to increase blood circulation.
Constructed with premium technical fabrics for superior moisture management and breathability.
200 thread count for ultimate durability,comfort and fit.
Left and right anatomical design.
But how do they feel?
I've been fortunate enough to try out a number of different brands of compression gear – some were purchased with my own money, some I won in blog giveaways, and some (like Tiux) I received for free so that I could review them here. With that said, I feel comfortable telling you that Tiux Compression Socks absolutely stand up to their more expensive competition.
The footbed is significantly more cushioned than the other brands that I've tried.
The toe box is wide, but not too wide – just enough so that my feet don't feel squished.
They are designed (and clearly marked) differently for the left and right foot.
The top band is wider than other compression socks. It still fits snugly, but I find it more comfortable – plus they're easier to take on and off.
Really, the only thing that comes to mind is the color – black/gray/green aren't really my thing. BUT I can see on their website that they're coming out with two other color combos – green/black/blue and pink/purple/green. So that takes care of that.
Oh, and before I get to the giveaway, here's one other cool thing about Tiux. They've committed to donating 1% of their revenue to MAG (Mines Advisory Group) – an organization whose mission is to save lives and protect communities from landmines, unexploded ordnance (UXO), and other weapons remaining after conflict.
Tiux is giving away one pair of their Performance Compression Socks. Use the form below to enter. And if you don't want to wait for the giveaway, go HERE to pre-order a pair today!
Stuff you should know before you enter the giveaway —> * This giveaway is open to US residents only. You must be 18+ to enter. Winners will be notified via email and given 48 hours to respond. If the winner does not respond within 48 hours, a new winner may be selected. Mommy Runs It is not responsible for prize fulfillment.
I would love to win these! Love your website!
I would LOVE to win these! I have never tried compresion socks before and would love to start!
I'd love to win these! Compression socks have made a huge difference in my recovery from long runs in the past.
I want to win because I know they can help with my recovery and calf issues. Thank you!
I want to win because I've been having issues with my calves after running, and I think these would really help. Plus they look cool 🙂 Thank you for the wonderful giveaway.
These would be great after my long runs as a train for a marathon!
I'd like to win them for my FIL.
I've had a calf cramp with exercise lately and would love to win these to see if it helps!
I would love to win a pair because I get calf cramps and I have heard these really help!
They look and sound comfortable, and it's awesome that they donate some of their proceeds to such a worthy cause!
I would love to win these socks! I am an avid half marathoner, and for the past 6 months, I have been working on my speed. They sound like a good way to pamper my legs after speedwork.


Welcome to the 2018-19 Water polo season!!!
It is a program in which all club families are expected to volunteer in assisting with club operations and ongoing development. We are a nonprofit organization requiring a wide variety of people to assist in all areas of the club.
Please, get in the habit of doing this promptly after you have volunteered.
When completing the registration for your child your family is assigned a certain number of volunteer points.
You are also asked to send a volunteer commitment cheque (with your other registration money) which will only be cashed by the club if your family does not meet its volunteer commitment by the end of the season.
How does my family earn volunteer points?
Your family (athlete, parents, etc.) can earn points by volunteering to participate in any of the clubs committees, board of directors, minor official, league coordinator, team manager, website/social media assistance and communication roles to name just a few opportunities. Points per role are based on level of leadership and time commitment.
How can I find out about club volunteer opportunities?


text:
Fact Sheet 17 – Emirates SkyCargo
... represented an increase of 12.2 per cent over the 1.4 million tonnes carried the previous year. Cargo revenue contributed 17.2 percent of the airline's total transport revenue. The airline's freight division currently uses cargo hold capacity in Emirates' passenger aircraft, plus eight freighters – ...
NASA`s Space Network Ground Segment Sustainment
... originally installed in the 1960s to support the first NASA spaceflight missions. These old ground terminals 'looked up' at orbiting customer spacecraft as they flew overhead, limiting the contact support time. TDRSs would 'look down' at customers and, given their geosynchronous orbits, each TDRS wo ...
Sunshade protection
Vought Airtrans
LTV's (Vought) Airtrans was an automated people mover system that operated at Dallas-Fort Worth International Airport between 1974 and 2005. The adaptable people mover was utilized for several separate systems: the Airport Train, Employee Train, American Airlines TrAAin and utility service. All systems utilized the same guideways and vehicle base but served different stations to create various routes.After 30 years of service the system's 1970s technology was no longer adequate for the expanding airport's needs, and in 2005 it was replaced by the current Skylink system. While most of the system was auctioned and sold for scrap, some guideways and stations (now closed to the public) remain. Airtrans moved nearly 5 million people in its first year of operation; by the end of its life it had served over 250 million passengers.As the first US installation of a fully automated transit system, Airtrans technology was expected to be deployed in similar mass transit systems around the country. In Japan, the system was licensed by a consortium formed between Niigata Engineering and Sumitomo Corporation for similar deployments there. However, no further systems were constructed. Car #25 was donated to the Frontiers of Flight Museum in Dallas, Texas, and Cars #30 and #82 were donated to North Texas Historic Transportation in Fort Worth, Texas.


text:
Home State Arkansas
Arkansas, Delta Daily News, Local News, Louisiana, Mississippi, State June 8, 2019
Gas Prices Expected to Continue to Fall
THE DELTA (Ben Caxton) — Industry analysts with GasBuddy.com say gas prices will continue to fall this summer, predicting the price at the pump could drop below $2 a gallon. The national average has fallen for four straight weeks and is now $2.81. Concerns about President Trump's tariffs on China…
Arkansas, Delta Daily News, Local News, State June 5, 2019
Crossett to Lose 550 Jobs at Georgia Pacific Plant
CROSSETT, AR (Ben Caxton) — Georgia Pacific announced yesterday that it is shutting down some operations at its Crossett, Arkansas plant. In a press release, the company says permanently shut down the bleached board machines, as well as the extrusion plant, Woodyard, pulp mill and a significant portion of the…
Louisiana Man Dies in Chicot County Wreck
CHICOT COUNTY, AR (Ben Caxton) — A Lousiana man is dead after the Freightliner Semi he was driving hit a culvert just after 6:00 PM Friday evening in Chicot County. Arkansas State Police say, Ronald Bowman, of Delhi, Louisiana, was traveling south on Highway 159, south of Mack Ball Road…
Video Forces Suspension Of Helena-west Helena Officer
HELENA-WEST HELENA, AR (Ben Caxton) — A Helena-West Helena police officer is off the job pending an investigation after body camera video surfaced showing him pointing a gun at a man over Memorial Day weekend. The video shows officer Terry Daughtery approaching a black car, several times asking the man…
All Three Mississippi Teams Notch Tournament Wins
THE DELTA (Ben Caxton) — All three Mississippi teams in the NCAA college baseball tournament notched wins yesterday in their opening games. In Starkville, Mississippi State used a 7th inning rally to take the lead on the way to an 11 to 6 win over Southern. Both Ole Miss and…
Escaped Arkansas Inmates Captured in New Mexico
LITTLE ROCK, AR (Ben Caxton) — Two inmates who escaped from an Arkansas jail have been captured in New Mexico. Authorities say 31-year-old Jason Michael Brown and 47-year-old Geronimo Espericueta were able to escape their cell in a Little Rock jail on Thursday by crawling through a bathroom ceiling. Brown…
Arkansas, Delta Daily News, Local News, State May 29, 2019
Police Investigating Officer Who Pulled Gun
HELENA-WEST HELENA, AR (Ben Caxton) — Police in Helena-West Helena are reviewing body camera footage to see what happened Sunday morning after a man claimed an officer pulled a gun on him for no reason. Edrick Truitt was parked in front of a closed convenience store around 3 AM Sunday…
Arkansas County First in the State to Go Solar
PHILLIPS COUNTY, AR (Ben Caxton) — Phillips County is the first county in Arkansas to go solar, expecting solar energy technology will save taxpayers money. Phillips County is building a solar farm as part of its new criminal justice complex hoping to save about $50,000 a year. Eventually, there will…
Arkansas, Delta Daily News, Local News, Louisiana, Mississippi, State May 27, 2019
Delta Counties Approved for Federal Disaster Assistance
THE DELTA (Ben Caxton) — Coahoma, Leflore, Sunflower and Washington County have all been approved for federal aid to recover from severe weather. They join 20 other Mississippi counties previously approved for recovery aid from February storms that resulted in tornadoes and flooding.
Arkansas Governor Declares a State Of Emergency
LITTLE ROCK, AR (Ben Caxton) — Arkansas Governor Asa Hutchinson declared a state of emergency in the capital on Friday due to record flooding on the Arkansas River. The declaration orders the Arkansas National Guard to send high-water rescue teams to the western part of the state and suspends many…
Delta Daily News, Local News, Mississippi, State October 25, 2018
Mound Bayou Police Looking for Burglary Suspect
Mound Bayou, MS (Ben Caxton) — Mound Bayou Police are looking for a man they say broke into a home and stole a 40″ television set from a bedroom. The burglar gained entry to the residence by throwing a brick through the bedroom window just before 10:00 PM Monday. A…


Most days, I manage to forget just exactly how old I really am. Never mind the fact that I'm always a little bit shocked when I look in the mirror, especially first thing in the morning when I'm not wearing any make up and my face is still puffy and my hair looks like what we used to call a "rat's nest." Or that my trips to the mall tend to focus only on stores that cater to women of a certain age, which means that the clothes they sell are designed for maximum coverage and almost always feature a "control panel" somewhere in the mid section. Or that I can no longer read anything without a pair of really strong reading glasses. Or that I am now routinely offered senior citizen's discounts by clerks who don't look old enough to hold a job. Denial is a wonderful thing, and over the years, I've gotten really, really, good at it.
But every once in a while something comes a long to remind me that my youthful days are now ancient history, and today was one of those days.
My daughter had a birthday today. I knew it was coming, since it lands on the same day every year. I also knew how old she was, since it's not that hard to count to thirty-two. (Although I admit that up until a few days ago, I was under the impression that she was going to turn thirty-one, so I probably shouldn't be bragging on my counting skills.) Yet there's something about knowing that my daughter, whose birth I can remember as if it happened just yesterday, is turning thirty-two that just makes me feel old.
But the more I think about it, the more I realize that what I'm really concerned about isn't the actual number of years I've been on this earth. I'm just trying to avoid behaving the way I have always thought old people did: longing for the "good old days," afraid to try new things, becoming obsessed with my health, and in general, letting the "young" people do all the important stuff and have all the fun. Which, if you think about it, is just plain silly.
People of all ages are still actively engaged in the world around them, working hard to help others and contributing to their communities. People of all ages are still having fun, still pursuing their interests, and still making new friends. I think that the time has come for me to stop being afraid that turning a certain age means I have to somehow let go of the essence of who I really am and how I want to live my life.
Yes, my body isn't as strong as it was and I have far more sags, bags and wrinkles than I would like. But I can live with that. It's just the price I pay for the privilege of having lived for over sixty years, and all that I have experienced and learned in that time. Underneath it all, I'm still me and always will be, no matter what my age. Which means that getting older might not be so bad after all….
Spring has finally arrived, which means it's time to do my annual Spring cleaning. This week I'll pack up the last of my winter clothes and replace them with outfits more appropriate for warmer weather. I'll touch up the paint on the walls and baseboards, wash the windows, vacuum the curtains and even toss my pillows in the washing machine. I'll also clean out the junk drawer and sort through the many boxes of stuff we have stored in our basement in an effort to get rid of anything we no longer use or love. I am not what you would call a "saver," but for some reason Spring is the time when I am especially motivated to get rid of excess stuff.
And this year I've been thinking that maybe it's time I took my Spring cleaning one step further. If I'm willing to get rid of the things in my house that are no longer useful to me, then maybe I should be willing to get rid of some of the things in my life that are no longer useful to me as well. I am nothing if not a creature of habit, but that doesn't mean that all of my habits are worthy of keeping. In fact, I'm quite sure that some of them aren't good for me at all.
Do I really need to start each day by turning on the morning news, knowing that all it usually does it make me me feel depressed, annoyed, or even angry? Can't all that negativity at least wait until after breakfast? And do I really need to sit down at my computer several times a day, checking my emails and Facebook page? Wouldn't that time be better spent doing something that's actually useful, or even relaxing?
Is the Diet Coke that I drink each time I'm walking dogs at the local animal shelter really the best way to quench my thirst, particularly on a hot and humid day? Is it time to make the switch to water, as so many of the other volunteers do, even though I've always bought myself a Diet Coke as a treat when I'm walking dogs? I could go on, but if I listed all of my habits that aren't exactly enhancing my life, I'd end up with a blog post that was at least 5,000 words. Which would be way too long, and way too embarrassing to share. The point is that my house isn't the only thing that could use a bit of "cleaning out" this Spring.
They say old habits die hard, and that's quite true. But I can still choose to leave some of my old habits behind, especially those that are no longer serving me and that may actually be getting in the way of the kind of life I actually want to lead. And if I can manage to get rid of even a few of those habits this year, then that will be the best Spring cleaning I've ever done.
There has always been a part of me that would like to live out in the country, in a big rambling farmhouse surrounded by enough land to keep a few horses, several dogs and whatever other animals I happened to acquire. I enjoy the peaceful beauty of rural areas, and the thought of living closer to nature, with the chance to grow lots of vegetables and maybe even have fresh eggs from my very own chickens is appealing to me. But that's not the life I chose, and it's not the life I am living.
I live in an inner suburb of a large city, on less than a quarter-acre lot, with neighbors close by on three sides. I can't step out my door and go for a nice walk in the country, but I can walk to several stores and restaurants, and my children could walk to their school when they were little. My son, daughter, and mother each live within a twenty minute drive from my home, and my husband and I have many good friends who live close enough to see often. All in all, I am happy with the way things have turned out, and have no plans of moving anytime soon.
I think we all have to make our choices in life, and there are always trade-offs in whatever choice we make. As much as I would enjoy living in that big house in the country, I also enjoy living in a city with all that a big urban area has to offer. Country living is, for me, one of those choices that I think about from time to time and wonder just exactly what my life would be like if I had followed that particular dream. Just like how each time my husband and I visit Sanibel Island, we think, "Wouldn't it be wonderful if we could just live down here?" But then we go home, look around us, and realize that we are content to stay just where we are.
There will always be a part of me that yearns for the country life, and for the island life as well. But I know that not all dreams can be followed, and that we have to choose the ones that are the most important to us. For my nephew and his wife, the dream of farm life was the one worth pursuing, and I'm so glad it worked out for them. (And I hope they don't mind us visiting rather often!) But for me, both the rural life and the island life are simply the tempting roads that I didn't travel on the journey of my life.


There was something about the awards at the 13th Thessaloniki Documentary Festival that made them somewhat anticlimactic. The ceremony held on Saturday night at the Olympian Theater felt as an afterthought to the ten days of screenings, panels and events that preceded it. In many ways, the festival feels more like a showcase for documentary film than a film festival; its eclectic reach and diversity of titles gives it a more flexible function than a traditional festival would. The primary focus is in its programming, an asset best reflected in this year's theme: Images of the 21st Century. The films that made up the festival's impressive slate weren't limited to new or recent releases, with a number of titles outside the retrospective sections dating as far back to 2007.
The ample selection of films gives Thessaloniki's programming a dynamic edge, with specialty sections that explore a multitude of themes dealing with identity, global perspectives, memory, music, human rights, and environmental issues. Also of note was the extensive offering of Greek films, providing local filmmakers a chance to screen their work in a domestic film industry where distribution can be an uphill battle. The business end of the festival isn't only limited to providing opportunities for Greek filmmakers. With a strong and growing presence in its Doc Market, the festival presents a good opportunity for American filmmakers looking for European distribution.
Embracing local audiences has proved to be vital for the festival, which has found important support from its local government despite the financial crisis. "I am a cinema freak, not just a cinema lover," said Thessaloniki Mayor Yiannis Boutaris in an event for selected press and filmmakers. "I see everything from 'Harry Potter' to Almodóvar," confessed the Mayor, reflecting the sort of film culture that both Thessaloniki film festivals have fostered.
The Audience Awards for feature-length films were given to Vikebe Lokkeberg's "Tears of Gaza" in the international section and to the Greek film "Alma Bonita" from directors Vivi Zografou and Alexis Ponce. FIRPESCI awards were given to Greece's "Only the Words Continue" by Kalliopi Legaki and Sophia Tzavella's "Paradise Hotel." Tzavella's doc about a Roma housing compound in Bulgaria was produced by HBO Bulgaria. The American cable network had a strong presence in the festival with screenings of Alexander Nanau's "The World According to Ion B." from HBO Romania and Jennifer Arnold's "A Small Act," a top ten audience favorite at Hot Docs last year.
A number of independent organizations also awarded prizes at this year's festival. ERT3, a Greek public television channel, awarded a prize of €3, 000 along with a broadcast of the winning film, Laetitia Moreau's "A Future Without Oil." The World Wildlife Foundation named Titus Faschina's "Close to Heaven" as the best documentary in the Habitat section and Amnesty International did the same for David Andre's "Everlasting Sorrow, Life After the Death Penalty" in the Human Rights category. Andre's look into the lasting effects of the death penalty also served as the festival's closing night film.


PA "military court" in Hebron sentencing of man the eight of its kind in the past few months.
A Palestinian Authority "military court" in Hebron on Sunday sentenced another Palestinian to death by firing squad on suspicion of "collaboration" with Israel. The 28-year-old man, who used to serve in the PA's elite Presidential Guard, is the eighth Palestinian to receive the death sentence in the past few months. But none of the death verdicts, which require the approval of PA President Mahmoud Abbas, have been carried out. The latest death sentence was issued by a three-judge panel in Hebron after holding 10 sessions to look into the charges against the former security officer. The court was told that the accused, a resident of the Al-Aroub refugee camp north of Hebron, was recruited as an informant for Israel in 1997 while working at a car wash in Gush Etzion. Presiding Judge Ahmed Abu Dayyah said in his verdict that the accused had been found guilty of collaboration with the "enemy." He said the actions of the accused resulted in the killing of a Palestinian gunman and the arrest of others who had sought sanctuary inside the Church of the Nativity during Operation Defensive Shield. The man was also found guilty of passing on information to the Shin Bet that led to the arrest of Adnan Abayat, the former commander of Fatah's armed wing, the Aksa Martyrs Brigades, and his deputy, Rateb Abayat. The two, who operated in the Bethlehem area, were hiding inside a local hospital when they were caught by the IDF and later sentenced to life imprisonment. Defense lawyer Yusef al-Ribie told the court that his client had been tortured during interrogation and called for his immediate release.