MOTIVATION: Deep sequencing based ribosome footprint profiling can provide novel insights into the regulatory mechanisms of protein translation. However, the observed ribosome profile is fundamentally confounded by transcriptional activity. In order to decipher principles of translation regulation, tools that can reliably detect changes in translation efficiency in case-control studies are needed. RESULTS: We present a statistical framework and an analysis tool, RiboDiff, to detect genes with changes in translation efficiency across experimental treatments. RiboDiff uses generalized linear models to estimate the over-dispersion of RNA-Seq and ribosome profiling measurements separately, and performs a statistical test for differential translation efficiency using both mRNA abundance and ribosome occupancy. AVAILABILITY AND IMPLEMENTATION: RiboDiff webpage http://bioweb.me/ribodiff Source code including scripts for preprocessing the FASTQ data are available at http://github.com/ratschlab/ribodiff CONTACTS: [email protected] or [email protected] information: Supplementary data are available at Bioinformatics online.

An $L(2,1)$-labeling of a graph G is a function f from the vertex set $V(G)$ to the set of all nonnegative integers such that $| f(x) - f(y) | \geq 2$ if $d(x,y) = 1$ and $| f(x) - f(y) | \geq 1$ if $d(x,y) = 2$. The $L(2,1)$-labeling number $\lambda (G)$ of G is the smallest number k such that G has an $L(2,1)$-labeling with $\max\{ f(v ):v \in V(G) \} = k$. In this paper, we give exact formulas of $\lambda (G \cup H)$ and $\lambda (G + H)$. We also prove that $\lambda (G) \leq \Delta ^2 + \Delta $ for any graph G of maximum degree $\Delta $. For odd-sun-free (OSF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq 2\Delta + 1$. For sun-free (SF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq \Delta + 2\chi (G) - 2$. Finally, we present a polynomial time algorithm to determine $\lambda (T)$ for a tree T.

The profile minimization problem is to find a one-to-one function f from the vertex set $V(G)$ of a graph G to the set of all positive integers such that $\sum _{x \in V(G)} \{ f(x) - \min _{y \in N[x]} f(y)\} $ is as small as possible, where $N[x] = \{ x\} \cup \{ y:y{\text{ is adjacent }}x \} $ is the closed neighborhood of x in G. This paper gives an $O(n^{1.722} )$ time algorithm for the problem in a tree of n vertices.