BACKGROUND
sequencing genomes is one of the most fundamental problems in modern biology and has immense impact on biomedical research.
de novo sequencing is computationally more challenging when compared to sequencing with a reference genome.
on the other hand the existing sequencing technology is not mature enough to identify/read the entire sequence of the genome - especially for complex organisms like the mammals.
however small fragments of the genome can be read with acceptable accuracy.
the shotgun sequencing employed in many sequencing projects breaks the genome randomly at many places and generates a large number of small fragments  of the genome.
the problem of reassembling all the fragmented reads into a small sequence close to the original sequence is known as the sequence assembly  problem.
although the sa problem seems similar to the shortest common super string  problem, there are in fact some fundamental differences.
firstly, the genome sequence might contain several repeating regions.
however, in any optimal solution to the scs problem we will not be able to find repeating regions - because we want to minimize the length of the solution string.
in addition to the repeats, there are other issues such as errors in reads and double strandedness of the reads which make the reduction to scs problem very complex.
existing algorithms to address the sa problem can be classified into two broad categories.
the first class of algorithms model a read as a vertex in a directed graph - known as the overlap graph  <cit> .
the second class of algorithms model every substring of length k  in a read as a vertex in a  a de bruijn graph  <cit> .
in an overlap graph, for every pair of overlapping reads, directed edges are introduced consistent with the orientation of the overlap.
since the transitive edges in the overlap graph are redundant for the assembly process they are removed and the resultant graph is called the string graph  <cit> .
the edges of the string graph are classified into optional, required and exact.
the sa problem is reduced to the identification of a shortest walk in the string graph which includes all the required and exact constraints on the edges.
identifying such a walk - minimum s-walk, on the string graph is known to be np-hard  <cit> .
in the de bruijn graph model every substring of length k in a read acts as a vertex  <cit> .
a directed edge is introduced between two k-mers if there exists some read in which these two k-mers overlap by exactly k -  <dig> symbols.
thus every read in the input is mapped to some path in the de bruijn graph.
the sa problem is reduced to a chinese postman problem  on the de bruijn graph, subject to the constraint that the resultant cpp tour include all the paths corresponding to the reads.
this problem  is also known to be np-hard.
thus solving the sa problem exactly on both of these graph models is intractable.
overlap graph based algorithms were found to perform better  with sanger based read methods.
sanger methods produce reads typically around  <dig> base pairs long and are very reliable.
unfortunately sanger based methods are very expensive.
to overcome the issues with sanger reads, new read technologies such as sequencing by synthesis  and pyrosequencing  have emerged.
these rapidly emerging read technologies are collectively termed as the next generation sequencing  technologies.
these ngs technologies can produce shorter genome fragments .
ngs technologies have drastically reduced the sequencing cost per base-pair when compared to sanger technology.
the reliability of ngs technology is acceptable, although it is relatively lower than the sanger technology.
in the recent past, the sequencing community has witnessed an exponential growth in the adoption of these ngs technologies.
on the other hand these ngs technologies can increase the number of reads in the sa problem by a large magnitude.
the computational cost of building an overlap graph on these short reads is much higher than that of building a de bruijn graph.
de bruijn graph based algorithms handle short reads very efficiently  in practice compared to the overlap graph based algorithms.
however the major bottleneck in using de bruijn graph based assemblers is that they require a large amount of memory to build the de bruijn graph.
this limits the applicability of these methods to large scale sa problems.
in this paper we address this issue and present algorithms to construct large de bruijn graphs very efficiently.
our algorithm is optimal in the sequential, parallel, and out-of-core models.
a recent work by jackson and aluru  <cit>  yielded parallel algorithms to build these de bruijn graphs efficiently.
they present a parallel algorithm that runs in o time using p processors .
the message complexity of their algorithm is Θ. by message complexity we mean the total number of messages  communicated by all the processors in the entire algorithm.
the distributed de bruijn graph building algorithm in abyss  <cit>  is similar to the algorithm of  <cit> .
one of the major contributions of our work is to show that we can build a bi-directed de bruijn graph in Θ time with a message complexity of Θ. an experimental comparison of these two algorithms on an sgi altix machine shows that our algorithm is considerably faster.
in addition, our algorithm works optimally in an out-of-core setting.
in particular, our algorithm requires only Θblog) i/o operations.
methods
preliminaries
let s ∈ Σn be a string of length n. any substring sj  of length k is called a k-mer of s. the set of all k-mers of a given string s is called the k-spectrum of s and is denoted by s .
given a k-mer sj , s¯j denotes the reverse complement of sj .
let ≤ be the partial ordering among the strings of equal length such that si ≤ sj indicates that the string si is lexicographically smaller than sj .
given any k-mer si, let s^i be the lexicographically smaller string between si and s¯j.
we call s^i the canonical k-mer of si.
in other words, if si≤s¯i then s^i =si otherwise s^i =s¯i.
a k-molecule of a given k-mer si is a tuple  consisting of the canonical k-mer of si and the reverse complement of the canonical k-mer.
we refer to the reverse compliment of the canonical k-mer as non-canonical k-mer.
a bi-directed graph is a generalized version of a standard directed graph.
in a directed graph every edge has only one arrow head .
on the other hand in a bi-directed graph every edge has two arrow heads attached to it .
let v be the set of vertices and e = {|vi, vj ∈ v Λ o <dig>  o <dig> ∈ {◁, ▷}} be the set of bi-directed edges in a bi-directed graph g. for any edge e =  ∈ e, o <dig> = e and o <dig> = e refer to the orientations of the arrow heads on the vertices vi and vj , respectively.
a walk w  between two nodes vi, vj ∈ v of a bi-directed graph g is a sequence vi,ei <dig> vi <dig> ei <dig> vi <dig> …,vim,eim+ <dig> vj, such that for every intermediate vertex vil,  <dig> ≤ l ≤ m the orientation of the arrow head on the incoming edge adjacent on vil should match the orientation of the arrow head on the outgoing edge.
to make this clearer, let eil,vil,eil+ <dig> be a sub-sequence in the walk w .
if eil= and eil+1= then for the walk to be valid it should be the case that o2=o' <dig>  figure  <dig> illustrates an example of a bi-directed graph.
figure  <dig> shows a simple bi-directed walk between the nodes a and e. a bi-directed walk between two nodes may not be simple.
figure  <dig> shows a bi-directed walk between a and e which is not simple - because b repeats twice.
a de bruijn graph dk of order k on a given string s is defined as follows.
the vertex set v of dk is defined as the k-spectrum of s ).
we use the notation suf , respectively) to denote the suffix  of length l in the string vi.
let the symbol ◦ denote the concatenation operation between two strings.
the set of directed edges e of dk is defined as follows:
e = {| suf = pre Λ vi <cit>  ◦ suf ◦ vj  ∈ s}.
we can also define de bruijn graphs for sets of strings as follows.
if s = {s <dig>  s <dig> .
.
.
sn} is any set of strings, a de bruijn graph bk of order k on s has v=∪i=1ns and e = {| suf = pre Λ ∃ l : vi <cit>  ◦ suf ◦ vj  ∈ s}.
to model the double strandedness of the dna molecules we should also consider the reverse complements  while we build the de bruijn graph.
to address this a bi-directed de bruijn graph bdk has been suggested in  <cit> .
the set of vertices v of bdk consists of all possible k-molecules from s ∪ s¯.
the set of bi- directed edges for bdk is defined as follows.
let x, y be two k-mers which are next to each other in some input string z∈.
then an edge is introduced between the k- molecules vi and vj corresponding to x and y, respectively.
please note that two consecutive k-mers in some input string always overlap by k -  <dig> symbols.
the converse need not be true.
the orientations of the arrow heads on the edges are chosen as follows.
if the canonical k-mers of nodes vi and vj overlap then an edge  is introduced.
if the canonical k-mer of vi overlaps with the non-canonical k-mer of vj then an edge  is introduced.
finally if the non-canonical k-mer of vi overlaps with canonical k-mer of vj then an edge  is introduced.
RESULTS
our algorithm to construct bi-directed de bruijn graphs
in this section we describe our algorithm biconstruct to construct a bi-directed de bruijn graph on a given set of reads.
the following are the main steps in our algorithm to build the bi-directed de bruijn graph.
let rf = {r <dig>  r <dig> .
.
.
rn}, ri ∈ Σr be the input set of reads.
rf¯={r1¯,r2¯... rn¯} is a set of reverse complements.
let r* =rf∪r¯f and rk+1=∪r∈r*s. rk+ <dig> is the set of all -mers from the input reads and their reverse complements.
•  generate canonical edges: let  =  be the k-mers corresponding to a -mer z ∈ rk+ <dig>  recall that x^ and ŷ are the canonical k- mers of x and y, respectively.
create a canonical bi-directed edge  for each -mer as follows.
={    x=x^,y=y^           ifx^≤y^,               elsex≠x^∧y=y^          if x^≤y^               else x=x^∧y≠y^          if x^≤y^               elsex≠x^∧y≠y^         if x^≤y^,              else
•  reduce multiplicity: sort all the bi-directed edges in , using radix sort.
since the parameter k is always odd this guarantees that a pair of canonical k-mers has exactly one orientation.
remove the duplicates and record the multiplicities of each canonical edge.
gather all the unique canonical edges into an edge list ℰ.
•  collect bi-directed vertices: for each canonical bi-directed edge ∈ℰ, collect the canonical k-mers v^i, v^j into list v. sort the list v and remove duplicates, such that v contains only the unique canonical k-mers.
•  adjacency list representation: the list ℰ is the collection of all the edges in the bi-directed graph and the list v is the collection of all the nodes in the bi-directed graph.
it is now easy to use ℰ and generate the adjacency lists representation for the bi-directed graph.
this may require one extra radix sorting step.
analysis of the algorithm biconstruct
theorem  <dig>  algorithm biconstruct builds a bi-directed de bruijn graph of order k in Θ time.
here n is number of characters/symbols in the input.
proof.
without loss of generality assume that all the reads are of the same size r. let n be the number of reads in the input.
this generates a total of n -mers in .
the radix sort needs to be applied in at most 2k log passes, resulting in 2k logn operations.
since n = nr is the total number of characters/symbols in the input, the radix sort takes Θ) operations assuming that in each pass of sorting only a constant number of symbols are used.
if k log = o, the sorting takes only o time.
in practice since n is very large in relation to k and |Σ|, the above condition readily holds.
since the time for this step dominates that of all the other steps, the runtime of the algorithm biconstruct is Θ.
a parallel algorithm for building bi-directed de bruijn graphs
in this section we illustrate a parallel implementation of our algorithm.
let p be the number of processors available.
we first distribute n/p reads for each processor.
all the processors can execute  in parallel.
in  we need to perform parallel sorting on the list ℰ. parallel radix/bucket sort -which does not use any all-to-all communications- can be employed to accomplish this.
for example, the integer sorting algorithm of kruskal, rudolph and snir takes o) time.
this will be o if n is a constant degree polynomial in p. in other words, for coarse-grain parallelism the run time is asymptotically optimal - which means optimality within a constant.
in practice coarse-grain parallelism is what we have.
here n = n .
we call this algorithm par-biconstruct.
theorem  <dig>  algorithm par-biconstruct builds a bi-directed de bruijn graph in time o. the message complexity is o.
the algorithm of jackson and aluru  <cit>  first identifies the vertices of the bi-directed graph - which they call representative nodes.
then for every representative node |Σ| many-to-many messages are generated.
these messages correspond to potential bi-directed edges which can be adjacent on that representative node.
a bi-directed edge is successfully created if both the representatives of the generated message exist in some processor, otherwise the edge is dropped.
this results in generating a total of Θ many-to-many messages.
the authors in the same paper demonstrate that communicating many-to-many messages is a major bottleneck and does not scale well.
we remark that the algorithm biconstruct does not involve any many-to-many communications and does not have any scaling bottlenecks.
the algorithm presented in  <cit>  can potentially generate spurious bi-directed edges.
according to the definition  <cit>  of the bi-directed de bruijn graph in the context of sa problem, a bi-directed edge between two k-mers/vertices exists if and only if there exists some read in which these two k-mers are adjacent.
we illustrate this by a simple example.
consider a read ri = aatgcatc.
if we wish to build a bi-directed graph of order  <dig>  then aat, atg, tgc, gca, cat , and atc form a subset of the vertices of the bi-directed graph.
in this example we see that the k-mers aat and atc overlap by exactly  <dig> symbols.
however there cannot be any bi-directed edge between them according to the definition - because they are not adjacent.
on the other hand the algorithm presented in  <cit>  generates the following edges with respect to the k-mer aat : {, , , }.
the edges  and  are purged since the k-mers ata and atc are missing.
however bi-directed edges with corresponding orientations are established between atg and atc.
unfortunately  is a spurious edge and can potentially generate wrong assembly solutions.
in contrast to their algorithm  <cit>  our algorithm does not use all-to-all communications - although we use point-to-point communications.
out of core algorithms for building bi-directed de bruijn graphs
theorem  <dig>  there exists an out-of-core algorithm to construct a bi-directed de bruijn graph using an optimal number of i/o's.
proof.
replace the radix sorting with an external r-way merge sort which takes only Θblog) i/o's.
here m is the main memory size, n is the sum of the lengths of all reads, and b is the block size of the disk.
simplified bi-directed de bruijn graphs
the bi-directed de bruijn graph constructed in the previous section may contain several linear chains.
these chains have to be compacted to save space as well as time.
the graph that results after this compaction step is referred to as the simplified bi-directed graph.
a linear chain of bi-directed edges between nodes u and v can be compacted only if we can find a valid bi-directed walk connecting u and v. all the k-mers/vertices in a compactable chain can be merged into a single node, and relabelled with the corresponding forward and reverse complementary strings.
in figure  <dig> we can see that the nodes x <dig> and x <dig> can be connected with a valid bi-directed walk and hence these nodes are merged into a single node.
in practice the compaction of chains plays a very crucial role.
it has been reported that merging the linear chains can reduce the number of nodes in the graph by up to 30%  <cit> .
although the bi-directed chain compaction problem seems like a list ranking problem there are some fundamental differences.
firstly, a bi-directed edge can be traversed in both the directions.
as a result, applying pointer jumping directly on a bi-directed graph can lead to cycles and cannot compact the bi-directed chains correctly.
figure  <dig> illustrates the first phase of pointer jumping.
pointer jumping is an operation on a directed chain/linked list which changes the neighbour of a list node to its neighbour's neighbour.
as we can see, the green arcs indicate valid pointer jumps from the starting nodes.
however since the orientation of the node y <dig> is reverse relative to the direction of pointer jumping a cycle results.
in contrast, a valid bi-directed chain compaction would merge all the nodes between y <dig> and y <dig> since there is a valid bi-directed walk between y <dig> and y <dig>  on the other hand, bi-directed chain compaction may result in changing the orientation of some bi-directed edges and these edges should be recognised and updated accordingly.
consider a bi-directed chain in figure  <dig>  this chain contains two possible bi-directed walks - y <dig> to y <dig> and x <dig> to x <dig>  see figure  <dig>  the walk from y <dig> to y <dig>  spells out a label tagg after compaction.
once we perform this compaction ) the orientation of the edge between y <dig> and y <dig> in the original graph is no longer valid, because the label ccta on the newly compacted node cannot overlap with the label ggt on the node y <dig>  however the label tagg on the newly compacted node overlaps with label ggt on the y <dig> and hence its orientation should be updated.
on the other hand after the edge between x <dig> and y <dig> does not need any update after compacting the nodes x <dig>  x <dig> and x <dig>  see figure  <dig> and figure  <dig>
since bi-directed chain compaction has a lot of practical importance, efficient and correct algorithms are essential.
we now provide algorithms for the bi-directed chain compaction problem.
our key idea here is to transform a bi-directed graph into a directed graph and then apply list ranking.
we define the listrankingtransform as an operation which replaces every bi-directed edge with a pair of directed edges with some orientation - see figure  <dig> for these orientations.
given a list of candidate canonical bi-directed edges, we apply a listrankingtransform  which introduces two new nodes v+, v- for every node v in the original graph.
directed edges corresponding to the orientation are introduced.
see figure  <dig>
lemma  <dig>  let bg be a bi-directed graph; let bgt be the directed graph after applying listrankingtransform.
two nodes u, v ∈ v are connected by a bi-directed path iff u+ ∈ vt  is connected to one of v+ or v- by a directed path.
proof.
we first prove the forward direction by induction on the number of nodes in the bi- directed graph.
consider the basis of induction when |v | =  <dig>  let v <dig>  v <dig> ∈ v. clearly we are only interested when v <dig> and v <dig> are connected by a bi-directed edge.
by the definition of listrankingtransform the lemma in this case is trivially true.
now consider a bi-directed graph with |v | = n +  <dig> nodes, if the path between vi, i < n and vj , j < n does not involve node vn the lemma still holds by induction on the sub bi-directed graph bg.
now assume that vi .
.
.
vp, vn, vq .
.
.
vj is the bi-directed path between vi and vj involving the node vn.
).
figure  <dig> shows what the transformed directed graph looks like.
observe the colors of bi-directed edges and the corresponding directed edges.
by the induction hypothesis on the sub bi-directed paths vi .
.
.
vp, vn and vn, vq .
.
.
vj we have the following.
vi+ is connected to vn+ or vn− by some directed path p <dig> ); vn+ is connected to vj+ or vj− by some directed path p <dig>  we examine three possible cases depending on how the directed edge from p <dig> and p <dig> is incident on vn+ in case- <dig> we have both p <dig> and p <dig> pointing into node vn+.
this implies that the orientation of the bi-directed edges in the original graph is according to figure  <dig>  in this case we cannot have a bi-directed walk involving the node vn, which contradicts our original assumption.
similarly case- <dig> ) would also lead to a similar contradiction.
only case- <dig> would let node vn be involved in a bi-directed walk.
in this case vi+ will be connected to either vj+ or vj− by concatenation of the paths p <dig> and p <dig>  we can make a similar argument to prove the reverse direction.
algorithm for bi-directed chain compaction
given a bi-directed graph we now give an outline of the algorithm which compacts all the valid bi-directed chains.
• step-1: apply the listrankingtransform for each bi-directed edge.
let the resultant directed graph be g.
• step-2: identify a subset of nodes v' = {v : v ∈ v ,  > <dig> or dout >1)} and a subset of edges e' = { :  ∈ e, }.
• step-3: apply pointer jumping on the directed graph g.
• step-4: now let  be a maximal chain obtained after pointer jumping.
due to the symmetry in the graph there exists a corresponding complementary chain .
each chain is replaced with a single node and its label is the concatenation of all the labels in the chain.
we should stick to some convention while we give a new number to the newly created node.
for example, we can choose min{vi, vj } as the new number for the newly created node.
in our example if vi = min{vi, vj } then we replace the chain  with node vi+ and relabel it with the concatenated label.
similarly, the chain  will be replaced with the node vi− and relabeled accordingly.
• step-5: finally, to maintain the connectivity we need to update the edges in e' to reflect the changes during compaction.
coming back to our example, we have replaced the chain  with the node vi+.
as a result we need to replace any edge ∈e' with the edge .
similarly we also need to update any edges adjacent on vj+.
note that all of the above steps can be accomplished with some constant number of radix sorting operations.
figure  <dig> illustrates the compaction algorithm on a bi-directed graph.
the red nodes in figure  <dig> indicate the nodes in the set v'.
red colored edges indicate the edges in e'.
after list ranking we will have four maximal chains as follows: , , .
now if we stick to the convention described in step- <dig> we renumber the new node corresponding to the chains ,  as y <dig>  as a result the edges  and  are updated ) as  and .
finally the directed edges are replaced with bi-directed edges in figure  <dig>
analysis of bi-directed compaction on parallel and out-of-core models
let ℰl be the list of candidate edges for compaction.
to do compaction in parallel, we can use a segmented parallel prefix  <cit>  on p processors to accomplish this in time o).
list ranking can also be done out-of-core as follows.
without loss of generality we can treat the input for the list ranking problem as a set s of ordered tuples of the form .
given s we create a copy and call it s'.
we now perform an external sort of s and s' with respect to y  as the key) and x, respectively.
the two sorted lists are scanned linearly to identify tuples  ∈ s,  ∈ s' such that y =x'.
these two tuples are merged into a single tuple  and is added to a list ℰl'.
this process is now repeated on ℰl'.
note that if the underlying graph induced by ℰl does not have any cycles then |ℰl'|≤|ℰl|/2; which means that the size of ℰl' geometrically decreases after every iteration.
the i/o complexity of each iteration is dominated by the external sorting and hence bi-directed compaction can be accomplished out-of-core with Θ|ℰl|blogmb) i/o operations, where c is the length of the longest chain.
care should be taken to deal with cycles.
the sort-merge algorithm mentioned above will run forever in the presence of cycles.
to address this we can maintain what is known as join count in every sort-merge phase.
given any s the join count of a tuple  ∈ s is an indicator variable j =  <dig>  if ∃ ∈ s; else  <dig>  finally j = Σ∈s j. notice that the function j strictly decreases in every sort and merge phase and finally becomes zero when there are no cycles.
however in the presence of cycles the function j decreases and then remains constant.
thus if the function j remains constant in any two consecutive sort-merge phases we can stop iterating and report that there are some cycles.
once we stop the list ranking we can easily detect the edges in the cycles.
our implementation of this out-of-core list ranking based on this idea is available at http://trinity.engr.uconn.edu/~vamsik/ex-list-rank.
improving the construction of the bi-directed de bruijn graph in some practical assemblers
in this section we briefly describe how our algorithms can be used to speedup some of the existing sa programs.
as an example, we consider velvet  <cit> .
velvet is a suite of programs - velveth and velvetg, which has recently gained acclamation in assembling short reads.
the velvet program builds a simplified bi-directed graph from a set of reads.
we now briefly describe the algorithm used in velvet to build this graph.
the velvet program puts all the k-mers from the input into a hash table and then identifies the k-mers which are present in at least  <dig> reads - this information is called the roadmap in velvet's terminology.
the program then builds a de bruijn graph using these k-mers.
finally it takes every read and threads it on these k-mers.
the worst case time complexity is o) - assuming that the implementation of hash table is based on a balanced search tree.
however velvet uses a splay tree so this would be the amortized runtime rather than the worst case.
since velvet builds this graph entirely in-memory, this has some serious scalability problems especially on large scale assembly projects.
however velvet has some very good assembly heuristics to remove errors and identify redundant assembly paths, etc.
our out-of-core algorithm can act as a replacement to the code in velvet that performs in-memory graph construction.
the internal de bruijn graph of velvet is slightly different from the bi-directed graph our algorithm builds.
it is easy to see the equivalence between these two representations.
.
we have implemented an out-of-core algorithm that takes in a file with reads and the value of k and generates the graph for velvet program.
to be more precise, velvet program creates a file with the name graph in the directory when we run the velvetg program.
we have modified the code in the velvet program by adding an option which quits after it builds the graph file without any simplification.
this gives us a chance to compare the velvet's algorithm which can build the graph file with our algorithm.
the results and more details about the program are in the results section.
discussion
before we go into the discussion we briefly describe our experimental setting.
we used a sgi-altix 64-bit,  <dig> node supercomputer with a ram of  <dig> gb per node for our parallel algorithm experiments.
for our sequential out-of-core experiments we used a 32-bit x <dig> machine with  <dig> gb of ram.
all our algorithms are implemented in c under linux environment.
we have compared the performance of our algorithm and that of jackson and aluru  <cit> .
we refer to the later algorithm as ja.
to make this comparison fair, we have implemented the ja algorithm  also on the same platform that our algorithm runs on.
we have used the sgi/altix ia- <dig> machine for all of our experiments.
our implementation uses mpi for communication between the processors.
we used a test set of  <dig> million un-paired reads obtained from sequencing a plant genome at cshl.
the performance of both the algorithms is measured with various values of k  on multiple processors.
both the algorithms  use the same underlying parallel sorting routines.
input reads:  <dig> short reads, each of size  <dig> base pairs
average user time speed up =  <dig> x
average system time speed up =  <dig> x
average real time speed up =  <dig> x
the user time of our algorithm is also consistently superior compared to the user time of ja.
this clearly is because we do much less local computations.
in contrast, ja needs to do a lot of local processing, which arises from processing all the received edges, removing redundant ones, and collecting the necessary edges to perform many-to-many communications.
we also compare the memory used by both the algorithms.
we briefly describe how we obtained the memory reports in our experiments.
since the memory used by each processor is different during execution at any given instance we add-up the memory used by each processor and divide by the number of processors and we report this number in our experiments.
we obtained the resident memory and shared memory from the top command and averaged it over the number of memory probe samples obtained by top.
table  <dig> gives details of the memory usage of both the algorithms.
from these results it is clear that our approach is also efficient compared to the ja algorithm.
parbiconstruct uses upto 4x less resident memory compared to the ja algorithm.
input reads:  <dig> short reads, each of size  <dig> base pairs
average efficiency of resident memory across all processors =  <dig>
average efficiency of shared memory across all processors  <dig>
since ja takes a significant amount of time for inputs larger than  <dig> million, we have compared these algorithms only for input sizes up to  <dig> million.
the experimental results reported in  <cit>  start with at least  <dig> processors.
we however show the scalablity of our algorithm for up to  <dig> million  reads in table  <dig>  table  <dig> clearly demonstrates the scalability of our algorithm.
we make our implementations and all the details of test cases used available at http://trinity.engr.uconn.edu/~vamsik/parbidirected.
out-of-core algorithm versus velvet graph building algorithm
our aim is to study the computational efficiency of the current velvet's algorithm to build the de bruijn graph and our algorithm.
to accomplish this we have modified the code of velvet to stop once it completes building the graph from the reads.
this is done as follows.
firstly we run the velveth program to complete the building of roadmaps.
the code of velvetg is modified such that the program dumps out the graph file after threading of the reads.
our out-of-core algorithm generates graph file directly by taking the reads file and the value of k. we have used a low end desktop 32-bit machine with  <dig> gb ram to demonstrate the scalability of our out-of-core algorithm.
our results indicate that the velvet algorithm starts virtual memory trashing  <cit>  for around  <dig> million reads with k =  <dig>  this trashing leads to massive increase in the page-faults and stalls the program from progressing further.
thus the velvet algorithm cannot build large bi-directed graphs.
in contrast to velvet our algorithm works with a constant  amount of memory and scales well for building large amounts of reads - which we demonstrate in table  <dig>
* indicates that velvet program did not complete and the program was stopped after this time.
the program is available at http://trinity.engr.uconn.edu/~vamsik/ex-build-vgraph/.
CONCLUSIONS
in this paper we have presented an efficient algorithm to build a bi-directed de bruijn graph, which is a fundamental data structure for any sequence assembly program - based on an eulerian approach.
our algorithm is also efficient in parallel and out of core settings.
these algorithms can be used in building large scale bi-directed de bruijn graphs.
also, our algorithm does not employ any all-to-all communications in a parallel setting and performs better than that of  <cit> .
finally, our out-of-core algorithm can build these graphs with a constant amount of ram, and hence can act as a replacement for the graph construction algorithm employed by velvet  <cit> .
authors' contributions
vk designed and implemented the algorithms, and drafted the manuscript.
sr participated in designing the algorithms, revised the manuscript, and coordinated all phases of the project.
hd also participated in the design of algorithms and contributed towards the figures in the manuscript.
mv and vt introduced the sequence assembly problem to the team and provided short read data to validate our method.
all the authors read and approved the final manuscript.

 sequencing genomes is one of the most fundamental problems in modern biology and has immense impact on biomedical research. de novo sequencing is computationally more challenging when compared to sequencing with a reference genome. on the other hand the existing sequencing technology is not mature enough to identify/read the entire sequence of the genome - especially for complex organisms like the mammals. however small fragments of the genome can be read with acceptable accuracy. the shotgun sequencing employed in many sequencing projects breaks the genome randomly at many places and generates a large number of small fragments of the genome. the problem of reassembling all the fragmented reads into a small sequence close to the original sequence is known as the sequence assembly problem. although the sa problem seems similar to the shortest common super string problem, there are in fact some fundamental differences. firstly, the genome sequence might contain several repeating regions. however, in any optimal solution to the scs problem we will not be able to find repeating regions - because we want to minimize the length of the solution string. in addition to the repeats, there are other issues such as errors in reads and double strandedness of the reads which make the reduction to scs problem very complex. existing algorithms to address the sa problem can be classified into two broad categories. the first class of algorithms model a read as a vertex in a directed graph - known as the overlap graph. the second class of algorithms model every substring of length k in a read as a vertex in a a de bruijn graph. in an overlap graph, for every pair of overlapping reads, directed edges are introduced consistent with the orientation of the overlap. since the transitive edges in the overlap graph are redundant for the assembly process they are removed and the resultant graph is called the string graph. the edges of the string graph are classified into optional, required and exact. the sa problem is reduced to the identification of a shortest walk in the string graph which includes all the required and exact constraints on the edges. identifying such a walk - minimum s-walk, on the string graph is known to be np-hard. in the de bruijn graph model every substring of length k in a read acts as a vertex. a directed edge is introduced between two k-mers if there exists some read in which these two k-mers overlap by exactly k - symbols. thus every read in the input is mapped to some path in the de bruijn graph. the sa problem is reduced to a chinese postman problem on the de bruijn graph, subject to the constraint that the resultant cpp tour include all the paths corresponding to the reads. this problem is also known to be np-hard. thus solving the sa problem exactly on both of these graph models is intractable. overlap graph based algorithms were found to perform better with sanger based read methods. sanger methods produce reads typically around base pairs long and are very reliable. unfortunately sanger based methods are very expensive. to overcome the issues with sanger reads, new read technologies such as sequencing by synthesis and pyrosequencing have emerged. these rapidly emerging read technologies are collectively termed as the next generation sequencing technologies. these ngs technologies can produce shorter genome fragments. ngs technologies have drastically reduced the sequencing cost per base-pair when compared to sanger technology. the reliability of ngs technology is acceptable, although it is relatively lower than the sanger technology. in the recent past, the sequencing community has witnessed an exponential growth in the adoption of these ngs technologies. on the other hand these ngs technologies can increase the number of reads in the sa problem by a large magnitude. the computational cost of building an overlap graph on these short reads is much higher than that of building a de bruijn graph. de bruijn graph based algorithms handle short reads very efficiently in practice compared to the overlap graph based algorithms. however the major bottleneck in using de bruijn graph based assemblers is that they require a large amount of memory to build the de bruijn graph. this limits the applicability of these methods to large scale sa problems. in this paper we address this issue and present algorithms to construct large de bruijn graphs very efficiently. our algorithm is optimal in the sequential, parallel, and out-of-core models. a recent work by jackson and aluru yielded parallel algorithms to build these de bruijn graphs efficiently. they present a parallel algorithm that runs in o time using p processors. the message complexity of their algorithm is Θ. by message complexity we mean the total number of messages communicated by all the processors in the entire algorithm. the distributed de bruijn graph building algorithm in abyss is similar to the algorithm of. one of the major contributions of our work is to show that we can build a bi-directed de bruijn graph in Θ time with a message complexity of Θ. an experimental comparison of these two algorithms on an sgi altix machine shows that our algorithm is considerably faster. in addition, our algorithm works optimally in an out-of-core setting. in particular, our algorithm requires only Θblog) i/o operations. methods preliminaries let s ∈ Σn be a string of length n. any substring sj of length k is called a k-mer of s. the set of all k-mers of a given string s is called the k-spectrum of s and is denoted by s. given a k-mer sj, s¯j denotes the reverse complement of sj. let ≤ be the partial ordering among the strings of equal length such that si ≤ sj indicates that the string si is lexicographically smaller than sj. given any k-mer si, let s^i be the lexicographically smaller string between si and s¯j. we call s^i the canonical k-mer of si. in other words, if si≤s¯i then s^i =si otherwise s^i =s¯i. a k-molecule of a given k-mer si is a tuple consisting of the canonical k-mer of si and the reverse complement of the canonical k-mer. we refer to the reverse compliment of the canonical k-mer as non-canonical k-mer. a bi-directed graph is a generalized version of a standard directed graph. in a directed graph every edge has only one arrow head. on the other hand in a bi-directed graph every edge has two arrow heads attached to it. let v be the set of vertices and e = {|vi, vj ∈ v Λ o o ∈ {◁, ▷}} be the set of bi-directed edges in a bi-directed graph g. for any edge e = ∈ e, o = e and o = e refer to the orientations of the arrow heads on the vertices vi and vj, respectively. a walk w between two nodes vi, vj ∈ v of a bi-directed graph g is a sequence vi,ei vi ei vi …,vim,eim+ vj, such that for every intermediate vertex vil, ≤ l ≤ m the orientation of the arrow head on the incoming edge adjacent on vil should match the orientation of the arrow head on the outgoing edge. to make this clearer, let eil,vil,eil+ be a sub-sequence in the walk w. if eil= and eil+1= then for the walk to be valid it should be the case that o2=o' figure illustrates an example of a bi-directed graph. figure shows a simple bi-directed walk between the nodes a and e. a bi-directed walk between two nodes may not be simple. figure shows a bi-directed walk between a and e which is not simple - because b repeats twice. a de bruijn graph dk of order k on a given string s is defined as follows. the vertex set v of dk is defined as the k-spectrum of s ). we use the notation suf, respectively) to denote the suffix of length l in the string vi. let the symbol ◦ denote the concatenation operation between two strings. the set of directed edges e of dk is defined as follows: e = {| suf = pre Λ vi ◦ suf ◦ vj ∈ s}. we can also define de bruijn graphs for sets of strings as follows. if s = {s s... sn} is any set of strings, a de bruijn graph bk of order k on s has v=∪i=1ns and e = {| suf = pre Λ ∃ l: vi ◦ suf ◦ vj ∈ s}. to model the double strandedness of the dna molecules we should also consider the reverse complements while we build the de bruijn graph. to address this a bi-directed de bruijn graph bdk has been suggested in. the set of vertices v of bdk consists of all possible k-molecules from s ∪ s¯. the set of bi- directed edges for bdk is defined as follows. let x, y be two k-mers which are next to each other in some input string z∈. then an edge is introduced between the k- molecules vi and vj corresponding to x and y, respectively. please note that two consecutive k-mers in some input string always overlap by k - symbols. the converse need not be true. the orientations of the arrow heads on the edges are chosen as follows. if the canonical k-mers of nodes vi and vj overlap then an edge is introduced. if the canonical k-mer of vi overlaps with the non-canonical k-mer of vj then an edge is introduced. finally if the non-canonical k-mer of vi overlaps with canonical k-mer of vj then an edge is introduced.  our algorithm to construct bi-directed de bruijn graphs in this section we describe our algorithm biconstruct to construct a bi-directed de bruijn graph on a given set of reads. the following are the main steps in our algorithm to build the bi-directed de bruijn graph. let rf = {r r... rn}, ri ∈ Σr be the input set of reads. rf¯={r1¯,r2¯... rn¯} is a set of reverse complements. let r* =rf∪r¯f and rk+1=∪r∈r*s. rk+ is the set of all -mers from the input reads and their reverse complements. • generate canonical edges: let = be the k-mers corresponding to a -mer z ∈ rk+ recall that x^ and ŷ are the canonical k- mers of x and y, respectively. create a canonical bi-directed edge for each -mer as follows. ={    x=x^,y=y^           ifx^≤y^,               elsex≠x^∧y=y^          if x^≤y^               else x=x^∧y≠y^          if x^≤y^               elsex≠x^∧y≠y^         if x^≤y^,              else • reduce multiplicity: sort all the bi-directed edges in, using radix sort. since the parameter k is always odd this guarantees that a pair of canonical k-mers has exactly one orientation. remove the duplicates and record the multiplicities of each canonical edge. gather all the unique canonical edges into an edge list ℰ. • collect bi-directed vertices: for each canonical bi-directed edge ∈ℰ, collect the canonical k-mers v^i, v^j into list v. sort the list v and remove duplicates, such that v contains only the unique canonical k-mers. • adjacency list representation: the list ℰ is the collection of all the edges in the bi-directed graph and the list v is the collection of all the nodes in the bi-directed graph. it is now easy to use ℰ and generate the adjacency lists representation for the bi-directed graph. this may require one extra radix sorting step. analysis of the algorithm biconstruct theorem algorithm biconstruct builds a bi-directed de bruijn graph of order k in Θ time. here n is number of characters/symbols in the input. proof. without loss of generality assume that all the reads are of the same size r. let n be the number of reads in the input. this generates a total of n -mers in. the radix sort needs to be applied in at most 2k log passes, resulting in 2k logn operations. since n = nr is the total number of characters/symbols in the input, the radix sort takes Θ) operations assuming that in each pass of sorting only a constant number of symbols are used. if k log = o, the sorting takes only o time. in practice since n is very large in relation to k and |Σ|, the above condition readily holds. since the time for this step dominates that of all the other steps, the runtime of the algorithm biconstruct is Θ. a parallel algorithm for building bi-directed de bruijn graphs in this section we illustrate a parallel implementation of our algorithm. let p be the number of processors available. we first distribute n/p reads for each processor. all the processors can execute in parallel. in we need to perform parallel sorting on the list ℰ. parallel radix/bucket sort -which does not use any all-to-all communications- can be employed to accomplish this. for example, the integer sorting algorithm of kruskal, rudolph and snir takes o) time. this will be o if n is a constant degree polynomial in p. in other words, for coarse-grain parallelism the run time is asymptotically optimal - which means optimality within a constant. in practice coarse-grain parallelism is what we have. here n = n. we call this algorithm par-biconstruct. theorem algorithm par-biconstruct builds a bi-directed de bruijn graph in time o. the message complexity is o. the algorithm of jackson and aluru first identifies the vertices of the bi-directed graph - which they call representative nodes. then for every representative node |Σ| many-to-many messages are generated. these messages correspond to potential bi-directed edges which can be adjacent on that representative node. a bi-directed edge is successfully created if both the representatives of the generated message exist in some processor, otherwise the edge is dropped. this results in generating a total of Θ many-to-many messages. the authors in the same paper demonstrate that communicating many-to-many messages is a major bottleneck and does not scale well. we remark that the algorithm biconstruct does not involve any many-to-many communications and does not have any scaling bottlenecks. the algorithm presented in can potentially generate spurious bi-directed edges. according to the definition of the bi-directed de bruijn graph in the context of sa problem, a bi-directed edge between two k-mers/vertices exists if and only if there exists some read in which these two k-mers are adjacent. we illustrate this by a simple example. consider a read ri = aatgcatc. if we wish to build a bi-directed graph of order then aat, atg, tgc, gca, cat, and atc form a subset of the vertices of the bi-directed graph. in this example we see that the k-mers aat and atc overlap by exactly symbols. however there cannot be any bi-directed edge between them according to the definition - because they are not adjacent. on the other hand the algorithm presented in generates the following edges with respect to the k-mer aat: {,,, }. the edges and are purged since the k-mers ata and atc are missing. however bi-directed edges with corresponding orientations are established between atg and atc. unfortunately is a spurious edge and can potentially generate wrong assembly solutions. in contrast to their algorithm our algorithm does not use all-to-all communications - although we use point-to-point communications. out of core algorithms for building bi-directed de bruijn graphs theorem there exists an out-of-core algorithm to construct a bi-directed de bruijn graph using an optimal number of i/o's. proof. replace the radix sorting with an external r-way merge sort which takes only Θblog) i/o's. here m is the main memory size, n is the sum of the lengths of all reads, and b is the block size of the disk. simplified bi-directed de bruijn graphs the bi-directed de bruijn graph constructed in the previous section may contain several linear chains. these chains have to be compacted to save space as well as time. the graph that results after this compaction step is referred to as the simplified bi-directed graph. a linear chain of bi-directed edges between nodes u and v can be compacted only if we can find a valid bi-directed walk connecting u and v. all the k-mers/vertices in a compactable chain can be merged into a single node, and relabelled with the corresponding forward and reverse complementary strings. in figure we can see that the nodes x and x can be connected with a valid bi-directed walk and hence these nodes are merged into a single node. in practice the compaction of chains plays a very crucial role. it has been reported that merging the linear chains can reduce the number of nodes in the graph by up to 30%. although the bi-directed chain compaction problem seems like a list ranking problem there are some fundamental differences. firstly, a bi-directed edge can be traversed in both the directions. as a result, applying pointer jumping directly on a bi-directed graph can lead to cycles and cannot compact the bi-directed chains correctly. figure illustrates the first phase of pointer jumping. pointer jumping is an operation on a directed chain/linked list which changes the neighbour of a list node to its neighbour's neighbour. as we can see, the green arcs indicate valid pointer jumps from the starting nodes. however since the orientation of the node y is reverse relative to the direction of pointer jumping a cycle results. in contrast, a valid bi-directed chain compaction would merge all the nodes between y and y since there is a valid bi-directed walk between y and y on the other hand, bi-directed chain compaction may result in changing the orientation of some bi-directed edges and these edges should be recognised and updated accordingly. consider a bi-directed chain in figure this chain contains two possible bi-directed walks - y to y and x to x see figure the walk from y to y spells out a label tagg after compaction. once we perform this compaction ) the orientation of the edge between y and y in the original graph is no longer valid, because the label ccta on the newly compacted node cannot overlap with the label ggt on the node y however the label tagg on the newly compacted node overlaps with label ggt on the y and hence its orientation should be updated. on the other hand after the edge between x and y does not need any update after compacting the nodes x x and x see figure and figure since bi-directed chain compaction has a lot of practical importance, efficient and correct algorithms are essential. we now provide algorithms for the bi-directed chain compaction problem. our key idea here is to transform a bi-directed graph into a directed graph and then apply list ranking. we define the listrankingtransform as an operation which replaces every bi-directed edge with a pair of directed edges with some orientation - see figure for these orientations. given a list of candidate canonical bi-directed edges, we apply a listrankingtransform which introduces two new nodes v+, v- for every node v in the original graph. directed edges corresponding to the orientation are introduced. see figure lemma let bg be a bi-directed graph; let bgt be the directed graph after applying listrankingtransform. two nodes u, v ∈ v are connected by a bi-directed path iff u+ ∈ vt is connected to one of v+ or v- by a directed path. proof. we first prove the forward direction by induction on the number of nodes in the bi- directed graph. consider the basis of induction when |v | = let v v ∈ v. clearly we are only interested when v and v are connected by a bi-directed edge. by the definition of listrankingtransform the lemma in this case is trivially true. now consider a bi-directed graph with |v | = n + nodes, if the path between vi, i < n and vj, j < n does not involve node vn the lemma still holds by induction on the sub bi-directed graph bg. now assume that vi... vp, vn, vq... vj is the bi-directed path between vi and vj involving the node vn. ). figure shows what the transformed directed graph looks like. observe the colors of bi-directed edges and the corresponding directed edges. by the induction hypothesis on the sub bi-directed paths vi... vp, vn and vn, vq... vj we have the following. vi+ is connected to vn+ or vn− by some directed path p ); vn+ is connected to vj+ or vj− by some directed path p we examine three possible cases depending on how the directed edge from p and p is incident on vn+ in case- we have both p and p pointing into node vn+. this implies that the orientation of the bi-directed edges in the original graph is according to figure in this case we cannot have a bi-directed walk involving the node vn, which contradicts our original assumption. similarly case- ) would also lead to a similar contradiction. only case- would let node vn be involved in a bi-directed walk. in this case vi+ will be connected to either vj+ or vj− by concatenation of the paths p and p we can make a similar argument to prove the reverse direction. algorithm for bi-directed chain compaction given a bi-directed graph we now give an outline of the algorithm which compacts all the valid bi-directed chains. • step-1: apply the listrankingtransform for each bi-directed edge. let the resultant directed graph be g. • step-2: identify a subset of nodes v' = {v: v ∈ v, > or dout >1)} and a subset of edges e' = {: ∈ e, }. • step-3: apply pointer jumping on the directed graph g. • step-4: now let be a maximal chain obtained after pointer jumping. due to the symmetry in the graph there exists a corresponding complementary chain. each chain is replaced with a single node and its label is the concatenation of all the labels in the chain. we should stick to some convention while we give a new number to the newly created node. for example, we can choose min{vi, vj } as the new number for the newly created node. in our example if vi = min{vi, vj } then we replace the chain with node vi+ and relabel it with the concatenated label. similarly, the chain will be replaced with the node vi− and relabeled accordingly. • step-5: finally, to maintain the connectivity we need to update the edges in e' to reflect the changes during compaction. coming back to our example, we have replaced the chain with the node vi+. as a result we need to replace any edge ∈e' with the edge. similarly we also need to update any edges adjacent on vj+. note that all of the above steps can be accomplished with some constant number of radix sorting operations. figure illustrates the compaction algorithm on a bi-directed graph. the red nodes in figure indicate the nodes in the set v'. red colored edges indicate the edges in e'. after list ranking we will have four maximal chains as follows:,,. now if we stick to the convention described in step- we renumber the new node corresponding to the chains,  as y as a result the edges and are updated ) as and. finally the directed edges are replaced with bi-directed edges in figure analysis of bi-directed compaction on parallel and out-of-core models let ℰl be the list of candidate edges for compaction. to do compaction in parallel, we can use a segmented parallel prefix on p processors to accomplish this in time o). list ranking can also be done out-of-core as follows. without loss of generality we can treat the input for the list ranking problem as a set s of ordered tuples of the form. given s we create a copy and call it s'. we now perform an external sort of s and s' with respect to y as the key) and x, respectively. the two sorted lists are scanned linearly to identify tuples ∈ s, ∈ s' such that y =x'. these two tuples are merged into a single tuple and is added to a list ℰl'. this process is now repeated on ℰl'. note that if the underlying graph induced by ℰl does not have any cycles then |ℰl'|≤|ℰl|/2; which means that the size of ℰl' geometrically decreases after every iteration. the i/o complexity of each iteration is dominated by the external sorting and hence bi-directed compaction can be accomplished out-of-core with Θ|ℰl|blogmb) i/o operations, where c is the length of the longest chain. care should be taken to deal with cycles. the sort-merge algorithm mentioned above will run forever in the presence of cycles. to address this we can maintain what is known as join count in every sort-merge phase. given any s the join count of a tuple ∈ s is an indicator variable j = if ∃ ∈ s; else finally j = Σ∈s j. notice that the function j strictly decreases in every sort and merge phase and finally becomes zero when there are no cycles. however in the presence of cycles the function j decreases and then remains constant. thus if the function j remains constant in any two consecutive sort-merge phases we can stop iterating and report that there are some cycles. once we stop the list ranking we can easily detect the edges in the cycles. our implementation of this out-of-core list ranking based on this idea is available at http://trinity.engr.uconn.edu/~vamsik/ex-list-rank. improving the construction of the bi-directed de bruijn graph in some practical assemblers in this section we briefly describe how our algorithms can be used to speedup some of the existing sa programs. as an example, we consider velvet. velvet is a suite of programs - velveth and velvetg, which has recently gained acclamation in assembling short reads. the velvet program builds a simplified bi-directed graph from a set of reads. we now briefly describe the algorithm used in velvet to build this graph. the velvet program puts all the k-mers from the input into a hash table and then identifies the k-mers which are present in at least reads - this information is called the roadmap in velvet's terminology. the program then builds a de bruijn graph using these k-mers. finally it takes every read and threads it on these k-mers. the worst case time complexity is o) - assuming that the implementation of hash table is based on a balanced search tree. however velvet uses a splay tree so this would be the amortized runtime rather than the worst case. since velvet builds this graph entirely in-memory, this has some serious scalability problems especially on large scale assembly projects. however velvet has some very good assembly heuristics to remove errors and identify redundant assembly paths, etc. our out-of-core algorithm can act as a replacement to the code in velvet that performs in-memory graph construction. the internal de bruijn graph of velvet is slightly different from the bi-directed graph our algorithm builds. it is easy to see the equivalence between these two representations.. we have implemented an out-of-core algorithm that takes in a file with reads and the value of k and generates the graph for velvet program. to be more precise, velvet program creates a file with the name graph in the directory when we run the velvetg program. we have modified the code in the velvet program by adding an option which quits after it builds the graph file without any simplification. this gives us a chance to compare the velvet's algorithm which can build the graph file with our algorithm. the results and more details about the program are in the results section. discussion before we go into the discussion we briefly describe our experimental setting. we used a sgi-altix 64-bit, node supercomputer with a ram of gb per node for our parallel algorithm experiments. for our sequential out-of-core experiments we used a 32-bit x machine with gb of ram. all our algorithms are implemented in c under linux environment. we have compared the performance of our algorithm and that of jackson and aluru. we refer to the later algorithm as ja. to make this comparison fair, we have implemented the ja algorithm also on the same platform that our algorithm runs on. we have used the sgi/altix ia- machine for all of our experiments. our implementation uses mpi for communication between the processors. we used a test set of million un-paired reads obtained from sequencing a plant genome at cshl. the performance of both the algorithms is measured with various values of k on multiple processors. both the algorithms use the same underlying parallel sorting routines. input reads: short reads, each of size base pairs average user time speed up = x average system time speed up = x average real time speed up = x the user time of our algorithm is also consistently superior compared to the user time of ja. this clearly is because we do much less local computations. in contrast, ja needs to do a lot of local processing, which arises from processing all the received edges, removing redundant ones, and collecting the necessary edges to perform many-to-many communications. we also compare the memory used by both the algorithms. we briefly describe how we obtained the memory reports in our experiments. since the memory used by each processor is different during execution at any given instance we add-up the memory used by each processor and divide by the number of processors and we report this number in our experiments. we obtained the resident memory and shared memory from the top command and averaged it over the number of memory probe samples obtained by top. table gives details of the memory usage of both the algorithms. from these results it is clear that our approach is also efficient compared to the ja algorithm. parbiconstruct uses upto 4x less resident memory compared to the ja algorithm. input reads: short reads, each of size base pairs average efficiency of resident memory across all processors = average efficiency of shared memory across all processors since ja takes a significant amount of time for inputs larger than million, we have compared these algorithms only for input sizes up to million. the experimental results reported in start with at least processors. we however show the scalablity of our algorithm for up to million reads in table table clearly demonstrates the scalability of our algorithm. we make our implementations and all the details of test cases used available at http://trinity.engr.uconn.edu/~vamsik/parbidirected. out-of-core algorithm versus velvet graph building algorithm our aim is to study the computational efficiency of the current velvet's algorithm to build the de bruijn graph and our algorithm. to accomplish this we have modified the code of velvet to stop once it completes building the graph from the reads. this is done as follows. firstly we run the velveth program to complete the building of roadmaps. the code of velvetg is modified such that the program dumps out the graph file after threading of the reads. our out-of-core algorithm generates graph file directly by taking the reads file and the value of k. we have used a low end desktop 32-bit machine with gb ram to demonstrate the scalability of our out-of-core algorithm. our results indicate that the velvet algorithm starts virtual memory trashing for around million reads with k = this trashing leads to massive increase in the page-faults and stalls the program from progressing further. thus the velvet algorithm cannot build large bi-directed graphs. in contrast to velvet our algorithm works with a constant amount of memory and scales well for building large amounts of reads - which we demonstrate in table * indicates that velvet program did not complete and the program was stopped after this time. the program is available at http://trinity.engr.uconn.edu/~vamsik/ex-build-vgraph/.  in this paper we have presented an efficient algorithm to build a bi-directed de bruijn graph, which is a fundamental data structure for any sequence assembly program - based on an eulerian approach. our algorithm is also efficient in parallel and out of core settings. these algorithms can be used in building large scale bi-directed de bruijn graphs. also, our algorithm does not employ any all-to-all communications in a parallel setting and performs better than that of. finally, our out-of-core algorithm can build these graphs with a constant amount of ram, and hence can act as a replacement for the graph construction algorithm employed by velvet. authors' contributions vk designed and implemented the algorithms, and drafted the manuscript. sr participated in designing the algorithms, revised the manuscript, and coordinated all phases of the project. hd also participated in the design of algorithms and contributed towards the figures in the manuscript. mv and vt introduced the sequence assembly problem to the team and provided short read data to validate our method. all the authors read and approved the final manuscript. 
furthermore, our algorithms do not employ any all-to-all communications in a parallel setting and perform better than the prior algorithms. assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. in an earlier work, an o time parallel algorithm has been given for this problem. in this paper we present a Θ time parallel algorithm with a communication complexity that is equal to that of parallel sorting and is not sensitive to Σ. the generality of our algorithm makes it very easy to extend it even to the out-of-core model and in this case it has an optimal i/o complexity of Θblog). we demonstrate the scalability of our parallel algorithm on a sgi/altix computer. the bi-directed de bruijn graph is a fundamental data structure for any sequence assembly program based on eulerian approach. we also provide efficient algorithms for the bi-directed chain compaction problem. these algorithms can be used in building large scale bi-directed de bruijn graphs. efficient algorithms for building these massive de bruijn graphs are very essential in large sequencing projects based on short reads. our algorithms for constructing bi-directed de bruijn graphs are efficient in parallel and out of core settings. algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. we demonstrate the scalability of our sequential out-of-core algorithm by comparing it with the algorithm used by velvet to build the bi-directed de bruijn graph. finally our out-of-core algorithm is extremely memory efficient and can replace the existing graph construction algorithm in velvet. our experiments reveal that our algorithm can build the graph with a constant amount of memory, which clearly outperforms velvet. the first class uses an overlap/string graph and the second type uses a de bruijn graph. however with the recent advances in short read sequencing technology, de bruijn graph based algorithms seem to play a vital role in practice.
 assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. the first class uses an overlap/string graph and the second type uses a de bruijn graph. however with the recent advances in short read sequencing technology, de bruijn graph based algorithms seem to play a vital role in practice. efficient algorithms for building these massive de bruijn graphs are very essential in large sequencing projects based on short reads. in an earlier work, an o time parallel algorithm has been given for this problem. here n is the size of the input and p is the number of processors. this algorithm enumerates all possible bi-directed edges which can overlap with a node and ends up generating Θ messages.  in this paper we present a Θ time parallel algorithm with a communication complexity that is equal to that of parallel sorting and is not sensitive to Σ. the generality of our algorithm makes it very easy to extend it even to the out-of-core model and in this case it has an optimal i/o complexity of Θblog). we demonstrate the scalability of our parallel algorithm on a sgi/altix computer. a comparison of our algorithm with the previous approaches reveals that our algorithm is faster - both asymptotically and practically. we demonstrate the scalability of our sequential out-of-core algorithm by comparing it with the algorithm used by velvet to build the bi-directed de bruijn graph. our experiments reveal that our algorithm can build the graph with a constant amount of memory, which clearly outperforms velvet. we also provide efficient algorithms for the bi-directed chain compaction problem.  the bi-directed de bruijn graph is a fundamental data structure for any sequence assembly program based on eulerian approach. our algorithms for constructing bi-directed de bruijn graphs are efficient in parallel and out of core settings. these algorithms can be used in building large scale bi-directed de bruijn graphs. furthermore, our algorithms do not employ any all-to-all communications in a parallel setting and perform better than the prior algorithms. finally our out-of-core algorithm is extremely memory efficient and can replace the existing graph construction algorithm in velvet. 