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

A set of \emph{sequencing reads} is a massive collection $R = \{R_1,\ldots,R_n \}$ of $n$ overlapping short strings that together encode the sequence of a DNA sample. Analyzing this kind of data allows scientists to uncover complex biological processes that otherwise could not be studied.  There are many ways for extracting information from a set of reads (see \cite{reuter2015high} for review).  However, in most of the cases, the process can be reduced to build a \emph{de Bruijn graph} (dBG) of the collection and then search for graph paths that spell segments of the source DNA (see  ~\cite{bray2016near,iqbal2012novo,salmela2016accurate} for some examples).

Briefly, a dBG is a directed labeled graph that stores the transitions of the substrings of size $k$, or \emph{kmers}, in $R$. Constructing it is relatively simple, and the resulting graph usually uses less space than the input text.  Nevertheless,  this data structure is lossy, so it is not always possible to know if the label of a path matches a substring of the source DNA. The only paths that fulfill this property are those in which all nodes, except the first and last, have indegree and outdegree one~\cite{kececioglu1995comb}. Still, they represent just a fraction of the complete dBG.

More branched parts of the graph are also informative, but traverse them requires extra information to avoid spelling incorrect sequences. A simple solution is to augment the dBG with colors, in other words, we assign a particular color $c_i$ to every string $R_i \in R$, and then we store the same $c_i$ in every edge that represents a kmer of $R_i$. In this way, we can walk over the graph always following the successor node colored with the same color of the current node.

The idea of coloring dBGs was first proposed by Iqbal et al. \cite{iqbal2012novo}. Their data structure, however, contemplated a union dBG built from several string collections, with colors assigned to the collections rather than particular strings. Considering the potential applications of colored dBGs, Boucher et al. \cite{BBGPS15} proposed a succinct version of the data structure of Iqbal et al. In their index, called VARI, the topology of the graph is encoded using $BOSS$~\cite{BOSS12}, and the colors are stored separately from the dBG in a binary matrix $C$, in which the rows represent the kmers and the columns represent the colors. Since the work of Boucher et al., some authors have tried to compress and manipulate $C$ even further; including that of \cite{almodaresi2017rainbowfish}, \cite{pandey2018mantis}, \cite{holley2015bloom}, while others, such as \cite{mustafa2017metannot} and \cite{mustafa2018dynamic} have proposed methods to store compressed and dynamic versions $C$.

An instance of a colored dBG for a single set $R$ can also be encoded using a color matrix. The only difference though is that the number of columns is proportional to the number of sequences in $R$. Assigning a particular color to every sequence is not a problem if the collection is of small or moderated size. However, massive datasets are rather usual in Bioinformatics, so even using a succinct representation of $C$ might not be enough. One way to reduce the number of columns is to reuse colors for those sequences that do not share any kmer in the dBG. Alpanahi et al. \cite{alipanahi2018recoloring} addressed this problem, and showed that it is unlikely that the minimum-size coloring can be approximated in polynomial time.

Alpanahi et al. also proposed a heuristic for recoloring the colored dBG of a set of sequences that, in practice, dramatically reduces the number of colors when $R$ is a set of sequencing reads. Their coloring idea, however, might still produce incorrect sequences, so the applications of their version of the colored dBG are still limited.

\noindent{\bf Our Contributions.}
In this article, we show how to use a colored dBG to store and analyze a collection of sequencing reads succinctly. Similarly to VARI, we use $BOSS$ and the color matrix $C$ to encode the data. However, we reduce the space requirements by partially coloring the dBG and greedily reusing the same colors for different reads when possible. We also propose two algorithms that work on top of the data structure, one for reconstructing the reads directly from the dBG and other for assembling contigs. We believe that these two algorithms can serve as a base to perform Bioinformatics analyses in compressed space. Our experimental results show that on average, the percentage of nodes in $BOSS$  that need to be colored is about 12.4\%, the space usage of the whole index is about half the space of the plain representation of $R$ (1 Byte/DNA symbol), and that more than 99\% of the original reads can be reconstructed from the index.

\section{Preliminaries}\label{sec:pre}

\paragraph{\textbf{{\em DNA strings}}. \rm A DNA sequence $R$ is a string over the alphabet $\Sigma=\{\texttt{a},\texttt{c},\texttt{g},\texttt{t}\}$ (which we map to $[2..5]$), where every symbol represents a particular nucleotide in a DNA molecule. The DNA \emph{complement} is a permutation $\pi[2..\sigma]$ that reorders the symbols in $\Sigma$ exchanging \texttt{a} with \texttt{t} and \texttt{c} with \texttt{g}. The \emph{reverse complement} of $R$, denoted $R^{rc}$, is a string transformation that reverses $R$ and then replaces every symbol $R[i]$ by its complement $\pi(R[i])$. For technical convenience we add to $\Sigma$ the so-called \emph{dummy} symbol \texttt{\$}, which is always mapped to 1.}

\paragraph{\textbf{{\em de Bruijn graph}}. \rm A de Bruijn graph (dBG) \cite{de1946combinatorial} of the string collection $R=\{R_1,\ldots,R_n\}$ is a labeled directed graph $G=(V,E)$ that encodes the transitions between the substrings of size $k$ of $R$, where $k$ is a parameter. Every node $v \in V$ is labeled with a unique $k-1$ substring of $R$. Two nodes $v$ and $u$ are connected by a directed edge $(v,u) \in E$ if the $k-2$ suffix of $v$ overlaps the $k-2$ prefix of $u$ and the $k$-string resulted from the overlap exists as substring in $R$. The label of the edge is the last symbol of the label of node $u$.}

\paragraph{\textbf{{\em Rank and select data structures}}. \rm Given a sequence $B[1..n]$ of elements over the alphabet $\Sigma=[1..\sigma]$, $\texttt{rank}_{b}(B,i)$ with $i \in [1..n]$ and $b\in\Sigma$, returns the number of times the element $b$ occurs in $B[1..i]$, while $\texttt{select}_b(B,i)$ returns the position of the $i$th occurrence of $b$ in $B$. For binary alphabets, $B$ can be represented in $n+o(n)$ bits so that \texttt{rank} and \texttt{select} are solved in constant time~\cite{Cla96}. When $B$ has $m \ll n$ 1s, a compressed representation using $m\lg\frac{n}{m}+\mathcal{O}(m)+o(n)$ bits, still solving the operations in constant time, is of interest~\cite{raman2007}.}

\paragraph{\textbf{{\em BOSS index.}}}The $BOSS$ data structure \cite{BOSS12} is a succinct representation for dBGs based on the \emph{Burrows-Wheeler Transform} ($BWT$)~\cite{BW94}. In this index, the labels of the nodes are regarded as rows in a matrix and sorted in reverse lexicographical order, i.e., strings are read from right to left. Suffixes and prefixes in $R$ of size below $k-1$ are also included in the matrix by padding them with \texttt{\$} symbols in the right size (for suffixes) or the left side (for prefixes). These padded nodes are also called \emph{dummy}. The last column of the matrix is stored as an array $K[1..\sigma]$, with $K[i]$ being the number of labels lexicographically smaller than any other label ending with character $i$. Additionally, the symbols of the outgoing edges of every node are sorted and then stored together in a single array $E$. A bit vector $B[1..|E|]$ is also set to mark the position in $E$ of the first outgoing symbol of each node.
The complete index is thus composed of the vectors $E$, $K$, and $B$. It can be stored in $|E|(\mathcal{H}_{0}(E)+\mathcal{H}_{0}(B))(1+o(1)) + \mathcal{O}(\sigma \log n)$ bits, where $\mathcal{H}_0$ is the zero-order empirical entropy~\cite[Sec~2.3]{navarro2016compact}. This space is reached with a Huffman-shaped Wavelet Tree \cite{MN05} for $E$, a compressed bitmap~\cite{raman2007} for $B$ (as it is usually very dense), and a plain array for $K$.
Bowe et al. \cite{BOSS12} defined the following operations over $BOSS$ to navigate the graph:
\begin{itemize}
    \item \texttt{outdegree$(v)$}: number of outgoing edges of $v$.
    \item \texttt{forward$(v, a)$}: node reached by following an edge from $v$ labeled with $a$.
    \item \texttt{indegree$(v)$}: number of incoming edges of $v$.
    \item \texttt{backward$(v)$}: list of the nodes with an outgoing edge to $v$.
    \item \texttt{nodeLabel$(v)$}: label of node $v$.
\end{itemize}
The first four operations can be answered in $\mathcal{O}(\log\sigma)$ time while the last one takes $\mathcal{O}(k\log\sigma)$ time. For our purposes, we also define the following operations:
\begin{itemize}
    \item \texttt{forward\_r$(v, r)$}: node reached by following the \emph{r-th} outgoing edge of $v$ in lexicographical order.
    \item \texttt{label2Node$(S)$}: identifier in $BOSS$ of the node labeled with the $(k-1)$-string $S$.
\end{itemize}
The function \texttt{forward\_r} is a small variation \texttt{forward}, and it maintains the original time, while the function \texttt{label2Node} is the opposite of \texttt{nodeLabel}, but it also maintain its complexity in $\mathcal{O}(k\log\sigma)$ time.

\paragraph{\textbf{{\em Graph coloring.}}}The problem of coloring a graph $G=(V,E)$ consists of assigning an integer $c(v) \in [1..\omega]$ to each node $v \in V$ such that i) no adjacent nodes have the same color and ii) $\omega$ is minimal. The coloring is \emph{complete} if all the nodes of the graph are assigned with one color, and it is \emph{proper} if constraint i) is met for each node. The chromatic number of a graph $G$, denoted by $\chi(G)$, is the minimum number of colors required to generate a coloring that is complete and proper. A coloring using exactly $\chi(G)$ colors is considered to be optimal. Determining if there is a feasible $\omega$-coloring for $G$ is well known to be NP-complete, while the problem of inferring $\chi(G)$ is NP-hard~\cite{lewis2015guide}.

\paragraph{\textbf{{\em Colored dBG.}}}\label{prem:dbgcol} The first version of the colored dBG \cite{iqbal2012novo} was described as a union graph $G$ built from several dBGs of different string collections. The edges in $G$ that encode the kmers of the \emph{i-th} collection are assigned the color $i$. The compacted version of this graph \cite{BBGPS15} represents the topology of $G$ using the $BOSS$ index and the colors using a binary matrix $C$, where the position $C[i,j]$ is set to true if the kmer represented by the \emph{i-th} edge in the ordering of $BOSS$ is assigned color $j$. The rows of $C$ are then stored using the compressed representation for bit vectors of \cite{raman2007}, or using Elias-Fano encoding \cite{fano1971number,elias1974,okanohara2007practical} if the rows are very sparse. In the single set version of the colored dBG, the colors are assigned to every string. Therefore, the number of columns in $C$ grows with the size of the collection. Alipanahi et al.~\cite{alipanahi2018recoloring} noticed that we could reduce the space of $C$ by using the same colors in those strings that have no common kmers. This new problem was named the \emph{CDBG-recoloring}, and formally stated as follows; given a set $R$ of strings and its dBG $G$, find the minimum number of colors such that i) every string $R_i \in R$ is assigned one color and ii) strings having two or more kmers in common in $G$ cannot have the same color.  Alipanahi et al. \cite{alipanahi2018recoloring} showed that an instance $I(G')$ of the \emph{Graph-Coloring} problem can be reduced in polynomial time to another instance $I'(G)$ of the \emph{CDBG-recoloring} problem. Thus, any algorithm that finds $\chi(G')$, also finds the minimum number of colors for dBG $G$. However, they also proved that the decision version of \emph{CDBG-Recoloring} is NP-complete.

\section{Definitions}

Let $R=\{R_1,R_2,....,R_n\}$ be a collection of $n$ DNA sequencing \emph{reads}, and let $R'=\{R_1,R_1^{rc}..R_n,R_n^{rc}\}$ be a collection of size $2n$ that contains the strings in $R$ along with their DNA reverse complements. The dBG of order $k$ constructed from $R'$ is defined as $G_{R'}^{k}=(V,E)$, and an instance of $BOSS$ for $G_{R'}^{k}$ is denoted as $BOSS(G_{R'}^{k})=(V',E')$, where $V'$ and $E'$ include the dummy nodes and their edges. For simplicity, we will refer to $BOSS(G_{R'}^{k})$ just as $BOSS(G)$. A node in $V'$ is considered an \emph{starting} node if its $k-1$ label is of the form \texttt{\$}$A$, where \texttt{\$} is a dummy symbol and $A$ is a $k-2$ prefix of one or more sequences in $R'$. Equivalently, a node is considered an \emph{ending} node if its $k-1$ label is of the form $A$\texttt{\$}, with \texttt{\$} being a dummy and $A$ being a $k-2$ suffix of one or more sequences in $R'$. Nodes whose labels do not contain dummy symbols are considered \emph{solid}, and solid nodes with at least one predecessor node with outdegree more than one are considered \emph{critical}. For practical reasons, we define two extra functions, \texttt{isStarting} and \texttt{isEnding} that are used to check if a node is starting or ending respectively.

A \emph{walk} $P$ over the dBG of $BOSS(G)$ is a sequence $(v_0,e_0,v_1...v_{t-1},e_t,v_t)$ where $v_0,v_1,...v_{t-1},v_t$ are nodes and $e_1..e_t$ are edges, $e_i$ connecting $v_{i-1}$ with $v_i$. $P$ is a \emph{path} if all the nodes are different, except possibly the first and the last. In such case, $P$ is said to be a \emph{cycle}. A sequence $R_i \in R$ is \emph{unambiguous} if there is a path in $BOSS(G)$ whose label matches the sequence of $R_i$ and if no pair of colored nodes in $(u,v) \in P$ share a predecessor node $v' \in P$. In any other case, $R_i$ is \emph{ambiguous}. Finally, the path $P_i$ that spells the sequence of $R_i$ is said to be \emph{safe} if every one of its branching nodes has only one successor colored with the color of $R_i$.

We assume that $R$ is a \emph{factor-free} set, i.e., no $R_i \in R$ is also a substring of another sequence $R_j$, with $i\neq j$.

\section{Coloring a dBG of reads}

In this section, we define a coloring scheme for $BOSS(G)$ that generates a more succinct color matrix, and that allows us to reconstruct and assemble unambiguous sequences of $R'$. We use the dBG of $R'$ because most of the Bioinformatic analyses require the inspection of the reverse complements of the reads.
Unlike previous works, the rows in $C$ represent the nodes in $BOSS(G)$ instead of the edges.

\paragraph{\textbf{{\em A partial coloring.}}}\label{sec:col_sch}
We make $C$ more sparse by coloring only those nodes in the graph that are \emph{strictly} necessary for reconstructing the sequences. We formalize this idea with the following lemma:

\begin{lemma}\label{lem:col}
For the path of an unambiguous sequence $R_i \in R'$ to be safe we have to color the starting node $s_i$ that encodes the $k-2$ prefix of $R_i$, the ending node $e_i$ that encodes the $k-2$ suffix of $R_i$ and the critical nodes in the path.
\end{lemma}

\begin{proof}
We start a walk from $s_i$ using the following rules: (i) if the current node $v$ in the walk has outdegree one, then we follow its only outgoing edge, (ii) if $v$ is a branching node, i.e., it has outdegree more than one, then we inspect its successor nodes and follow the one colored with the same color of $s_i$ and (iii) if $v$ is equal to $e_i$, then we stop the traversal.\qed
\end{proof}

Note that the successor nodes of a branching node are critical by definition, so they are always colored. On the other hand, nodes with outdegree one do not require a color inspection because they have only one possible way out.

Coloring the nodes $s_i$ and $e_i$ for every $R_i$ is necessary; otherwise, it would be difficult to know when a path starts or ends. Consider, for example, using the solid nodes that represent the $k-1$ prefix and the $k-1$ suffix of $R_i$ as starting and ending points respectively. It might happen that the starting point of $R_i$ can also be a critical point of another sequence $R_j$. If we start a reconstruction from $s_i$ and pick the color of $R_j$, then we will generate an incomplete sequence. A similar argument can be used for ending nodes. The concepts associated with our coloring idea are depicted in Figures~\ref{fig:col_diag}A and \ref{fig:col_diag}B.

\paragraph{\textbf{{\em Unsafe coloring.}}}\label{sec:unreco} As explained in Section~\ref{prem:dbgcol}, we can use the recoloring idea of \cite{alipanahi2018recoloring} to reduce the number of columns in $C$. Still, using the same colors for unrelated strings is not safe for reconstructing unambiguous sequences.

\begin{lemma}\label{lem:unco}
Using the same color $c$ for two unambiguous sequences $R_i,R_j \in R'$ that do not share any $k-1$ substring might produce an unsafe path for $R_i$ or $R_j$.
\end{lemma}

\begin{proof}
Assume there is another pair of sequences $R_x, R_y \in R'$ that do not share any $k-1$ subsequence either, to which we assign them color $c'$. Suppose that the paths of $R_x$ and $R_j$ crosses the paths of $R_i$ and $R_j$ such that the resulting dBG topology resembles a grid. In other words, if $R_i$ has the edge $(u,u')$ and $R_j$ has the edge $(v,v')$, then $R_x$ has the edge $(u,v)$ and $R_y$ has the edge $(u',v')$. In this scenario, $v$ will have two successors, node $v'$ from the path of $R_j$ and some other node $v''$ from the path of $R_x$. Both $v'$ and $v''$ are critical by definition so they will be colored with $c$ and $c'$ respectively. The problem is that node $v'$ is also a critical node for $R_y$, so it will also have color $c'$. The reason is that $u'$, a node that precedes $v'$, appears in $R_i$ and $R_y$. As a consequence, the path of $R_x$ is no longer safe because one of its nodes ($v$ in this example) has to successors colored with $c'$. A similar argument can be made for $R_i$ and color $c$. Figure \ref{fig:unsafe_col} depicts the idea of this proof.
\qed \end{proof}

When spurious edges connect paths of unrelated sequences that are assigned the same color (as the in the proof of Lemma~\ref{lem:unco}), we can generate chimeric strings if, by error, we follow one of those edges. In the algorithm, we solve this problem by assigning different colors to those strings with sporadic edges, even if they do not share any $k-1$ substring.

\begin{figure}[!t]
\centering
\includegraphics[width=0.8\linewidth]{figures/unsafe_coloring.pdf}
\caption{Example of unsafe paths produced by a graph recoloring. (A) The dBG generated from the unambiguous sequences $R_i$, $R_j$, $R_x$ and $R_y$. Every texture represents the path of a specific string. (B) Recolored dBG. Sequences $R_i$ and $R_j$ are assigned the same color $c$ (light gray) as they do not share any $k-1$ substring. Similarly, sequences $R_x$ and $R_y$ are assigned another color $c'$ (horizontal lines) as they do not share any $k-1$ sequence neither. Nodes $u,u',v,v'$ and $v''$ are those mentioned in the Proof of Lemma ~\ref{lem:unco}. The sequences of $R_i$ and $R_x$ cannot be reconstructed as their paths become unsafe after the recoloring.}
\label{fig:unsafe_col}
\end{figure}

\paragraph{\textbf{{\em Safer and greedy coloring.}}}\label{sec:greedycol} Our greedy coloring algorithm starts by marking in a bitmap $N=[1..|V'|]$ the $p$ nodes of $BOSS(G)$ that need to be colored (starting, ending and critical). After that, we create an array $M$ of $p$ entries. Every $M[j]$ with $j \in [1..p]$ will contain a dynamic vector that stores the colors of the \emph{j-th} colored node in the $BOSS$ ordering. We also add $\texttt{rank}_1$ support to $N$ to map a node $v \in V$ to its array of colors in $M$. Thus, its position can be inferred as $\texttt{rank}_1(N,v)$.

The only inputs we need for the algorithm are $N$, $R'$ and $BOSS(G)$. For every $R_i \in R'$ we proceed as follows; we append a dummy symbol at the ends of the string, and then use the function \texttt{label2Node} to find the node $v$ labeled with the $k-1$ prefix of $R_i$. Note that this prefix will map a starting node as we append dummies to $R_i$. From $v$, we begin a walk on the graph and follow the edges whose symbols match the characters in the suffix $R_i[k..|R_i|]$. Note now that the last node $v'$ we visit in this walk is an ending node that maps the $k-1$ suffix of $R_i$. As we move through the edges, we store in an array $W_i$ the starting, ending, and critical nodes associated with $R_i$. Additionally, we push into another array $I_i$ the neighbor nodes of the walk that need to be inspected to assign a color to $R_i$. The rules for pushing elements into $I_i$ are as follows; i) if $v$ is a node in the path of $R_i$ with outdegree more than one, then we push all its successor nodes into $I_i$, ii) if $v$ is a node in the path of $R_i$ with indegree more than one, then we visit every predecessor node $v'$ of $v$, and if $v'$ has outdegree more than one, then we push into $I_i$ the successor nodes of $v'$. Once we finish the traversal, we create a hash map $H_i$ and fill it with the colors that were previously assigned to the nodes in $I_i$ and $W_i$. After that, we pick the smallest color $c'$ that is not in the keys of $H_i$, and push it to every array $M[\texttt{rank}_1(N,j)]$ with $j \in W_i$. After we process all the sequences in $R'$, the final set of colors is represented by the values in $M$. The whole processing of coloring a $R_i$ is described in detail by the procedure \texttt{greedyCol} in Pseudocode~\ref{alg:gc}.

The construction of the sets $W_i$ and $I_i$ is independent for every string in $R'$, so it can be done in parallel. However, the construction of the hash map $H_i$ and the assignment of the color $c'$ to the elements of $W_i$ has to be performed sequentially as all the sequences in $R'$ need concurrent access to $M$.
\begin{figure}[!t]
\centering
\includegraphics[width=0.9\linewidth]{figures/coloring_diagram}
\caption{Succinct colored dBG. (A) The topology of the graph. Colors and textures represent the paths that spell the input sequences of the dBG. Numbers over the nodes are their identifiers. Nodes 4,1,6 and 10 are starting nodes (darker borders). Nodes 11,13 and 12 are ending nodes and nodes 3,9,11 and 5 are critical. (B) Our greedy coloring algorithm. (C) The binary matrix $C$ that encodes the colors of Figure B. The left side is $C$ in its uncompressed form and the right side is our succinct version of $C$ using the arrays $N$,$M'$, and $F$.}
\label{fig:col_diag}
\end{figure}

\paragraph{\textbf{{\em Ambiguous sequences.}}}\label{sec:ambseqs} Our scheme, however, cannot safely retrieve sequences that are ambiguous.

\begin{lemma}
Ambiguous sequences of $R'$ cannot be reconstructed safely from the color matrix $C$ and $BOSS(G)$.
\end{lemma}

\begin{proof}
Assume that collection $R$ is composed just by one string $R_1=XbXc$, where $X$ is a repeated substring and $b,c$ are two different symbols in $\Sigma$. Consider also that the kmer size for $BOSS(G)$ is $k=|X|+1$. The instance of $BOSS(G)$ will have a node $v$ labeled with $X$, with two outgoing edges, whose symbols are $b$ and $c$. Given our coloring scheme, the successor nodes of $v$ will be both colored with the same color. As a consequence, if during a walk we reach node $v$, then we will get stuck because there is not enough information to decide which is the correct edge to follow (both successor nodes have the same color).\qed
\end{proof}

A sequence $R_i$ will be ambiguous if it has the same $k-1$ pattern in two different contexts. Another case in which $R_i$ is ambiguous is when a spurious edge connects an uncolored node of $R_i$ with two or more critical nodes in the same path. Note that unlike unambiguous sequences with spurious edges, an ambiguous sequence will always be encoded by an unsafe path, regardless of the recoloring algorithm. In general, the number of ambiguous sequences will depend on the value we use for $k$.

\section{Compressing the colored dBG}\label{sec:colrep}

The pair $(M,N)$ can be regarded as a compact representation of $C$, where the empty rows were discarded. Every $M[i]$, with $i\in [1..|M|]$, is a row with at least one value, and every color $M[i][j]$, with $j \in [1..|M[i]|]$, is a column. However, $M$ is not succinct enough to make it practical. We are still using a computer word for every color of $M$. Besides, we need $|M|$ extra words to store the pointers for the lists in $M$.

We compress $M$ by using an idea similar to the one implemented in $BOSS$ to store the edges of the dBG. The first step is to sort the colors of every list $M[i]$. Because the greedy coloring generates a set of unique colors for every node, each $M[i]$ becomes an array of strictly increasing elements after the sorting. Thus, instead of storing the values explicitly, we encode them as deltas, i.e., $M[i][j]=M[i][j]-M[i][j-1]$. After transforming $M$, we concatenate all its values into one single list $M'$ and create a bit map $F=[1..|M'|]$ to mark the first element of every $M[i]$ in $M'$. We store $M'$ using Elias-Fano encoding \cite{elias1974,fano1971number} and $F$ using the compressed representation for bit maps of \cite{raman2007}. Finally, we add $\texttt{select}_1$ support to $F$ to map a range of elements in $M'$ to an array in $M$. The complete representation of the color matrix now becomes $C = N + F + M'$ (see Figure \ref{fig:col_diag}C). The complete index of the colored dBG is thus composed of our version of $C$ and $BOSS(G)$. We now formalize the idea of retrieving the colors of a node from the succinct representation of $C$.

\begin{itemize}
    \item \texttt{getColors}$(v)$: list of colors assigned to node $v$.
\end{itemize}

\begin{theorem} the function  {\rm \tt getColors}$(v)$ computes in $\mathcal{O}(c)$ time the $c$ colors assigned to node $v$.
\end{theorem}

\begin{proof}
We first compute the rank $r$ of node $v$ within the colored nodes. This operation is carried out with $r=\texttt{rank}_1(N,v)$. After retrieving $r$, we obtain the range $[i..j]$ in $M'$ where the values of $v$ lie. For this purpose, we perform two $\texttt{select}_1$ operations over $F$, $[i,j]=(\texttt{select}_1(F,r),\texttt{select}_1(F,r+1)-1)$. Finally, we scan the range $[i..j]$ in $M'$, and as we read the values, we incrementally reconstruct the colors from the deltas. All the \texttt{rank} and \texttt{select} operations takes $\mathcal{O}(1)$, and reading the $c=j-i+1$ entries from $M'$ takes $\mathcal{O}(c)$, because retrieving an element from an Elias-Fano-encoded array also takes $\mathcal{O}(1)$. In conclusion, computing the colors of $v$ takes $\mathcal{O}(c)$.\qed
\end{proof}

\section{Algorithms for the colored dBG}
\paragraph{\textbf{{\em Reconstructing unambiguous sequences.}}}\label{sec:trav_graph} We describe now an online algorithm that works on top of our index and that reconstructs all the unambiguous sequences in $R'$. We cannot tell, however, if a reconstructed string $R_i$ was present in the original set $R$ or if it was its reverse complement $R_{i}^{rc}$. This is not really a problem, because a sequence and its reverse complement are equivalent in most of the Bioinformatic analyses.

The algorithm receives as input a starting node $v$. It first computes an array $A$ with the colors assigned to $v$ using the function \texttt{getColors} (see Section~\ref{sec:colrep}), and then sets a string $S=\texttt{nodeLabel}(v)$. For every color $a \in A$, the algorithm performs the following steps; initializes two temporary variables, an integer $v'=v$ and string $S'=S$, and then begins a graph walk from $v'$. If the outdegree of $v'$ is one, then the next node in the walk is the successor node $v'=\texttt{outgoing\_r}(v',1)$. On the other hand, if the outdegree of $v'$ is more than one, then the algorithm inspects all the successor nodes of $v'$ to check which one of them is the node $v''$ colored with $a$. If there is only one such $v''$, then it sets $v'=v''$. This procedure continues until $v'$ becomes an ending node. During the walk, the edge symbols are pushed into $S'$. When an ending node is reached, the algorithm reports $S'[1..|S'|-1]$ as the reconstructed sequence.

If at some point during a walk, the algorithm reaches a node with outdegree more than one, and with more than one successor colored with $a$, then aborts the reconstruction of the string as the path is unsafe for color $a$. Then, it returns to $v$ and continues with the next sequence. The complete procedure is detailed in the function \texttt{buildSeqs} of Algorithm~\ref{alg:bs}.

\paragraph{\textbf{{\em Assembling contigs.}}} Our coloring scheme for the dBG allows us to report sequences that represent the overlap of two or more strings of $R'$. There are several ways in which a set of sequences can be arranged such that they form valid overlaps, but in practice, we are not interested in all such combinations. What we want is to compute only those union strings that describe real segments of the underlying genome of $R'$, a.k.a \emph{contig} sequences. In this work we do not go deep into the complexities of contig assembly  (see \cite{kececioglu1995comb,medvedev2007computability,idury1995new,medvedev2011paired} for some review). Instead, we propose a simple heuristic, that work on top of our index, and that it is aimed to produce contigs that are longer than those produced by uncolored dBGs.

Similar to \texttt{buildSeqs}, this method traverses the graph to reconstruct the contigs. During the process, it uses the color information to weight the outgoing edges \emph{on the fly}, and thus, inferring which is the most probable path that matches a real segment of the source DNA.

The algorithm receives as input a starting node $v$ and initializes a set $L$ and hash map $Q$. Both data structures are used to store information about the strings that belong to the contig of $v$. A read $R_i \in R'$ is identified in the index as a pair $(c,v')$, where $c$ is a color assigned to $R_i$ and $v'$ is the starting node of its path. $L$ contains the reads already traversed while $Q$ contains the active reads. The algorithm also initializes a string $S=\texttt{nodeLabel}(v)$ and pushes every pair $Q[c_i]=v$ with $c_i \in \texttt{getColor}(v)$. After that, it begins a walk from $v$ and pushes into $S$ the symbols of the edges it visits. For every new node $v'$ reached during the walk, the algorithm checks if one of its predecessor nodes, say $u$, is a starting node. If so, then for every $c_i \in \texttt{getColors}(u)$ sets $Q[c_i]=u$ if $(c_i,u)$ does not exist in $L$. On the other hand, if one of the successors of $v'$, say $u'$, is an ending node, then for every $c_i \in \texttt{getColors}(u')$ sets $L[(c,Q[c_i])]$ and then removes the entry $Q[c_i]$. After updating $Q$ and $L$, it selects one of the outgoing edges of $v'$ to continue the walk. For this purpose, the algorithm uses the following rules; (i) if $v'$ has outdegree one, then it takes its only outgoing edge, (ii) if $v'$ has outdegree more than one, then it inspects how the colors in $Q$ distribute among the successors of $v'$. If there is only one successor node of $v'$, say $v''$, colored with at least $x$ fraction of the colors of $Q$, where $x$ is a parameter, then the algorithm follows $v''$, and removes from $Q$ the colors of the other successor nodes of $v'$.

The algorithm will stop if; (i) there is no such $v''$ that meet the $x$ threshold, (ii) there is more than one successor of $v'$ with the same color or (iii) $v'$ has outdegree one, but the successor node is an ending node. After finishing the walk, the substring $S[2..|S|]$ is reported as the contig. The procedure \texttt{contigAssm} in Pseudocode~\ref{alg:ca} describes in detail the contig assembly algorithm, and a graphical example is shown in Figure~\ref{fig:ctg_assm}.

\begin{figure}[!t]
\centering
\includegraphics[width=\linewidth]{figures/contig_assm.pdf}
\caption{Example of the assembly of a contig using our index. (A) Inexact overlap of four sequences. The circle to the left of every string represents its color in the dBG. Light gray symbols are mismatches in the overlap. (B) The colored dBG of the sequences. Circles with darker borders are starting and ending nodes. Light gray values over the starting nodes are their identifiers. The contig assembly begins in node 5 (denoted with a dashed arrow) and the threshold $x$ to continue the extension is set to 0.5. The state of the hash map $Q$ when the walk reaches a branching node (dashed circles) is depicted below the graph. The assembly ends in the right-most branching node as it has not a successor node that contains at least 50\% of the colors in $Q$. The final contig is shown as a light grey path over the graph, and its sequence is stored in $S$.}
\label{fig:ctg_assm}
\end{figure}

\section{Experiments}

We use a set of reads generated from the E.coli genome\footnote{http://spades.bioinf.spbau.ru/spades\_test\_datasets/ecoli\_mc} to test the ideas described in this article. The raw file was in \texttt{FASTQ} format and contained 14,214,324 reads of 100 characters long each. We preprocessed the file by removing sequencing errors using the tool of~\cite{bankevich2012spades}, and discarding reads with \texttt{N} symbols. The preprocessing yielded a data set of 8,655,214 reads (a \texttt{FASTQ} file of 2GB). Additionally, we discarded sequencing qualities and the identifiers of the reads as they are not considered in our data structure. From the resulting set $R$ (a text file of 833.67 MB), we created another set $R'$ that considers the elements in $R$ and their reverse complements.

Our version of the colored dBG, the algorithm for greedy coloring and the algorithms for reconstructing and assembly reads were implemented in \texttt{C++}\footnote{https://bitbucket.org/DiegoDiazDominguez/colored\_bos/src/master}, on top of the \texttt{SDSL-lite} library~\cite{gbmp2014sea}. In our implementation, arrays $M'$ and $F$ are precomputed beforehand to store the colors directly to them, because using the dynamic list $M$ is not cache-friendly. Additionally, all our code, except the algorithm for contig assembly, can be executed using multiple threads.

We built six instances of our index using $R'$ as input. We choose different values for $k$, from 25 to 50 in steps of five. The coloring of every one of these instances was carried out using eight threads. Statistics about the graph topologies are shown in Table \ref{tab:dbg}, and statistics about the coloring process are shown in Table 2. In every instance, we reconstructed the unambiguous reads (see  Table \ref{tab:color}). Additionally, we generated an FM-index of $R'$ to locate the reconstructed reads and check that they were real sequences.  All the tests were carried out on a machine with Debian 4.9, 252 GB of RAM and processor Intel(R) Xeon(R) Silver @ 2.10GHz, with 32 cores.

\section{Results}

The average compression rate achieved by our index is 1.89, meaning that, in all the cases, the data structure used about half the space of the plain representation of the reads (see Table~\ref{tab:dbg}). We also note that the smaller the value for $k$, the greater the size of the index. This behavior is expected as the dBG becomes denser when we decrease $k$. Thus, we have to store a higher number of colors per node.

\begin{table}[!htb]
\caption{Statistics about the different colored dBGs generated in the experiments. The index size is expressed in MB and considers the space of $BOSS(G)$ plus the space of our succinct version of $C$. The compression rate was calculated as the space of the plain representation of the reads (833.67 MB) divided by the index size.}
\label{tab:dbg}
\centering
\begin{tabular}{c|c|c|c|c|c}
\toprule
\textbf{k}&\textbf{Total number}&\textbf{Number of}  &\textbf{Number of}&\textbf{Index}    &\textbf{Compression} \\
          &\textbf{of nodes}    &\textbf{solid nodes}&\textbf{edges}    &\textbf{size}&\textbf{rate} \\
\midrule
25 & 106,028,714 & 11,257,781 & 120,610,151 & 446.38 & 1.86 \\
30 & 142,591,410 & 11,425,646 & 157,186,548 & 443.82 & 1.87 \\
35 & 179,167,289 & 11,561,630 & 193,773,251 & 441.18 & 1.88 \\
40 & 215,751,326 & 11,667,364 & 230,365,635 & 438.23 & 1.90 \\
45 & 252,337,929 & 11,743,320 & 266,958,709 & 435.30 & 1.91 \\
50 & 288,925,674 & 11,791,640 & 303,552,318 & 432.13 & 1.92 \\
\bottomrule
\end{tabular}
\end{table}

The number of colors of every instance is several orders of magnitude smaller than the number of reads, being $k=25$ the instance with more colors (6552) and $k=50$ the instance with the fewest (1689). Even though the fraction of colored nodes in every instance is small, the percentage of the index space used by the color matrix is still high (~73\% on average). Regarding the time for coloring the graph, it seems to be reasonable for practical purposes if we use several threads. In fact, building, filling and compacting $C$ took 5,015 seconds on average, and the value decreases if we increment $k$. The working space, however, is still considerable. We had memory peaks ranging from 3.03 GB to 4.3 GB, depending on the value for $k$ (see Table~\ref{tab:color}).

The process of reconstructing the reads yielded a small number of ambiguous sequences in all the instances (2,760 sequences on average), and decreases with higher values of $k$, especially for values above 40 (see Table~\ref{tab:color}).

\begin{table}[ht]
\centering
\caption{Statistics about our greedy coloring algorithm.  The column "Color space usage" refers to the percentage of the index space used by our succinct version of $C$. Elapsed time and memory peak are expressed in seconds and MB, respectively, and both consider only the process of building, filling, and compacting the color matrix.}
\label{tab:color}
\begin{tabular}{c|c|c|c|c|c|c}
\toprule
\textbf{k}&\textbf{Number of}    &\textbf{Number of}&\textbf{Color space}&\textbf{Ambiguous}&\textbf{Elapsed}&\textbf{Memory}\\
          &\textbf{colored nodes}&\textbf{colors}   &\textbf{usage}      &\textbf{sequences}&\textbf{Time}&\textbf{peak}\\
\midrule
25 & 21,882,874 & 6,552 & 83.03 & 1904 &5,835 & 4,391\\
30 & 21,907,324 & 4,944 & 79.14 & 1502 &5,551 & 4,119\\
35 & 21,926,687 & 2,924 & 75.27 & 1224 &5,131 & 3,847\\
40 & 21,942,083 & 2,064 & 71.40 & 1054 &4,872 & 3,575\\
45 & 21,954,138 & 1,888 & 67.51 & 714 &4,507 & 3,303\\
50 & 21,964,947 & 1,689 & 63.58 & 176 &4,199 & 3,030\\
\bottomrule
\end{tabular}
\end{table}

\section{Conclusions and further work}

Experimental results shows our data structure is succinct, and that has a practical use. Still, we believe that a more careful algorithm for constructing the index is still necessary to reduce the memory peaks during the coloring. Further compaction of the color matrix can be achieved by using more elaborated compression techniques. However, this extra compression can increase the construction time of the colored dBG and produce a considerable slow down in the algorithms that work on top of it for extracting information from the reads. Comparison of our results with other similar data structures is difficult for the moment. Most of the indexes based on colored dBGs were not designed to handle huge sets of colors like ours and the greedy recoloring of \cite{alipanahi2018recoloring} does not scale well and needs extra information for reconstructing the reads. Still, it is a promising approach that, with further work, can be used in the future as a base for performing Bioinformatics analyses in compressed space.

\bibliographystyle{splncs04}

redpajama_set_name: RedPajamaArXiv


Designing your baby's nursery? From traditional to modern and contemporary, discover your nursery style now. Once you've picked a look, it's time to add the first (and most important) item to your nursery: a cot! Whether you select a cot, bassinet, Moses basket, or co-sleeper, you're going to need a place for your newborn to sleep. At Baby Village, our nursery furniture has been selected with the highest quality and value in mind. Next, choose from linen and manchester made from 100% organic cotton and waterproof mattresses, dressers and changers, Gliders and Ottomans and more. Then top things off with fun nursery decor, baby blankets and pillows!


Custom booklets are a good useful method to convey information for any purpose such as ceremony, comic book, or as a information package for a business product. Here at Copiesmart we have high quality digital printing as well as publication services where orders will see non standard sizes. We provide high quality, fast, and reliable service that can be reached from anywhere in the Greater Vancouver Area.
When it comes to high quality and fast turnaround printing look no further than Copiesmart for digital booklet printing. We are able to print high quality letter size booklets as well as 5.5" x 8.5" with different paper quality.
A booklet is also known as saddle stitch binding. This consists of either a 11"x17" paper or 8.5"x11" paper being folded in the middle and stapled with two staples to make it into a booklet. Digital printing is a quicker format to produce quantities of less than 500 books in a span of 24 hours.
When it comes to non standard sizes of booklets Copiesmart needs to rely on offset printing to have your job completed. In offset printing different sizes and orientation is possible because every page is printed on a large sheet of paper that is later cut and folded and stapled into the desired format. Sizes can range from 4" x 4" up to 11" x 11" or above. The pages will be printed on a full colour CMYK colour palate machine with very high quality.
These printing can be achieved on a variety of paper selection with different finishes and also there can be spot UV added on the covers or inside pages.
All of the services provided by Copiesmart can be accessed anywhere in the Greater Vancouver Area.


Unable to preach, Eugene continued to do the "announcements" .To understand what this means we need to look at the role of a "master of ceremonies" or of a television "anchor person" – it is the person who kept the whole mission together and gave it a unity of direction.
They are kind enough to accept the little that I give. I hold on to the announcements which, in conscience, can only be given by myself. They are so attentive, the silence they keep is so great, that they hear me everywhere although I speak in a low voice.
As for the announcements, they are indispensable; they have more effect than all the rest… So I hope you will leave me free to give them and all the more because, given the situation, it seems necessary. Yesterday evening I abstained from giving them and they were displeased. You know I twine things together somewhat. This way of going into matters has pleased them extraordinarily here. Do not think I preen myself because of it. I am affected only by the grief of seeing myself unable to do more.
Eugene's suffering due to his ill health had brought a lot of blessing and positive energy to the whole team in the success of the mission.
I went back and read the entries from 2010 and I really like what you are saying here Frank. Having done weaving of large wall hangings I know what it is like to bring ideas, colours and textures together into a beautiful piece of work. No one colour or type of wool alone was able to convey what everything did together.
The conductor of the symphony is much the same, as is the facilitator of a workshop or a retreat master. Eugene had the passion, the vision and the wisdom to often see things as they are and discern what was needed. I have not looked at him in quite this light so closely or perhaps so deeply. I see for sure that it was not a case of one man thinking he could do it much better than anyone else and so had to do it all (remembering the checks and balances of yesterday) – but rather a case of one man having the vision and the wisdom and being able to as you put it weave it all together. We could (and do) learn from him.
And I am beginning to see very clearly how all of these posts, even though written separately, really do come together, they are woven into an overall image of how Eugene lived, how the Oblates live and how we can all live. Thank you Eugene and thank you Frank.


text:
Greg Mueller of Webster Groves Recognized for 30 years of Distinguished Service.
Greg Mueller has today been recognized for 30 years of distinguished service. Mueller has shared his reflections and advice in an interview which took place at his office in Webster Groves, MO. Further information can be found at http://www.injurylawstl.com/
- December 14, 2018 /PressCable/ —
This year, Greg Mueller is being recognized for 30 years of distinguished service as a personal injury attorney in Webster Groves, and 20 years of distinguished services at his own personal injury firm, the Mueller Law Practice, LLC. This recognition is a result of 3 decades of dedicated, professional, and accomplished legal work on behalf of personal injury law and personal injury victims.
Since 1999, Greg Mueller from Webster Groves has only represented injury victims. Twenty years ago, he founded his own personal injury law firm dedicated to serving injury and accident victims. He is the managing partner and lead trial attorney with 30 years of litigation experience practicing exclusively in personal injury law. "Thirty years in any profession is an accomplishment, but particularly in the law, for Webster Groves-based attorney Greg Mueller and his contributions to the legal profession and his clients will be long remembered," said former defense attorney Robert Hayes.
In a recent one-to-one interview, Mueller noted past achievements, which helped build momentum towards the present day. Notably, one of the proudest was Mr. Mueller is receiving the highest rating for ethics and legal ability from the attorneys and judges with whom her work. Webster Groves attorney Greg Mueller has an "AV Rating," which is the highest rating for legal ability and ethical practices. It is the highest rating available for any attorney according to the most respected, nationwide attorney rating system. "I have held the highest rating for legal ability and ethical practices – continuously for 25 years. That is an accomplishment and record to be proud of."
Greg Mueller, a native of Webster Groves, has been involved with the personal injury law and workers compensation litigation for 30 years. He began his legal career as an appellate judicial law clerk at the Missouri Court of Appeals. Early in his career, he worked as a defense trial lawyer at a large insurance defense law firm, defending insurance companies, automobile and truck drivers, physicians, nursing homes, and hospitals. But since 1999, Greg Mueller has dedicated his professional legal career to representing injury and accident victims against insurance companies. He seeks to remain the top personal injury firm in Webster Groves, MO, and the greater St. Louis area.
Reflecting on this recognition Mueller attributes his success to the team around him: "The attorneys at the Mueller Law Practice have over 80 years of combined personal injury litigation experience. We are well versed in every aspect of personal injury, from the moment of an accident, to litigation, trial, and a successful appeal, if necessary."
In the same interview, Mueller stated the intentions for the future. The primary goal for the next 12 months, Mueller states, will be to achieve continued success for my clients. The aim is to remain as one of the top personal injury firms in Webster Groves, MO, as well as the greater St. Louis area.
When asked more personally about how they want to be perceived and remembered, Mueller said: "Behind every case is a person with a family in crisis. We don't just settle cases; we solve problems for people and their families. We are an excellent, professional law firm, smaller in size, dedicated to the individual accident victim, but with the skill and decades of successful results of a larger law firm."
Mueller closed the interview by sharing a recommendation for anybody who wanted to follow in Mueller's footsteps in some fashion, perhaps taking the achievements even further. According to Greg Mueller, a Webster Groves Attorney, the key is "getting up early and working hard every day with the focused and dedicated purpose to zealously advocate for those injured persons and their families to the best of my legal and personal ability."
Further information available at
http://www.injurylawstl.com/

redpajama_set_name: RedPajamaCommonCrawl


text:
Film Review – Bigfoot: The Lost Coast Tapes
November 29th, 2012 | POSTED BY Chad Eng
Some people like movies where the "monster" is shown, and some people like it when the suspense and action put images in your head that could never be adequately visualized on film (sadly, fans of computer generated imaging don't believe in the latter). Bigfoot: The Lost Coast Tapes is an independent film from Steve Barker, shot as a documentary. This film doesn't show the monster, and supports that decision by providing plenty of suspense and hints to keep the viewer stuck to their seat. Despite the running, yelling, and flashes of …something… in the woods, the film is surprisingly well put together and competent.
Sean is shooting a documentary on the Lost Coast in Northern California—an area of the Northwest with the most Sasquatch sightings in the country. He's tracking down Bigfoot. He brings his small crew (including his ex-girlfriend) to find the man who claims he's found a dead body of Bigfoot. Sean is paying this mountain man, Drybeck, a lot of money to interview him and spend some time filming in his secure compound deep in the woods.
During the initial interview with Drybeck, the crew is interrupted by noises in the woods. Drybeck rushes some of them inside as the generator is destroyed, but the film crew is there to get to the bottom of this legend/hoax. Sean is convinced it is Drybeck's associate playing tricks on them, but their confidence begins to erode a little bit, especially when Drybeck abandons them. The crew has some good footage to this point, but should they risk continuing the shoot, or should they try to get to safety and abandon the project?
The film is really well shot, even for a handheld-heavy "making of a documentary" film, with impressive suspense moments, especially considering there isn't any music soundtrack to help. The parts are played pretty well by the actors, even though Drybeck is a little bit over the top at times. They play him up as being an eccentric to cover the fact that he's a little flashy with his lines. There are plenty of self camera shots with screaming and blood, but I didn't get motion sick like I did with The Blair Witch Project. It is a much better production and story than that early handheld "real-life" film. Yes, you'll have to suspend belief in a few instances, and yes you'll see a few things coming plot-wise, but overall, the film is worth watching, especially if you're into the legend of Bigfoot at all.
Ashley Wood, Bigfoot, Corey Grant, Drew Rausch, Frank Ashmore, Noah Weisberg, Rich McDonald, Sasquatch
About Chad Eng
I'm a cross between Taylor Swift and Danzig, with a small dose of Christpher Burke thrown in. I like fried foods wrapped in bacon and I collect B-movies and kung-fu films. I host a regularly-occuring Bad Movie Night for 20-30 of my closest friends—jealous, aren't you?
Follow him on Twitter or email him.
CinemaCon Film Review – The Heat
You Make the Pick – Football Movies
Top 5 – Acts of Redemption
Film Review – The Host
Film Review – A Good Day to Die Hard
Edward Davidson
Allen Almachar
Benjamin Nason
Adelaide Blair
Cassidy Robinson


This fabulous chair was designed by Adrian Pearsall, a leader in mid century modern design. We found it in a basement and--before we knew anything about Pearsall--were taken by its exquisite construction, generous proportions and swooping lines. The frame was in great shape but the upholstery was in tatters and the foam had fossilized. It has been completely reupholstered from the frame up. The fabric is a cotton velvet in celedon. Also features tapered wood legs with ball casters. This chair is generous enough for you and your significant other, bff, or favorite pet. Makes a statement but lovely to sit in too.


While some people seem to think article writing is simple, those who actually do it for a living know that this isn't the case. A great article writer has their own methods, styles, and ideas that help them to write great articles. Most importantly, they're aware of the types of articles that audiences want to read and the styles that publications, whether printed or digital, wish to present.
Novice article writers often seek out hard and fast rules in order to write articles that they hope will be perceived as high quality. However, there really aren't any hard and fast rules for article writers, which is a difficult lesson to learn. While many an editor, client, and representative may insist that there is only one correct way to write an article, the experienced writer soon learns that this one "right way" varies enormously from client to client. The best thing a new writer can do is to review articles which the client prefers or has already published and take note of some basic qualities.
Point of view is often a hotly contested issue in article writing. Formal articles quite often require a third-person, impersonal point of view. That is, the author should avoid using "I" or addressing the reader either specifically or in general in a direct manner. However, many other publications, editors, and clients prefer a less formal style. In fact, they may find the formal style to be too cold, inaccessible, or uninteresting. As a result, it's best not to assume one way or the other.
Another issue which many clients and publications can be specific about is that of tense. Some prefer most, if not all, of the article to be written in a more technically correct past tense. Others, however, prefer the immediacy of the present tense. In either case, it's best to be consistent in your use of tense. This may not mean using the same tense over the course of the entire article, but it does mean using the tense consistently when dealing with the same type of information.
Finally, many editors have a strong preference for using active voice. This is the one situation in which writers can usually assume that active voice is preferred. If the client has no preference, and the writer knows this, they can revert to passive voice when necessary to improve flow.


text:
ASCE Home
Future City Showcases Brilliant Young Minds Already Innovating
BY Ben Walpole
DiscoverEengineers weekFuture CityFuture City CompetitionPre-College Outreach
ASCE President Norma Jean Mattei, back right, joins the winning team from Austin (TX) West Ridge Middle School at the Future City Competition finals.
The annual Future City engineering competition attracts and colorfully presents great hypothetical concepts as imagined by teams of middle school students.
This year, though, the batch of finalists was so strong, there's a good chance elements of these hypothetical cities will be found in our real future cities someday.
"These kids just astound me – the poise they have in answering our questions," said ASCE 2017 President Norma Jean Mattei, Ph.D., P.E., F.SEI, F.ASCE, who served as one of five judges at the finals in Washington, DC.
"The teams came up with what a future city needs, and some of the ideas that they had we may actually use. They really did their research. Some of the ideas they put together in such a way that they're unique. So we might see these things actually happen in the cities of tomorrow."
Celebrating its 25th anniversary this year as one of DiscoverE's signature Engineers Week events, Future City challenges teams of sixth-, seventh-, and eighth-grade students to research and develop a model city throughout the school year. More than 40,000 students took part around the world.
Many ASCE members serve as team mentors or regional coordinators. Don Wittmer, P.E., M.ASCE, is a regional coordinator in Chicago and, this year, oversaw all of the judging at the national competition.
The West Ridge Middle School team included an ASCE logo on one of its prize-winning model buildings.
"It's great to see the students' excitement and enthusiasm," Wittmer said. "And these kids are smart, beyond compare. If you hear some of the presentations they do, in answering the questions – the judges all yesterday, I was talking to them, they were all amazed at the students. It's amazing what they can do."
Each team designs a virtual city using SimCity, writes an essay, completes a project plan, builds a scale model of their city, and creates a short – often highly entertaining – presentation highlighting their city's key innovations. This year's theme was the Power of Public Space.
West Ridge Middle School in Austin, TX, came in first with its "Sociecity," featuring an array of public spaces. Its Future City model included plenty of moving parts such as a mechanized transportation system and fountain – even an ASCE logo on one of the buildings.
"We talked about what a public space was, what you kind of want in a public space, and we all started brainstorming ideas," said Hunter Samra, one of the team's three finals presenters.
Emma Tyler, another presenter added, "We also started bringing in recycled materials and thinking what each one could be in our city, in our model. And then from there, we decided what our public spaces should be."
Members of the West Ridge Middle School team react after learning that they'd earned first place in the Future City Competition finals.
"And we also started real early with a bunch of prototypes of all of our moving parts and we really worked hard on that first," said Tiffany Samra, rounding out the winning trio.
Two years ago, the Samra siblings' older brother was a presenter for a West Ridge team that finished second at that Future City finals, so there is a bit of a dynasty in the works.
Carol Reese is the team's teacher, while Nick Samsa is the professional engineering mentor. "We're just absolutely thrilled," Reese said.
Oakwood Middle School, of Canton, OH, won the ASCE-sponsored special award for Most Innovative Design of Infrastructure Systems.
Learn more about Future City and how you can get involved.
ASCE Members 'Invent Amazing' During #EWeek2019
Engineers Week 2017: Dreaming Big and Inspiring Students
#EWeek2018 Inspires Wonder
Civil Engineers, Congress Build Bridge to Span Gender Gap
Name: — required *
Email: — required *
Careers & Leadership
Promote the Profession
Save America's Infrastructure
Founded in 1852, the American Society of Civil Engineers (ASCE) represents more than 150,000 members worldwide and is America's oldest national engineering society.


text:
CloudBees Releases Another Industry First: Feature Flagging for On-Premise Use
Software delivery leader adds feature release control capability across environments, sets vision for integrated feature flagging within the software development lifecycle
SAN JOSE, CA. – May 5, 2020 – CloudBees, Inc. , the enterprise software delivery company, today announced a new release of CloudBees Feature Flags that enables developers to manage production deployments of new functionality in a controlled manner with an on-premise feature manager. The new offering strengthens CloudBees' leadership in the continuous integration/continuous delivery (CI/CD) space by extending users' ability to leverage feature flag technology in both on-premise and cloud environments. CloudBees Feature Flags is from the company and application formerly known as Rollout, acquired last year by CloudBees .
Feature flags have emerged as popular tools for deploying new features with the added advantage of enabling risk-free experimentation and fast results. As organizations enhance applications with rich new capabilities, many use feature flags to preview features for select audiences, with the ability to pull them back quickly if the functionality is not successful. In a recent survey , 97% of respondents say that it is important for their organization to implement new application features quickly, yet 65% say it is difficult for their organization to do so safely. CloudBees Feature Flags enables developers to easily release new features with confidence, reduce risk in doing so and manage large numbers of feature flags at scale.
"Very soon, all features will be released behind a feature flag. It's a natural evolution in continuous delivery. CloudBees has led the way in feature flag technology, making it a core part of our overall offering," said Sacha Labourey, CEO and co-founder, CloudBees. "With this release, we are providing the same functionality for on-premise environments that previously had only been available as a cloud-based service. We are committed to the ongoing integration, automation and governance of feature flags within the software delivery lifecycle and giving users choice in selecting the best environment for their project – on-premise or cloud."
CloudBees Feature Flags integrates with the company's deep CI/CD capabilities, giving organizations the most comprehensive feature management capabilities in the software development life cycle (SDLC). The ability to use feature flagging in an on-premise environment also opens up new avenues for usage in industries, such as government, finance, pharmaceuticals, utilities and healthcare, where there can be a mix of on-premise and cloud environments.
"We recognize that many companies are realizing the benefits of feature flags," said Moritz Plassnig, senior vice president and general manager, Software Delivery Management and Software Delivery Automation Cloud at CloudBees. "By flagging features, they no longer have to sacrifice innovation to lower risk. We felt that it was critical to offer this technology to any company working in on-premise or hybrid environments."
Read the blog about the new CloudBees Feature Flags functionality
Learn more about CloudBees Feature Flags
Sign up for the Preview Program
Read The Ultimate Guide to Feature Flags whitepaper
Download the Build vs. Buy eBook
Learn more about Software Delivery Management
About CloudBees
CloudBees, the enterprise software delivery company, provides the industry's leading DevOps technology platform. CloudBees enables developers to focus on what they do best: Build stuff that matters, while providing peace of mind to management with powerful risk mitigation, compliance and governance tools. Used by 50% of the Fortune 100, CloudBees is helping thousands of companies harness the power of continuous everything and gets them on the fastest path from great idea, to great software, to amazing customer experiences, to being a business that changes lives.
Backed by Matrix Partners, Lightspeed Venture Partners, Verizon Ventures, Delta-v Capital, Golub Capital and Unusual Ventures, CloudBees was founded in 2010 by former JBoss CTO Sacha Labourey and an elite team of continuous integration, continuous delivery and DevOps professionals. Follow CloudBees on Twitter , Facebook and LinkedIn .
Sydney Holmquist
PAN Communications
cloudbees@pancomm.com


Anyone who looked over the nominees for Monday night's Genie Awards would have noticed a significant title missing from the list of Canada's best films from 2007: Juno.
Here was an Academy Award-nominated movie shot in Vancouver by a Canadian director, a Canadian crew and with two Canadians among the lead actors, and not a single nomination. The $6.5-million comedy about a pregnant teen, played by Ellen Page, has been one of the year's box-office successes.
The Hollywood Reporter, a Los Angeles trade publication, certainly noticed. On Thursday, it ran a story on the oversight, blaming the Genie rule book -- particularly rules pertaining to film financing -- as the reason Juno was snubbed. Because the film was financed in the U.S. by Los Angeles-based Mandate Pictures and released by mini-major U.S. studio Fox Searchlight, with no Canadian funds put into the film, it failed to meet the Genie standards of what constitutes a Canadian feature film.
The story quoted Montreal-born Juno director Jason Reitman complaining about his film not making the cut, while Eastern Promises -- a co-production shot in England with an international cast and directed by Canadian David Cronenberg -- received 12 Genie nominations.
"It's a Canadian director, Canadian stars, Canadian cast, Canadian crew, shot in Canada," Reitman said at a pre-Oscars lunch at the Canadian Consulate in Los Angeles last week. "How are we not eligible for a Genie when David Cronenberg's film about Russians living in London shot in England with a British crew and British cast is eligible? I'm sorry, but somebody is going to have to explain that to me."
Well, someone from the Genies has an explanation for Reitman: Juno was never submitted to the Genies for consideration.
"The production company did not enter Juno into the competition," said Chris McDowall, spokesman for the Academy of Canadian Cinema & Television and the Genie Awards, which will be presented Monday at the Metro Toronto Convention Centre.
"The Academy didn't even have a chance to evaluate it for its Canadian eligibility, because they did not receive the submission," said McDowall, adding that he wasn't sure if Juno would have qualified had it been submitted.
"Financing is one of the [rules] criteria, but it's not everything," said McDowall.
In a statement, Academy CEO Sara Morton confirmed Juno was never submitted for Genie consideration, adding that "in order to be eligible for the Genies, a film must be Canadian as defined by CAVCO and the CRTC."
A check with the Canadian Audio-Visual Certification Office (CAVCO) failed to turn up the specific financing rules.
Candice Grabois, director of marketing and publicity for Mandate Pictures, said she could not comment on the controversy.
A call to Fox Searchlight Picture's publicity department was not returned by deadline.
The Hollywood Reporter story stated that Eastern Promises met the financing criteria because the Canadian co-producer, Toronto's Serendipity Point Films, raised 20 per cent of the budget in Canada.


text:
Community Directory Get Involved
Conferences Webinars
Certified Relocation Professional Certification Global Mobility Specialist Certification Learning Portal
Research Surveys & Benchmarking
Benchmarking Database Career Portal Forms Portal Learning Portal Tax & Legal Mastersource Mobility Magazine
The Future of Remote Work is here! Take our quick survey to participate now.
Final call to make your voice heard on Remote Internship practices for the industry.
New DOL and DHS Rules Aim to Restrict H-1B Visas
Eric House -
Published in: Government Affairs
Newly released rules from the U.S. Department of Labor and the U.S. Department of Homeland Security aim to make changes to the H-1B program that will make hiring these foreign national workers more difficult for companies.
Effective today, 8 October, a newly released Department of Labor (DOL) interim final rule (IFR) would require employers to increase what they pay H-1B beneficiaries. Administration officials have argued that the H-1B visa program has been taken advantage of to the detriment of U.S.-born workers. These wage increases will make it difficult for companies to hire high-skilled foreign nationals that fill critical roles in the U.S.
Under the DOL H-1B wage rule, that is effective immediately, employers must pay H-1B recipients the higher of the prevailing wage as determined by a formula set forth in the IFR, or the actual wage the employer pays its non-H-1B holders who hold a similar position. The new prevailing wage levels will be significantly higher than current prevailing wage levels due to changes in the formula under the rule. The specific increases in new prevailing wages depend on several factors including the profession and where in the U.S. the position is located. The IFR does outline four wage levels in which the percentiles of the surveyed wages, as determined by the Bureau of Labor Statistics, used to determine prevailing wages has increased from the 17, 34, 50 and 67th percentiles to the 45, 62, 78 and 95th percentiles of average wages. The prevailing wage has therefore been significantly increased for each wage level.
Additionally today, the Department of Homeland Security (DHS) announced an interim final rule (IFR, that aims to strengthen the H-1B nonimmigrant visa program to guarantee that only qualified H-1B petitions are approved. However, these restrictions will also make it more difficult for employers, in particular those providing services, to hire high-skilled foreign nationals.
According to the DHS, "The H-1B program was intended to allow employers to fill gaps in their workforce and remain competitive in the global economy, however it has now expanded far beyond that, often to the detriment of U.S. workers." Thus, the rule aims to avoid an influx of low-cost H-1B workers that, according to the DHS, leads to the stagnation of wages in certain industries.
According to the DHS press release, the rule will narrow the definition of "specialty occupation," require companies to close hiring loopholes and only make "real" offers to "real employees," and strengthen the DHS's compliance enforcement abilities through worksite inspections conducted through the entire H-1B petition process. The DHS rules are slated to go into effect in 60 days, however an IFR functions to expedite the time it takes to instate such rules.
How This Impacts Mobility
The hiring of foreign nationals in the U.S. forms one of the many bedrocks to workforce mobility. These new rules would severely restrict companies' ability to hire high-skilled foreign talent by imposing additional criteria and raising the wage of H-1B applicants. Companies are in a difficult position as they may be required to pay foreign national workers more than their U.S. workers in order to fill key positions. Should any member have questions regarding this development, please reach out to Vice President, Member Engagement and Public Policy Rebecca Peters, rpeters@worldwideercorg.
Join us at this year's Global Workforce Symposium, a month-long, virtual event that features informative and engaging content tracks that are directly relevant to all our industry sectors. That includes our Government Affairs Forums on 11/4 and 11/5, which cover public policy topics ranging from global, immigration and tax to real estate and compliance. Plus, there will be dynamic speakers, robust concurrent educational sessions and workshops, an extensive marketplace and exhibition hall, innovation labs and networking opportunities and events. There's something for everyone at the industry's biggest annual gathering, so don't miss the Virtual Worldwide ERC® Global Workforce Symposium from 28 October through 20 November 2020. Register now!
You might also enjoy reading:
CDC to Require Negative COVID Test Results for All U...
Beginning 26 January, airline passengers from any foreign country planning to travel to the U.S. must provide a negat...
U.S. Internal Revenue Service Issues Mileage Rates f...
On 22 December 2020, the United States Internal Revenue Service (IRS) provided new optional standard mileage rates fo...
New Restrictive H-1B Rules Finalized
Two new H-1B rules that would make hiring foreign nationals more difficult have been finalized.
Real Data. Targeted Program Benchmarking
Benchmark your entire program with real data, filtered to your needs, using our first-of-its-kind, cloud based, interactive benchmarking platform.
Safe workforce mobility is happening!
Worldwide ERC®'s framework for safe and successful workforce mobility now and post-COVID-19 will help you plan.
Get in Touch with Mobility Experts on the Front Lines
Finding the mobility professionals you need all over the world just got easier with our new, user-friendly Directory
In The Current Issue of Mobility Magazine
The top 10 things to keep in mind as we enter a new era for global mobility
How to embrace AI-based tech to enhance diversity and inclusion
The potential for strategic AI and big data to transform mobility
Mobility is Worldwide ERC®'s monthly magazine, delivering industry and business news and updates, as well as insights on global talent mobility programs, tips and trends.
Subscribe Preview
THE WORKFORCE MOBILITY ASSOCIATION SM
Advertising Opportunities Foundation
Sign In (Account)
Relocation Appraiser Resources
Copyright © 2019, Worldwide ERC® All rights reserved
Privacy Policy | Copyright Complaints


text:
Q: Parser takes only first character from the filename and says "File not found" I know it's very difficult to understand my issue, but I'll try my best to explain.
So I've cloned a repository from Github and working on it.
When I run the program without any arguments, it works fine
python main.py --audio works fine.
But when I try to pass my own file, it shows an error.
python main.py --audio myaudio.wav shows an error saying "FileNotFoundError: [Errno 2] No such file or directory: '<File Path/m'"
Notice how it only takes the first character from my argument?
In the code, for default mode, it's something like:
(args.py)parser.add_argument('--audio', default=['default_audio.wav'], type=list) and it works fine.
So naturally, I tried to add '[]' to my file name
python main.py --audio [myaudio.wav] Shows an error too which says "FileNotFoundError: [Errno 2] No such file or directory: '<File Path/['"
See, here it took only the first character of my provided argument i.e. '['
And the file IS there. No spelling mistakes in file name either.
Any help would be very much appreciated.

redpajama_set_name: RedPajamaStackExchange


text:
Q: Merge a column based on 2nd column I have file looking like this:
pw1jc5ssyt6hx618,254343
ysezaratlycpuggl,254333
pht92h4adr3mrbz3,254343
hguvgstqxu3gowfg,254344
gqjp2rsjmk1a2v9c,254333
twdzyi2ddbnrfknd,254333
gcmj7krrx5x6nf8r,254341
tpqorqbyrg1nmm7s,254333
alnac47rt8d4ege3,254343

I want to merge this file based on 2nd column, with - as a delimiter, so that the result looks like this:
254343,pw1jc5ssyt6hx618-pht92h4adr3mrbz3-alnac47rt8d4ege3
254333,ysezaratlycpuggl-gqjp2rsjmk1a2v9c-twdzyi2ddbnrfknd-tpqorqbyrg1nmm7s
254344,hguvgstqxu3gowfg
254341,gcmj7krrx5x6nf8r

A: awk is your friend
$ cat 299360
ipw1jc5ssyt6hx618,254343
ysezaratlycpuggl,254333
pht92h4adr3mrbz3,254343
hguvgstqxu3gowfg,254344
gqjp2rsjmk1a2v9c,254333
twdzyi2ddbnrfknd,254333
gcmj7krrx5x6nf8r,254341
tpqorqbyrg1nmm7s,254333
alnac47rt8d4ege3,254343
$ awk -v FS="," '/^$/{next} # for empty line go to next record
                {if(NR==1){ # checking for first record
                f2[$2]=$1;next} # Adding $1 to array f2 at index $2
                else{
                if($2 in f2){ # Check if $2 is already an index in f2
                f2[$2]=f2[$2]"-"$1;next #appending "-$1" to current value
                }
                else{
                f2[$2]=$1;next
                }
                }}
                END{ # This line will be processed at the end
                for(i in f2){  # for all the indexes i in f2
                printf "%s,%s\n",i,f2[i] #printing in the desired format
                }
                }
                ' 299360
254341,gcmj7krrx5x6nf8r
254333,ysezaratlycpuggl-gqjp2rsjmk1a2v9c-twdzyi2ddbnrfknd-tpqorqbyrg1nmm7s
254343,pw1jc5ssyt6hx618-pht92h4adr3mrbz3-alnac47rt8d4ege3
254344,hguvgstqxu3gowfg

Explanation

*

*FS="," – FS is awk's built-in variable that stands for field separator. Setting field separator to , will set , as the delimiter.

*You access fields by $1, $2 and so on.

*The awk script is enclosed in single quotes;
i.e., 'awk-script-goes-here'

*NR is an awk built-in variable that stands for record number (the number of the record currently being processed). By default, each line is a record.

*By f2[$2]=$1  we are setting up an associative array f2 with field2 (i.e., $2) as the index.

*$2 in f2 checks if the index is already present in the array.

*The if-else and printf are self explanatory.

*The END block in awk is executed only at the very end; i.e., after all the records have been processed.

*for(i in f2) is a for loop construct used to parse the associative arrays in awk. It is the other way of saying, for every index i in f2 do something

*Note that the above for loop may not print the array in an order. You may use the sort bash command to sort the array, though.

*next goes to the next record without processing the commands that follow.

*The /pattern/ checks for a pattern in awk; the pattern ^$ checks for empty line.

Reference
If you wish to get expert in awk, Effective awk Programming is a must read.
Ugly one-liner
awk -v FS="," '/^$/{next}{if(NR==1){f2[$2]=$1;next}else{if($2 in f2){f2[$2]=f2[$2]"-"$1;next}else{f2[$2]=$1;next}}}END{for(i in f2){printf "%s,%s\n",i,f2[i]}}' 299360

Note: Ideally, it's not a good idea to hard-code newlines in awk scripts, as in printf "%s,%s\n",i,f2[i]. You may replace it with printf "%s,%s\n",i,f2[i];print for extra portability.

A: With GNU datamash:
datamash -t, -s -g 2 collapse 1 <data.txt | sed 's/,/-/2g'

Result:
254333,ysezaratlycpuggl-gqjp2rsjmk1a2v9c-twdzyi2ddbnrfknd-tpqorqbyrg1nmm7s
254341,gcmj7krrx5x6nf8r
254343,pw1jc5ssyt6hx618-pht92h4adr3mrbz3-alnac47rt8d4ege3
254344,hguvgstqxu3gowfg

A: In perl:
#! /usr/bin/perl

use strict;
my %mergecol = ();

while(<>) {
  s/#.*//;            # strip comments
  next if (m/^\s*$/); # skip empty lines
  chomp;
  my ($val,$key) = split ',';
  push @{ $mergecol{$key} }, $val;
};

foreach my $k (keys %mergecol) {
  printf "%s,%s\n", $k, join('-', @{ $mergecol{$k} } );
}

The while loop reads the input and creates a Hash-of-Arrays (HoA) structure - an associative array where each element is an array (aka "list").  The keys to the hash are the second field, while the elements of each list are the first fields of lines with the same second field.
At the end of the script, the HoA is printed out one line per record, with the key name, a comma, and then the elements joined with a -.
run as:
$ ./rock.pl rock.txt
254341,gcmj7krrx5x6nf8r
254333,ysezaratlycpuggl-gqjp2rsjmk1a2v9c-twdzyi2ddbnrfknd-tpqorqbyrg1nmm7s
254344,hguvgstqxu3gowfg
254343,pw1jc5ssyt6hx618-pht92h4adr3mrbz3-alnac47rt8d4ege3

Or shortened and embedded in a shell command or script as a "one-liner":
$ perl -n -e '
    s/#.*//;
    next if (m/^\s*$/);
    chomp; ($v,$k)=split ","; push @{ $mc{$k} }, $v;
    END {
     foreach $k (keys %mc) { printf "%s,%s\n", $k, join("-",@{$mc{$k}}) }
    }' rock.txt

Or
$ perl -e 'while(<>) {s/#.*//;next if (m/^\s*$/);chomp;($v,$k)=split ",";push @{$mc{$k}}, $v};
    foreach $k (keys %mc) {printf "%s,%s\n",$k,join("-",@{$mc{$k}})}' rock.txt

Note that a hash or associative array is inherently unordered, if you want sorted output, either pipe into sort or use (sort keys %f) on the foreach my $k lines above.

A: Building on sjsam's answer, but simpler:
awk -v FS="," '
    {
            f2[$2] = f2[$2] "-" $1   # append "-" and $1 to the current value
    }
    END {   # This code will be processed at the end
            for (i in f2) {  # for all the indexes i in f2
                             # (i.e., each unique value from column 2)
                             # print one line in the desired format
                printf "%s,%s\n", i, gensub("-", "", 1, f2[i])
            }
    }
'

This simple-mindedly builds strings that look like this:
   -       pw1jc5ssyt6hx618      -       pht92h4adr3mrbz3      -       alnac47rt8d4ege3
(hyphen)       (value)        (hyphen)       (value)        (hyphen)       (value)
(but without the spaces; they're just for illumination).
Then, when it comes time to print the data, it removes the first -
using the general substitution function, gensub().  Unfortunately,
this isn't supported in the POSIX specification for awk;
it requires GNU Awk.
Alternatively, you could change gensub("-", "", 1, f2[i])
to substr(f2[i], 2) and get the substring of f2[i]
from the second character to the end
(i.e., all but the first character, which is -),
in a POSIX-compliant way.
This will (attempt to) process every line in the input.
If there are some lines in the input that should be ignored
(e.g., blank lines), you could change the first part to
    /./ {
            f2[$2] = f2[$2] "-" $1   # …
    }

or
    NF==2 {
            f2[$2] = f2[$2] "-" $1   # …
    }

When I run sjsam's answer or my own, I get
254333,ysezaratlycpuggl-gqjp2rsjmk1a2v9c-twdzyi2ddbnrfknd-tpqorqbyrg1nmm7s
254341,gcmj7krrx5x6nf8r
254343,pw1jc5ssyt6hx618-pht92h4adr3mrbz3-alnac47rt8d4ege3
254344,hguvgstqxu3gowfg

i.e., sorted by the value of the column 2 key.
You show the desired output
in order of first appearance of the column 2 key in the input.
If that's important to you, try:
awk -v FS="," '
    {
            if (! ($2 in f2)) appearance[++x] = $2
            f2[$2] = f2[$2] "-" $1   # append "-" and $1 to the current value
    }
    END {   # This code will be processed at the end
            for (ix in appearance) {
                             # for all the indexes i in f2
                             # (i.e., each unique value from column 2)
                             # print one line in the desired format
                i = appearance[ix]
                printf "%s,%s\n", i, gensub("-", "", 1, f2[i])
            }
    }
'

which uses the appearance array to keep track of the order of appearance.

A: With two-dimensional arrays found in GNU awk
awk -F, '{
  a[$2][$1]
  }
  END{
    for (i in a) {
      c=0; printf "%s,", i;
        for (j in a[i]) {
          ++c; printf "%s%s", j, length(a[i]) == c? "\n": "-"
          }
     }
   }' file