English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Assembling genomic sequences from a set of overlapping reads is one of themost fundamental problems in computational biology. Algorithms addressing theassembly problem fall into two broad categories -- based on the data structureswhich they employ. The first class uses an overlap/string graph and the secondtype uses a de Bruijn graph. However with the recent advances in short readsequencing technology, de Bruijn graph based algorithms seem to play a vitalrole in practice.  Efficient algorithms for building these massive de Bruijn graphs are veryessential in large sequencing projects based on short reads. In Jackson et. al.ICPP-2008, an $O(n/p)$ time parallel algorithm has been given for this problem.Here $n$ is the size of the input and $p$ is the number of processors. Thisalgorithm enumerates all possible bi-directed edges which can overlap with anode and ends up generating $\Theta(n\Sigma)$ messages.  In this paper we present a $\Theta(n/p)$ time parallel algorithm with acommunication complexity equal to that of parallel sorting and is not sensitiveto $\Sigma$. The generality of our algorithm makes it very easy to extend iteven to the out-of-core model and in this case it has an optimal I/O complexityof $\Theta(\frac{n\log(n/B)}{B\log(M/B)})$. We demonstrate the scalability ofour parallel algorithm on a SGI/Altix computer. A comparison of our algorithmwith that of Jackson et. al. ICPP-2008 reveals that our algorithm is faster. Wealso provide efficient algorithms for the bi-directed chain compaction problem.

Efficient Parallel and Out of Core Algorithms for Constructing Large Bi-directed de Bruijn Graphs