DALIGNER: Fast and sensitive detection of all pairwise local alignments

The first phase of the Dazzler assembler compares every read in the trimmed Dazzler database (DB) against every other read in the trimmed DB, seeking significant local alignments between them. In an old-fashioned OLC assembler, one would look, more restrictively, for overlaps between reads. But one can use local alignments to detect artifacts such as chimeric reads and unclipped adapter sequence by looking for consistent alignment terminations within a read, and one can also detect and annotate repetitive elements of the genome covered within a read by looking for “pile-ups” of alignments. Removing the artifacts and knowing the repetitive regions covered by a read is a huge advantage prior to assembling the reads. Indeed, the dazzler assembler employes several downstream phases specifically to remove artifacts, correct reads, and annotate repetitive elements prior to building a string graph which is the modern analog of the layout phase for an OLC architecture.

You can get the source code for the DALIGNER module on Github here. Grabbing the code and uttering “make” should produce 9 programs: daligner, LAsort, LAmerge, LAshow, LAcat, LAsplit, LAcheck, HPCdaligner, and HPCmapper.

Ideally one would like to call the alignment finder, daligner, with a DB, e.g. “daligner MyDB“, and after some computing it would output a file encoding all the found local alignments. Unfortunately for big projects the amount of memory and CPU time required make this impossible. For example, on the Pacbio 54X human data set, daligner took 15,600 CPU hours on our modest 480 core HPC cluster, and as a monolithic run would have required at least 12Tb of memory! I could start apologizing, but consider that the only other program that can compare reads at a 12-15% error rate, BLASR, took 404,000 CPU hours, and only delivered overlaps. Indeed, a primary reason for releasing daligner now, and not waiting to release a complete end-to-end assembler is precisely to provide the bioinformatics community with a feasible way to compute alignments for Pacbio data at this scale. While we’ve embedded daligner within our database framework, it is easy to grab daligner‘s output in an ASCII format and then use that in an HGAP pipeline (which is the only current end to end assembler publicly available).

So given the scale of the required computation we have to “bite the bullet” and take a job parallel, HPC approach to effect an all-against-all comparison of the trimmed DB. So as a running example, let’s suppose you’ve set up a DB that is partitioned and optionally has a “dust” track (see this blog post) with a command sequence like:

fasta2DB DB MyData1.fasta MyData2.fasta ...
DBdust DB
DBsplit -x1000 DB

Suppose for simplicity that DB splits into 3 blocks. Then calling HPCdaligner on the DB will produce a UNIX shell script that contains all the commands needed to effect the all against all comparison. For example, “HPCdaligner DB” produces the script:

# Daligner jobs (3)
daligner DB.1 DB.1
daligner DB.2 DB.1 DB.2
daligner DB.3 DB.1 DB.2 DB.3
# Initial sort jobs (9)
LAsort DB.1.DB.1.*.las && LAmerge L1.1.1 DB.1.DB.1.*.S.las && rm DB.1.DB.1.*.las
LAsort DB.1.DB.2.*.las && LAmerge L1.1.2 DB.1.DB.2.*.S.las && rm DB.1.DB.2.*.las
LAsort DB.1.DB.3.*.las && LAmerge L1.1.3 DB.1.DB.3.*.S.las && rm DB.1.DB.3.*.las
LAsort DB.2.DB.1.*.las && LAmerge L1.2.1 DB.2.DB.1.*.S.las && rm DB.2.DB.1.*.las

# Level 1 merge jobs (3)
LAmerge DB.1 L1.1.*.las && rm L1.1.*.las
LAmerge DB.2 L1.2.*.las && rm L1.2.*.las
LAmerge DB.3 L1.3.*.las && rm L1.3.*.las

Each non-comment line of the script should be submitted to your cluster as a job, and all the jobs following one of the 3 comment lines can be run in parallel, but these 3 batches of job groups need to be run in sequence. That is, the 3 “Daligner” jobs can be run in parallel as a group, and once they have all completed, one can then run the 9 “Initial sort” jobs in parallel as a group, and finally the “Level 1 merge” jobs as a group. And of course, for a small script like this one, you could just invoke the shell on the script and let the jobs run sequentially on your desktop, e.g. “HPCdaligner DB | csh“.

When all the jobs of our sample script have completed there will be 3 sorted alignment files DB.1.las, DB.2.las, DB.3.las that encode the alignments found for the reads in each of the 3 trimmed DB blocks, respectively. To describe the contents of these 3 files precisely, one must first know that for each alignment, a .las-file records:

a[ab,ae] x bcomp[bb,be]

where a and b are the indices (in the trimmed DB) of the reads that overlap, comp indicates whether the b-read is from the same or opposite strand, and [ab,ae] and [bb,be] are the intervals of a and bcomp, respectively, that align. It is further the case that an alignment between reads a and b results in two alignment records, one for a versus b and another for b versus a. In addition, a series of trace points is retained with each alignment record to facilitate the rapid delivery of an optimal alignment between the relevant intervals of the reads. We can now explain that the output file DB.n.las contains all the overlap records for which the first read a is in the trimmed block DB.n and these records further occur in sorted order of a, then b, then comp, and finally ab. What this means is that all the alignments involving a given a-read occur in a contiguous interval of the output files permitting easy and job parallel computation in the downstream phases for chimer detection, read correction, repeat analysis, etc..

The HPCdaligner UNIX shell script employes the three commands daligner, LAsort, and LAmerge to produce the sorted and partitioned .las files for each of the N blocks of a hypothetical database D as follows:

  • “Daligner” step: Every block is compared against every other block by calling daligner on every pair D.x and D.y such that y≤x. A call such as “daligner D.x D.y1 .. D.yk” performs k comparisons of block D.x versus each block D.yi and does so with a compiled number of threads T (default 4). Each of these pairwise block comparisons produces 2T unsorted .las files D.x.D.y.[C|N]t.las and if x > y, an additional 2T unsorted .las files D.y.D.x.[C|N]t.las. The file D.x.D.y.Ot.las contains every alignment produced by thread t where the a-read is in D.x and the b-read is in D.y and is in orientation O. In total (N+1)N/2 blocks are compared and 2N2T .las files result.
  • “Initial sort” step: The 2T .las files for each block pair x,y, are sorted and merged into a single sorted .las file. The 2T files are first sorted with LAsort, where for each unsorted file U.las the command produces the sorted overlap file U.S.las. These sorted .S.las files are then merged into a single sorted file, L1.x.y.las, with LAmerge and afterwords removed. At the end of this step there are exactly N2 sorted .las files, one for each block pair.
  • “Level k merge” steps: In a sequence of O(log N) levels the N files L1.x.*.las for a given block x are merged by LAmerge into a single .las file, D.x.las. At level 1, the N sorted files for a block are merged in groups of up to 25 resulting in ⌊N/25⌋ files, that in level 2 are merged in groups of up to 25, resulting in ⌊N/625⌋ files, and so on until only one file D.x.las remains. Even big projects involve less than 625 blocks, so typically only one or at most two merge levels are required.

For extraordinarily large projects the computation can be performed in stages as new data is added to the database, thus amortizing the cost of finding alignments over the interval of data production. For example, suppose you have a really big project going and that thus far the DB has 78 blocks in its current partition. Executing the script produced by “HPCdaligner DB 1-77" will compare blocks 1 to 77 versus each other producing files DB.1.las through DB.77.las. Note carefully that the last block, 78, was not included, because it is a partial block. Later on suppose you’ve added more data and now have 144 blocks. Then executing the script produced by “HPCdaligner DB 78-143” will compare blocks 78 to 143 against each other and against the earlier blocks 1 through 77, updating DB.1.las through DB.77.las and creating DB.78.las through DB.144.las. And so on. The only restrictions are that (a) one must add the blocks in sequential order once only, and (b) one should never add the last, partial block until the very last increment. By submitting each new complete block as it appears, I figure one could keep up with data production for say a 100X shotgun of D. melanogaster on a decent laptop.

The command LAshow produces an ASCII display of all or a selected subset of the alignments encoded in a given .las file, sorted or unsorted. One can view just the read indices and their aligned intervals, one per line, or a line rendering of the relationship between the two reads, or a complete BLAST-style alignment of each local alignment where one has several options for customizing the display. In addition to permitting one to browse local alignments, the ASCII output can also be fed into a python or pearl script that converts the information to a from that can be input to an external program of your choosing, such as the read correction step of the HGAP assembler.

The LAcat and LAsplit commands allow one to effectively change the partition of the .las files for a project should it ever be necessary. Suppose the .las files D.1.las, D.2.las, …, D.N.las have been computed for a database D.db that has been partitioned into N blocks. “LAcat D.# >E.las” will find all the .las files of the form D.#.las and stream the conceptual concatenation of all the .las files in numeric order to the standard output, in this case to the file E.las. In the other direction, “LAsplit F.# N <E.las” will split E.las as evenly as possible into N block files, F.1.las, F.2.las, …, F.N.las subject to the restriction that the alignments involving a given a-read are all in the same file. Note that F.x.las does not necessarily equal the original D.x.las, as the a-reads in F.x.las may not be the same as the reads in a given block, D.x.db, because the splitting criteria for LAsplit and DBsplit are not the same. To get exactly the same files back, one should instead utter “LAsplit F.#.las D.db <E.las” or more tersely “LAsplit F.# D <E.las” that splits the piped input according to the partitioning of database D !  Finally, observe that if you want to repartition the DB D and also all the D.#.las files, first call DBsplit on D, and afterwords call “LAcat D.# | LAsplit D.# D” to redistribute the alignment records into .las files according to the new partitioning.

Lastly, the command LAcheck reads through the .las files given to it and checks them for structural integrity, i.e. do they reasonably encode a properly formatted .las file? We find this command useful in ensuring that every stage of a large HPCdaligner script has been properly executed. In processes involving thousands of jobs, it is not unusual for one or two to go “haywire”. So while we didn’t build it into the HPCdaligner scripts, we strongly recommend that you run LAcheck on .las files throughout the process to make sure all is well. Doing so is standard operating procedure for our assembly group.

A precise, detailed, and up-to-date command reference can be found here.



9 thoughts on “DALIGNER: Fast and sensitive detection of all pairwise local alignments

  1. Pingback: ISMB 2014 Link Roundup

  2. Hello
    First, I am really impressed by the simplicity of the Database organisation and the downstream tools. That should have been the way PacBio themselves should have organised the data …..

    I encountered a problem though and wondered where this derived from. I generated a small database with one cell only (3 .h5 files) and dust-masked them. I further organised them in blocks with -x1000 as threshold. Since I have only 1 smart-cell it resulted in only block as well.

    Attempting to drive the DALIGNER

    HPCdaligner OAK_DB.db | csh

    Resulted in an error:

    daligner: Out of memory (Allocating dazzler hit vectors)

    Which is strange since it only used max. 5GB of memory and I am currently on a 256GB RAM machine ….

      • Daligner was using 5Gbp for the k-mer indexes it builds of the blocks. But then it merges these looking for common k-mers into a “hit list” that overflowed. To explain further, If there are lots of copies of a low-complexity k-mer, e.g AAAAAAAAAAAAAA, say 100 in each block, then 10,000 hits are generated. When you used the -d option you effectively masked all the low complexity k-mers and hence it ran, although doing it manually should not have been necessary. In general, one should suppress over represented tuples using the -t option when working with complex, repetitive genomesi.e. use -t10 or -t20.

        When I make the next minor update I will program in a bit more informative error message. Thanks

  3. Pingback: In DALIGN Paper, Gene Myers Delivers a Major Blow to His Biggest Competitor « Homolog.us – Bioinformatics

  4. Hello
    I would have another question, parsing the DALIGNER output. Assuming, we actually do not mask anything or put any size restrictions than we always expect A x B and B x A to occur. If I check by hand this is the case and the total number of queries and target is equal supporting this assumption.
    What I was wondering though: the trace points are sometimes different, are the coordinates as well ?

    E.g. would A x B [100..200] always (and I want to emphasize that) lead to B x A [100..200] or might we experience as well e.g. B x A [99..202] ?

  5. If there is an overlap between A and B, then B versus A is always reported. The intervals are the same. But for reads that are *complemented* with respect to each other, then the overlap intervals are described from A’s view if it is AxB, and from B’s view if it is BxA, and in that case the coordinates into A and B appear different. The trace points, on the other hand are actually distinct in the two overlap records because when A is first, we want a trace point every, say 100bp, of A, and when B is first we want a trace point every 100bp of B.

  6. Hello,
    I am wondering :
    1- if there is a way to use HPCmapper for mapping contig on reference?;
    2- can we use pacbio reads without qv value. The absence of gv value may affect the quality of alignement ?
    3- In witch step of alignemen the aligner part use quality of pacbio reads?.

    Thank you for your response and happy new year


    • Hi, I waited a bit to reply as I realized that I could make things a little bit more general with the introduction of .dam data sets and the upgraded capabilities of the daligner. So:

    • 1. Yes
    • 2. he daligner does not use QV values, so you do not need to add QV’s to a database unless you plan on running PacBios Quiver program at the backend of whatever pipeline you put together.
    • 3. As I said in 2. none of my tools use them for anything. I support them (in the database) because I figure there are users out there that will want to Quiver the final assembly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s