File: murasaki.txt

package info (click to toggle)
murasaki 1.68.6-6
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 1,928 kB
  • ctags: 3,100
  • sloc: cpp: 16,010; perl: 8,365; makefile: 186
file content (525 lines) | stat: -rw-r--r-- 21,973 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
NAME
    murasaki - compute anchors between multiple sequences

SYNOPSIS
     murasaki [OPTIONS] -p[pattern] seq1.fa seq2.gbk [seq3.raw ...] #compute anchors between seq1.fa and seq2.gbk using [pattern]
     mpirun murasaki [OPTIONS] -p[pattern] seq1.fa seq2.gbk [seq3.raw ...] #compute anchors between seq1.fa and seq2.gbk using [pattern] in parallel via MPI

DESCRIPTION
    Murasaki generates anchors based on all supplied sequences based on the
    user supplied pattern and hash tables. Essentially each base of each
    sequence is masked by the pattern, forming a seed that is used to
    generate a hash. The location of the seed is stored in the hash table.
    Once all seeds have been hashed and stored, Murasaki scans the hash
    table, generating anchors for all matching seeds. An anchor refers to a
    set intervals across a subset of the input sequences. These are stored
    in name.anchors files, and described in "FILE FORMATS". By default
    anchors are maximally extended until their minimum pairwise ungapped
    alignment score drops below a threshold in the same fashion the X-drop
    parameter in BLAST and BLAST-like searches.

  PATTERNS
    Murasaki uses spaced seed patterns to in considering seeds. A spaced
    seed pattern is typically expressed as a string of 1s and 0s necessarily
    starting and ending with a 1. 1s indicate that this base is considered
    part of the seed, while bases at 0 positions are not. For example with a
    pattern "1011" the sequence "ACGT" would match sequences "AGGT" and
    "ATGT" but not "ACTT". The number of 1s in the pattern is known as the
    "weight" of the pattern, and the number of 1s and 0s combined is the
    "length" of the pattern. Murasaki allows the use of any arbitrary
    pattern expressed as a string of 1s and 0s, and also interprets patterns
    of the form "x:y" to mean a "random pattern of weight *x* and length
    *y*."

    The choice of pattern obviously has an impact on sensitivity and
    specificity, but whether one pattern is "better" than another depends on
    the application and the input sequences under consideration. Calcuating
    "maximally sensitive spaced seed patterns" is a computationally
    difficult problem and there are a number of research papers describing
    various methods for approximation ("RELATED READING"). In general,
    however, "heavier" spaced seed patterns are less sensitive, but more
    specific, than lighter seeds. Anecdotally we find that seeds with
    weights approximately 60% to 75% (with lengths around 24 for bacteria,
    and 36 to 48 for mammals) are good for most applications. Extremely
    similar species (for example human and chimp) benefit from longer,
    heavier, seeds.

  HASH FUNCTIONS
    Hash functions (as well as hash parameters) are generated automatically
    based the system environment and input sequences. There are essentially
    two types of hash functions available in Murasaki: adaptive and
    cryptoraphic hashes. The adaptive hashes are XOR combinations of various
    bitwise shifts of the seed designed by analyzing the spaced seed pattern
    to maximize the entropy of the resulting hash. Cryptographic hashes are
    available via the CryptoPP library and use the *entire* spaced seed
    pattern to generate a hash using one of the common cryptographic hashes
    like MD5 or SHA-1. The adaptive hash functions are almost always faster
    and more efficient than MD5 and SHA-1, but the cryptographic functions
    are available for reference and may be useful as an alternative in the
    unlikely event you're dealing with an environment where the adaptive
    hasher is unsuitable (for example a sequence consisting of only A and T
    (leaving 1 out of every 2 bits unitilized)).

  MEMORY SCALING
    Murasaki can take a lot of memory. Storing the location of each seed in
    the hash table is the most costly part of the operation, requiring
    approximately "ceil(log_2(N))" bits per seed where "N" is the total
    sequence length. Locations are, by default, stored in a bitpacked format
    to approach theoretical minimum. The second most costly element is the
    hash table structure, where each bucket carries a small overhead and
    unused are simply wasted space. More hash table buckets (i.e. a longer
    hash table) decreases the expected number of collisions, leading to
    faster executation time. Therefore Murasaki tries to use as many buckets
    as possible by inspecting the available system memory and using as much
    as it can while still storing all the seed locations. If this automatic
    scaling is ineffective, setting the hash table size directly via the
    --hashbits|-b options can force a specific hash table size. If the
    memory of one computer is insufficient to store the desired hash table,
    PARALLELIZATION can be used to distribute the hash table across multiple
    computers.

  PARALLELIZATION
    Murasaki is designed to run in parallel using MPI. Consult the
    documentation for the specific variations of your MPI implementation,
    however in general the executation method looks like:

     mpirun [MPI options] murasaki [murasaki options] -p[pattern] [seq1 ...]

    Murasaki in parallel divides the number of processors available (NP)
    into two groups: hasher nodes and storage nodes. The storage nodes
    divide the hash table between each themselves, each being responsible
    for a different part of the table. Hasher nodes divide the input
    sequence in between themselves, each hashing a separate portion of the
    input sequence, and passing the seed location to the appropriate storage
    node for storage. When all the hasher nodes are finished hashing, the
    storage nodes scan their portion of hash table and pass matching sets of
    seeds to a hasher node where they are assembled into anchors and
    extended. Finally all the hasher nodes combine their independent anchor
    sets into one final set in "ceil(log_2(H))" iterations (where "H" is the
    number of hasher nodes), with each hasher node number 2h passing its
    anchors to hasher number 2h-1 at each iteration.

    Because almost none of the parallelization steps require communication
    between *all* nodes, and each seed and each anchor can be processed in
    parallel, Murasaki scales very well in parallel, running approximately
    twice as fast when twice as many nodes are available. Furthermore, the
    hash table is automatically grown to take advantage of the combined
    memory from multiple machines.

OPTIONS
    Most options can be specified in their long form (e.g. "--directory out"
    or "--directory=out") or short form (e.g. "-dout"). Options marked by
    <S> expect a string, <D> an integer, <F> a float, and <B> a boolean
    value ("yes/on/true/1" for true, "no/off/false/0" for false). Most
    booleans can omit the value, toggling the value from whatever it was to
    the opposite.

    Murasaki has a lot of options. Here we've separated them into categories
    to help distinguish the scope of the various options, however in certain
    situations certain option choices may have onforseen consequences, and
    of course ultimately if the specified output is *huge*, the required
    runtime will necessarily be *long*. It is a mistake to think that
    everything outside of the "tuning options" in Performance section has no
    bearing on performance.

  Anchor parameter related options
    These options shape what is considered an "anchor".

    --pattern|-p <S>
         specifies the seed pattern (eg. 11101001010011011). using the format
         C<[<w>:<l>]> automatically generates a random pattern of weight <w>
         and length <l>

    --repeatmask|-r <B>
        Skip repeat masked data (ie: lowercase atgc). Be aware that some
        sequence files are distributed purely in lower case.

    --seedfilter|-f <D>
        Skip seeds that occur more than N times. Exceptionally slow. See
        --hashfilter for a faster approximation.

    --hashfilter|-m <D>
        Like --seedfilter but works on hash keys instead of seeds. May cause
        some collateral damage to otherwise unique seeds, but it's faster.

    --skipfwd|-F <B>
        Don't hash/match the forward strands.

    --skiprev|-R <B>
        Don't hash/match the reverse complement strands.

    --skip1to1|-1 <B>
        Skip matches along the 1:1 line (good for comparing to self).

    --hashonly|-Q <B>
        Hash Only. No anchor output, just statistics.

    --hashskip|-S <D>
        Hashes every n bases. Default is 1 (i.e. hashing all positions). Not
        supplying any argument increments the skip amount by 1.

    --join|-j <D>
        Join anchors within n bases of eachother (default: 0). Specifying a
        negative D implies -D*patternLength.

    --bitscore|-B <B>
        toggles compututation of a bitscore for all anchors (default is on).

    --seedterms|-T <B>
        toggles retention of seed terms (defaults to off). These are
        necessary for computing TF-IDF scores).

    --sectime|-e <B>
        Always display times in seconds as opposed to human readable "1d 3h
        45m 5s" style times.

    --mergefilter|-Y <D>
        Filter out matches which would would cause more than *D* many
        anchors to be generated from 1 seed (default -Y100). Use -Y0 to
        disable.

    --scorefilter <D>
        Set a minimum ungapped score for seeds.

    --rifts|-/ <D>
        Allow anchors to skip D sequences (default 0).

    --islands|-% <D>
        Same as --rifts=S-D (where S is number of input seqs).

    --fuzzyextend|-z <B>
        Enable (default) or disable fuzzy extension (i.e. ungapped
        alignment) of anchors.

    --fuzzyextendlosslimit|-Z <D>
        Set the cutoff at which to stop extending fuzzy hits (ie. the BLAST
        X parameter).

    --gappedanchors <B>
        Use gapped (true) or ungapped (false (default)) anchors.

    --scorebyminimumpair <B>
        Do anchor scoring by minimum pair when appropriate (default).
        Alternative is arithmatic mean (seldom useful, but theoretically
        faster). =item --rifts|-/ <D>

        Allow anchors to skip D sequences (default 0).

    --islands|-% <D>
        Same as --rifts=S-D (where S is number of input seqs).

    --fuzzyextend|-z <B>
        Enable (default) or disable fuzzy extension (i.e. ungapped
        alignment) of anchors.

    --fuzzyextendlosslimit|-Z <D>
        Set the cutoff at which to stop extending fuzzy hits (ie. the BLAST
        X parameter).

    --gappedanchors <B>
        Use gapped (true) or ungapped (false (default)) anchors.

    --scorebyminimumpair <B>
        Do anchor scoring by minimum pair when appropriate (default).
        Alternative is arithmatic mean (seldom useful, but theoretically
        faster).

  Output options
    These options primarily affect what data is output where.

    --directory|-d <S>
         output directory (default: output)

    --name|-n <S>
         alignment name (default: test)

    --repeatmap|-i <B>
        Toggles keeping of a repeat map when --mergefilter is used (defaults
        to yes).

    --histogram|-H <D>
        Histogram computation level: (-H alone implies -H1)

        0 - no histogram (default)
        1 - basic bucketsize/bucketcount histogram data
        2 - bucket-based scores to anchors.detils
        3 - perbucket count data
        4 - perbucket + perpattern count data

        Any values above 2 are purely explorartory and can result in massive
        output files.

    --tfidf|-k <B>
        Perform accurate tfidf scoring from within murasaki (requires extra
        memory at anchor generation time). Default is no.

  Performance/tuning options
    These options primarily affect performance, and don't (in general)
    impact output.

    --quickhash|-q <D>
         specify a hashing function:

        0 - adaptive with S-boxes (default when there's plenty of hash table
        to spare)
        1 - don't pack bits to make hash (use first word only)
        2 - naively use the first hashbits worth of pattern
        3 - adaptivevely find a good hash (default)
        **experimental CryptoPP hashes**
        4 - MD5
        5 - SHA1
        6 - Whirlpool
        7 - CRC-32
        8 - Adler-32

        Note: 3 and 0 are the only "recommended" hash functions, and the
        only ones automatically selected. The others are provided merely for
        reference. 1, 7, and 8 aren't even expected to utilize the entire
        hash space.

    --hashbits|-b <D>
        use D bit hashes (for n's of 1 to WORDSIZE. default 26)

    --hashtype|-t <S>
        select hash table data structure to use:

        OpenHash - open sub-word packing of hashbits (default when there's
        plenty of hash table to spare)
        EcoHash - chained sub-word packing of hashbits (default)
        ArrayHash - malloc/realloc (fast but fragmentation-prone)
        MSetHash - memory exorbanant, almost pointless.

    --probing <D>
        0 - linear, 1 - quadratic (default). Only applicable for
        --hashtype=OpenHash.

    --hitfilter|-h <D>
        Minimum number of hits to be outputted as an anchor (default 1). In
        PatternHunter this is 2.

    --rseed|-s <D>
        Random number seed for non-deterministic algorithms (ie: adative
        hash function generation). If you're doing any performance
        comparisons, it's probably imperative that you use the same seed for
        each run of the same settings. Default is obtained from time() (ie:
        seconds since 1970).

    --memory|-M [<F>|<S>]
        Set the target amount of total memory (either in gb or as % total
        memory).

    --reverseotf|-o <B>
        Generate reverse complement on the fly (defaults to on). Turning
        this off precomputes the all reverse complement strands and stores
        them in memory, which rarely provides a measurable performance
        improvement.

    --binaryseq <B>
        Enable (default) or disable binary sequence read/write

   Adaptive hash function related:
    Performance options related to adaptive hash function generation.

    --hasherFairEntropy <B>
        Use more balanced entropy estimation (default: yes).

    --hasherCorrelationAdjust <B>
        Adjust entropy estimates for nearby sources assuming some
        correlation (default: yes).

    --hasherTargetGACycles <D>
        Adaptive hash function generation genetic algorithm cycle cutoff.

    --hasherEntropyAgro <F>
        How aggressive to be about pursuing maximum entropy hash functions
        (takes a real. default is 1).

  MPI Specific:
    --hashers|-A [<F>|<D>]
        Specify the number of processes to be used as hashers (only applies
        to MPI. If a number between 0 and 1 it refers to a ratio of np).

    --localhash|-K <B>
        Perform hashing locally on each storage node rather than sending it
        over the network (helpful for slow networks).

    --mpidistro|-L <B>
        Toggles use of MPI to distribute sequence data over (if the sequence
        is available on local disk on each node then turning this off may
        potentially accerlate the intial sequence loading).

    --waittoanchor|-w <B>
        Postpone actual anchor computation until all location sets have been
        received (as opposed to trying to work between receiving seed
        packets).

    --buffers|-u <D>
        Maximum number of unfinished buffers to allow while message passing
        (0 means unlimited). Default is set based on the number of nodes
        participating. MPI can crash or perform *very* poorly if this value
        is too high.

    --nobuffers|-U <B>
        Same as --buffers=1.

    --bigfirst|-I <B>
        Assign hashers to large memory nodes first.

    --hostbalance|-l <B>

        If yes (default): spread out hashers evenly among all nodes.
        If no: ignore host name when assigning jobs.

    --memorybalance|-a <B>

        If yes (default): balance hash storage between nodes based on the
        amount of available ram.
        If no: distribute storage evently. This more likely to achieve
        optimal run times, but might not utilize memory as efficiently.

    --distmerge|-< <B>

        if yes (default): during the merge step, storage nodes send seeds to
        any available hasher.
        if no: send all seeds to one node only.

    --distcollect|-> <B>

        if yes (default): collect anchor data from all hashers.
        if no: send all seeds to the final assembly node only.

    --mpiredirectoutput <B>

        if yes (default): each rank redirects its stdout/stderr to a
        separate file (murasaki-mpiout-*N*).
        if no: do what comes naturally (ie: managed by mpirun (for OpenMPI
        see --output-filename and --tag-output in mpirun(1))).

    --keepstdoe <B>
        Don't erase the murasaki-mpiout files on success.

    --sysvipc|-V <B>
        Use System V IPC to negotiate shared memory regions (saves memory
        when one host runs multiple nodes). Default is true.

  Universal options:
    --verbose|-v
        Increases verbosity.

    --version|-V
        Prints version information and quits.

    --help|-?
        Prints a help message and quits.

FILE FORMATS
    Murasaki has a wide array of output files, the formats of most of which
    are intended to be intuitive. All output files are prefixed by the value
    of the --name parameter. The primary output file formats are described
    here. Files are line based and tab delimited unless otherwise specified.

  .seqs
    The .seqs shows what sequences were used as input, 1 per line. This file
    gets used by various programs in conjunction with the .anchors file, so
    it's generally important that the contents reflect the correct sequence
    files. Moving anchor results between computers might result in a change
    of paths, requiring the user to update the .seqs file. As an
    alternative, always using relative paths can alleviate this problem.

  .anchors files
    These files are 1 anchor per line, with a 3-tuple per sequence. Each
    touple represents the start and stop coordinates and strand of the
    anchored interval on each sequence. The sequence order matches that of
    the order in the .seqs file. The coordinates are structured such that 1
    refers to the first base in the sequence, 2 to the second, etc. Negative
    values refer to the reverse complement sequence where -1 is the *last*
    base of the reverse complement sequence (ie: the complement first base
    in the forward sequence). The "strand" element is a '+' or '-' that
    merely matches the sign of the coordinates (this is redundant
    information, but kept to make parsing or filtering simpler).

    For examle:

     1       18     +       -1      -18       -

    This line describes an anchor where the first 18 bases of the first
    sequence match the first 18 bases of the reverse complement of the
    second sequence.

  .anchors.details
    This is an antiquated file format, but used by GMV to calculate
    statistics like TF-IDF scores, and has been kept around for that reason.
    The .anchors.details file has the same format and information as the
    .anchors file, however after the anchor touples are two more terms: a
    score, and a comma (,) delimited list of term and count pairs (written
    "term:count"). The score and count data might be varied depending on the
    "--histogram" option choices.

  .anchors.bitscore
    The term "bitscore" here is a misnomer, but maintained for historical
    reasons. In reality, this file contains the mean number of matching
    bases and length of each anchor (corresponding line by line to the
    .anchors file).

  .stats.tfidf
    Contains anchor TF-IDF scores (corresponding line by line to the
    .anchors file).

  .histogram
    Contains a simple histogram of the hash table usage. The first field is
    the bucket size, and the second is the frequency. For example a
    .histogram file like this:

     1  24
     2  1

    Would indicate that there were 24 hash buckets that stored only 1
    location (i.e. 24 unique seeds), and 1 hash bucket stored 2 locations
    (i.e. 1 seed that matched 2 locations (or 2 non-matching seeds that
    resulted in a hash collision)).

  .options
    Maintains a record of the options used when running Murasaki.

  .repeats
    The .repeats file stores a record of "repeats" as defined by the
    --mergefilter option (i.e. seeds that would have have induced more
    anchors than permitted). In this file, each repeat record is separated
    by a blank line. A repeat record looks like this:

     R: G.GCCTTT.T.ACT.CACAA..AT
     0: 2145540494 -425039256 -113794380 1998323403
     1: 2480929222 -1874514626 2543723555 -2550045172

    The first line (always prefixed "R:") shows the repeating seed itself
    (where the . are the bases masked by the pattern). The subsequent lines
    show where these seeds occured in the input sequences (in the first (0)
    and second (1) sequences). Note that if there are no hits in a
    particular sequence, it doesn't include a blank line for that sequence.
    For example:

     R: G.GCCTTT.T.ACT.CACAA..AT
     0: 2145540494 -425039256 -113794380 1998323403
     2: 2480929222 -1874514626 2543723555 -2550045172

    is also a valid .repeats file.

LICENSE
    GNU General Public License, version 3 (GPLv3)

AVAILABILITY
    <http://murasaki.sourceforge.net>

AUTHOR
    Kris Popendorf <krisp@dna.bio.keio.ac.jp>

SEE ALSO
    mbfa(1), geneparse(1)

  RELATED READING
    M. Csuros and B. Ma, "Rapid Homology Search with Two-Stage Extension and
    Daughter Seeds" (2005).
    F. P. Preparata and L. Zhang and K. W. Choi, "Quick, practical selection
    of effective seeds for homology search" (2005).
    KP Choi, et. al., "Good spaced seeds for homology search" (2004).