Debian Codegraph @

doc/murasaki.txt

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 NAME
2 murasaki - compute anchors between multiple sequences
3
4 SYNOPSIS
5 murasaki [OPTIONS] -p[pattern] seq1.fa seq2.gbk [seq3.raw ...] #compute anchors between seq1.fa and seq2.gbk using [pattern]
6 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
7
8 DESCRIPTION
9 Murasaki generates anchors based on all supplied sequences based on the
10 user supplied pattern and hash tables. Essentially each base of each
11 sequence is masked by the pattern, forming a seed that is used to
12 generate a hash. The location of the seed is stored in the hash table.
13 Once all seeds have been hashed and stored, Murasaki scans the hash
14 table, generating anchors for all matching seeds. An anchor refers to a
15 set intervals across a subset of the input sequences. These are stored
16 in name.anchors files, and described in "FILE FORMATS". By default
17 anchors are maximally extended until their minimum pairwise ungapped
18 alignment score drops below a threshold in the same fashion the X-drop
19 parameter in BLAST and BLAST-like searches.
20
21 PATTERNS
22 Murasaki uses spaced seed patterns to in considering seeds. A spaced
23 seed pattern is typically expressed as a string of 1s and 0s necessarily
24 starting and ending with a 1. 1s indicate that this base is considered
25 part of the seed, while bases at 0 positions are not. For example with a
26 pattern "1011" the sequence "ACGT" would match sequences "AGGT" and
27 "ATGT" but not "ACTT". The number of 1s in the pattern is known as the
28 "weight" of the pattern, and the number of 1s and 0s combined is the
29 "length" of the pattern. Murasaki allows the use of any arbitrary
30 pattern expressed as a string of 1s and 0s, and also interprets patterns
31 of the form "x:y" to mean a "random pattern of weight *x* and length
32 *y*."
33
34 The choice of pattern obviously has an impact on sensitivity and
35 specificity, but whether one pattern is "better" than another depends on
36 the application and the input sequences under consideration. Calcuating
37 "maximally sensitive spaced seed patterns" is a computationally
38 difficult problem and there are a number of research papers describing
39 various methods for approximation ("RELATED READING"). In general,
40 however, "heavier" spaced seed patterns are less sensitive, but more
41 specific, than lighter seeds. Anecdotally we find that seeds with
42 weights approximately 60% to 75% (with lengths around 24 for bacteria,
43 and 36 to 48 for mammals) are good for most applications. Extremely
44 similar species (for example human and chimp) benefit from longer,
45 heavier, seeds.
46
47 HASH FUNCTIONS
48 Hash functions (as well as hash parameters) are generated automatically
49 based the system environment and input sequences. There are essentially
50 two types of hash functions available in Murasaki: adaptive and
51 cryptoraphic hashes. The adaptive hashes are XOR combinations of various
52 bitwise shifts of the seed designed by analyzing the spaced seed pattern
53 to maximize the entropy of the resulting hash. Cryptographic hashes are
54 available via the CryptoPP library and use the *entire* spaced seed
55 pattern to generate a hash using one of the common cryptographic hashes
56 like MD5 or SHA-1. The adaptive hash functions are almost always faster
57 and more efficient than MD5 and SHA-1, but the cryptographic functions
58 are available for reference and may be useful as an alternative in the
59 unlikely event you're dealing with an environment where the adaptive
60 hasher is unsuitable (for example a sequence consisting of only A and T
61 (leaving 1 out of every 2 bits unitilized)).
62
63 MEMORY SCALING
64 Murasaki can take a lot of memory. Storing the location of each seed in
65 the hash table is the most costly part of the operation, requiring
66 approximately "ceil(log_2(N))" bits per seed where "N" is the total
67 sequence length. Locations are, by default, stored in a bitpacked format
68 to approach theoretical minimum. The second most costly element is the
69 hash table structure, where each bucket carries a small overhead and
70 unused are simply wasted space. More hash table buckets (i.e. a longer
71 hash table) decreases the expected number of collisions, leading to
72 faster executation time. Therefore Murasaki tries to use as many buckets
73 as possible by inspecting the available system memory and using as much
74 as it can while still storing all the seed locations. If this automatic
75 scaling is ineffective, setting the hash table size directly via the
76 --hashbits|-b options can force a specific hash table size. If the
77 memory of one computer is insufficient to store the desired hash table,
78 PARALLELIZATION can be used to distribute the hash table across multiple
79 computers.
80
81 PARALLELIZATION
82 Murasaki is designed to run in parallel using MPI. Consult the
83 documentation for the specific variations of your MPI implementation,
84 however in general the executation method looks like:
85
86 mpirun [MPI options] murasaki [murasaki options] -p[pattern] [seq1 ...]
87
88 Murasaki in parallel divides the number of processors available (NP)
89 into two groups: hasher nodes and storage nodes. The storage nodes
90 divide the hash table between each themselves, each being responsible
91 for a different part of the table. Hasher nodes divide the input
92 sequence in between themselves, each hashing a separate portion of the
93 input sequence, and passing the seed location to the appropriate storage
94 node for storage. When all the hasher nodes are finished hashing, the
95 storage nodes scan their portion of hash table and pass matching sets of
96 seeds to a hasher node where they are assembled into anchors and
97 extended. Finally all the hasher nodes combine their independent anchor
98 sets into one final set in "ceil(log_2(H))" iterations (where "H" is the
99 number of hasher nodes), with each hasher node number 2h passing its
100 anchors to hasher number 2h-1 at each iteration.
101
102 Because almost none of the parallelization steps require communication
103 between *all* nodes, and each seed and each anchor can be processed in
104 parallel, Murasaki scales very well in parallel, running approximately
105 twice as fast when twice as many nodes are available. Furthermore, the
106 hash table is automatically grown to take advantage of the combined
107 memory from multiple machines.
108
109 OPTIONS
110 Most options can be specified in their long form (e.g. "--directory out"
111 or "--directory=out") or short form (e.g. "-dout"). Options marked by
112 <S> expect a string, <D> an integer, <F> a float, and <B> a boolean
113 value ("yes/on/true/1" for true, "no/off/false/0" for false). Most
114 booleans can omit the value, toggling the value from whatever it was to
115 the opposite.
116
117 Murasaki has a lot of options. Here we've separated them into categories
118 to help distinguish the scope of the various options, however in certain
119 situations certain option choices may have onforseen consequences, and
120 of course ultimately if the specified output is *huge*, the required
121 runtime will necessarily be *long*. It is a mistake to think that
122 everything outside of the "tuning options" in Performance section has no
123 bearing on performance.
124
125 Anchor parameter related options
126 These options shape what is considered an "anchor".
127
128 --pattern|-p <S>
129 specifies the seed pattern (eg. 11101001010011011). using the format
130 C<[<w>:<l>]> automatically generates a random pattern of weight <w>
131 and length <l>
132
133 --repeatmask|-r <B>
134 Skip repeat masked data (ie: lowercase atgc). Be aware that some
135 sequence files are distributed purely in lower case.
136
137 --seedfilter|-f <D>
138 Skip seeds that occur more than N times. Exceptionally slow. See
139 --hashfilter for a faster approximation.
140
141 --hashfilter|-m <D>
142 Like --seedfilter but works on hash keys instead of seeds. May cause
143 some collateral damage to otherwise unique seeds, but it's faster.
144
145 --skipfwd|-F <B>
146 Don't hash/match the forward strands.
147
148 --skiprev|-R <B>
149 Don't hash/match the reverse complement strands.
150
151 --skip1to1|-1 <B>
152 Skip matches along the 1:1 line (good for comparing to self).
153
154 --hashonly|-Q <B>
155 Hash Only. No anchor output, just statistics.
156
157 --hashskip|-S <D>
158 Hashes every n bases. Default is 1 (i.e. hashing all positions). Not
159 supplying any argument increments the skip amount by 1.
160
161 --join|-j <D>
162 Join anchors within n bases of eachother (default: 0). Specifying a
163 negative D implies -D*patternLength.
164
165 --bitscore|-B <B>
166 toggles compututation of a bitscore for all anchors (default is on).
167
168 --seedterms|-T <B>
169 toggles retention of seed terms (defaults to off). These are
170 necessary for computing TF-IDF scores).
171
172 --sectime|-e <B>
173 Always display times in seconds as opposed to human readable "1d 3h
174 45m 5s" style times.
175
176 --mergefilter|-Y <D>
177 Filter out matches which would would cause more than *D* many
178 anchors to be generated from 1 seed (default -Y100). Use -Y0 to
179 disable.
180
181 --scorefilter <D>
182 Set a minimum ungapped score for seeds.
183
184 --rifts|-/ <D>
185 Allow anchors to skip D sequences (default 0).
186
187 --islands|-% <D>
188 Same as --rifts=S-D (where S is number of input seqs).
189
190 --fuzzyextend|-z <B>
191 Enable (default) or disable fuzzy extension (i.e. ungapped
192 alignment) of anchors.
193
194 --fuzzyextendlosslimit|-Z <D>
195 Set the cutoff at which to stop extending fuzzy hits (ie. the BLAST
196 X parameter).
197
198 --gappedanchors <B>
199 Use gapped (true) or ungapped (false (default)) anchors.
200
201 --scorebyminimumpair <B>
202 Do anchor scoring by minimum pair when appropriate (default).
203 Alternative is arithmatic mean (seldom useful, but theoretically
204 faster). =item --rifts|-/ <D>
205
206 Allow anchors to skip D sequences (default 0).
207
208 --islands|-% <D>
209 Same as --rifts=S-D (where S is number of input seqs).
210
211 --fuzzyextend|-z <B>
212 Enable (default) or disable fuzzy extension (i.e. ungapped
213 alignment) of anchors.
214
215 --fuzzyextendlosslimit|-Z <D>
216 Set the cutoff at which to stop extending fuzzy hits (ie. the BLAST
217 X parameter).
218
219 --gappedanchors <B>
220 Use gapped (true) or ungapped (false (default)) anchors.
221
222 --scorebyminimumpair <B>
223 Do anchor scoring by minimum pair when appropriate (default).
224 Alternative is arithmatic mean (seldom useful, but theoretically
225 faster).
226
227 Output options
228 These options primarily affect what data is output where.
229
230 --directory|-d <S>
231 output directory (default: output)
232
233 --name|-n <S>
234 alignment name (default: test)
235
236 --repeatmap|-i <B>
237 Toggles keeping of a repeat map when --mergefilter is used (defaults
238 to yes).
239
240 --histogram|-H <D>
241 Histogram computation level: (-H alone implies -H1)
242
243 0 - no histogram (default)
244 1 - basic bucketsize/bucketcount histogram data
245 2 - bucket-based scores to anchors.detils
246 3 - perbucket count data
247 4 - perbucket + perpattern count data
248
249 Any values above 2 are purely explorartory and can result in massive
250 output files.
251
252 --tfidf|-k <B>
253 Perform accurate tfidf scoring from within murasaki (requires extra
254 memory at anchor generation time). Default is no.
255
256 Performance/tuning options
257 These options primarily affect performance, and don't (in general)
258 impact output.
259
260 --quickhash|-q <D>
261 specify a hashing function:
262
263 0 - adaptive with S-boxes (default when there's plenty of hash table
264 to spare)
265 1 - don't pack bits to make hash (use first word only)
266 2 - naively use the first hashbits worth of pattern
267 3 - adaptivevely find a good hash (default)
268 **experimental CryptoPP hashes**
269 4 - MD5
270 5 - SHA1
271 6 - Whirlpool
272 7 - CRC-32
273 8 - Adler-32
274
275 Note: 3 and 0 are the only "recommended" hash functions, and the
276 only ones automatically selected. The others are provided merely for
277 reference. 1, 7, and 8 aren't even expected to utilize the entire
278 hash space.
279
280 --hashbits|-b <D>
281 use D bit hashes (for n's of 1 to WORDSIZE. default 26)
282
283 --hashtype|-t <S>
284 select hash table data structure to use:
285
286 OpenHash - open sub-word packing of hashbits (default when there's
287 plenty of hash table to spare)
288 EcoHash - chained sub-word packing of hashbits (default)
289 ArrayHash - malloc/realloc (fast but fragmentation-prone)
290 MSetHash - memory exorbanant, almost pointless.
291
292 --probing <D>
293 0 - linear, 1 - quadratic (default). Only applicable for
294 --hashtype=OpenHash.
295
296 --hitfilter|-h <D>
297 Minimum number of hits to be outputted as an anchor (default 1). In
298 PatternHunter this is 2.
299
300 --rseed|-s <D>
301 Random number seed for non-deterministic algorithms (ie: adative
302 hash function generation). If you're doing any performance
303 comparisons, it's probably imperative that you use the same seed for
304 each run of the same settings. Default is obtained from time() (ie:
305 seconds since 1970).
306
307 --memory|-M [<F>|<S>]
308 Set the target amount of total memory (either in gb or as % total
309 memory).
310
311 --reverseotf|-o <B>
312 Generate reverse complement on the fly (defaults to on). Turning
313 this off precomputes the all reverse complement strands and stores
314 them in memory, which rarely provides a measurable performance
315 improvement.
316
317 --binaryseq <B>
318 Enable (default) or disable binary sequence read/write
319
320 Adaptive hash function related:
321 Performance options related to adaptive hash function generation.
322
323 --hasherFairEntropy <B>
324 Use more balanced entropy estimation (default: yes).
325
326 --hasherCorrelationAdjust <B>
327 Adjust entropy estimates for nearby sources assuming some
328 correlation (default: yes).
329
330 --hasherTargetGACycles <D>
331 Adaptive hash function generation genetic algorithm cycle cutoff.
332
333 --hasherEntropyAgro <F>
334 How aggressive to be about pursuing maximum entropy hash functions
335 (takes a real. default is 1).
336
337 MPI Specific:
338 --hashers|-A [<F>|<D>]
339 Specify the number of processes to be used as hashers (only applies
340 to MPI. If a number between 0 and 1 it refers to a ratio of np).
341
342 --localhash|-K <B>
343 Perform hashing locally on each storage node rather than sending it
344 over the network (helpful for slow networks).
345
346 --mpidistro|-L <B>
347 Toggles use of MPI to distribute sequence data over (if the sequence
348 is available on local disk on each node then turning this off may
349 potentially accerlate the intial sequence loading).
350
351 --waittoanchor|-w <B>
352 Postpone actual anchor computation until all location sets have been
353 received (as opposed to trying to work between receiving seed
354 packets).
355
356 --buffers|-u <D>
357 Maximum number of unfinished buffers to allow while message passing
358 (0 means unlimited). Default is set based on the number of nodes
359 participating. MPI can crash or perform *very* poorly if this value
360 is too high.
361
362 --nobuffers|-U <B>
363 Same as --buffers=1.
364
365 --bigfirst|-I <B>
366 Assign hashers to large memory nodes first.
367
368 --hostbalance|-l <B>
369
370 If yes (default): spread out hashers evenly among all nodes.
371 If no: ignore host name when assigning jobs.
372
373 --memorybalance|-a <B>
374
375 If yes (deafult): balance hash storage between nodes based on the
376 amount of available ram.
377 If no: distribute storage evently. This more likely to achieve
378 optimal run times, but might not utilize memory as efficiently.
379
380 --distmerge|-< <B>
381
382 if yes (default): during the merge step, storage nodes send seeds to
383 any available hasher.
384 if no: send all seeds to one node only.
385
386 --distcollect|-> <B>
387
388 if yes (default): collect anchor data from all hashers.
389 if no: send all seeds to the final assembly node only.
390
391 --mpiredirectoutput <B>
392
393 if yes (default): each rank redirects its stdout/stderr to a
394 separate file (murasaki-mpiout-*N*).
395 if no: do what comes naturally (ie: managed by mpirun (for OpenMPI
396 see --output-filename and --tag-output in mpirun(1))).
397
398 --keepstdoe <B>
399 Don't erase the murasaki-mpiout files on success.
400
401 --sysvipc|-V <B>
402 Use System V IPC to negotiate shared memory regions (saves memory
403 when one host runs multiple nodes). Default is true.
404
405 Universal options:
406 --verbose|-v
407 Increases verbosity.
408
409 --version|-V
410 Prints version information and quits.
411
412 --help|-?
413 Prints a help message and quits.
414
415 FILE FORMATS
416 Murasaki has a wide array of output files, the formats of most of which
417 are intended to be intuitive. All output files are prefixed by the value
418 of the --name parameter. The primary output file formats are described
419 here. Files are line based and tab delimited unless otherwise specified.
420
421 .seqs
422 The .seqs shows what sequences were used as input, 1 per line. This file
423 gets used by various programs in conjunction with the .anchors file, so
424 it's generally important that the contents reflect the correct sequence
425 files. Moving anchor results between computers might result in a change
426 of paths, requiring the user to update the .seqs file. As an
427 alternative, always using relative paths can alleviate this problem.
428
429 .anchors files
430 These files are 1 anchor per line, with a 3-tuple per sequence. Each
431 touple represents the start and stop coordinates and strand of the
432 anchored interval on each sequence. The sequence order matches that of
433 the order in the .seqs file. The coordinates are structured such that 1
434 refers to the first base in the sequence, 2 to the second, etc. Negative
435 values refer to the reverse complement sequence where -1 is the *last*
436 base of the reverse complement sequence (ie: the complement first base
437 in the forward sequence). The "strand" element is a '+' or '-' that
438 merely matches the sign of the coordinates (this is redundant
439 information, but kept to make parsing or filtering simpler).
440
441 For examle:
442
443 1 18 + -1 -18 -
444
445 This line describes an anchor where the first 18 bases of the first
446 sequence match the first 18 bases of the reverse complement of the
447 second sequence.
448
449 .anchors.details
450 This is an antiquated file format, but used by GMV to calculate
451 statistics like TF-IDF scores, and has been kept around for that reason.
452 The .anchors.details file has the same format and information as the
453 .anchors file, however after the anchor touples are two more terms: a
454 score, and a comma (,) delimited list of term and count pairs (written
455 "term:count"). The score and count data might be varied depending on the
456 "--histogram" option choices.
457
458 .anchors.bitscore
459 The term "bitscore" here is a misnomer, but maintained for historical
460 reasons. In reality, this file contains the mean number of matching
461 bases and length of each anchor (corresponding line by line to the
462 .anchors file).
463
464 .stats.tfidf
465 Contains anchor TF-IDF scores (corresponding line by line to the
466 .anchors file).
467
468 .histogram
469 Contains a simple histogram of the hash table usage. The first field is
470 the bucket size, and the second is the frequency. For example a
471 .histogram file like this:
472
473 1 24
474 2 1
475
476 Would indicate that there were 24 hash buckets that stored only 1
477 location (i.e. 24 unique seeds), and 1 hash bucket stored 2 locations
478 (i.e. 1 seed that matched 2 locations (or 2 non-matching seeds that
479 resulted in a hash collision)).
480
481 .options
482 Maintains a record of the options used when running Murasaki.
483
484 .repeats
485 The .repeats file stores a record of "repeats" as defined by the
486 --mergefilter option (i.e. seeds that would have have induced more
487 anchors than permitted). In this file, each repeat record is separated
488 by a blank line. A repeat record looks like this:
489
490 R: G.GCCTTT.T.ACT.CACAA..AT
491 0: 2145540494 -425039256 -113794380 1998323403
492 1: 2480929222 -1874514626 2543723555 -2550045172
493
494 The first line (always prefixed "R:") shows the repeating seed itself
495 (where the . are the bases masked by the pattern). The subsequent lines
496 show where these seeds occured in the input sequences (in the first (0)
497 and second (1) sequences). Note that if there are no hits in a
498 particular sequence, it doesn't include a blank line for that sequence.
499 For example:
500
501 R: G.GCCTTT.T.ACT.CACAA..AT
502 0: 2145540494 -425039256 -113794380 1998323403
503 2: 2480929222 -1874514626 2543723555 -2550045172
504
505 is also a valid .repeats file.
506
507 LICENSE
508 GNU General Public License, version 3 (GPLv3)
509
510 AVAILABILITY
511 <http://murasaki.sourceforge.net>
512
513 AUTHOR
514 Kris Popendorf <[email protected]>
515
516 SEE ALSO
517 mbfa(1), geneparse(1)
518
519 RELATED READING
520 M. Csuros and B. Ma, "Rapid Homology Search with Two-Stage Extension and
521 Daughter Seeds" (2005).
522 F. P. Preparata and L. Zhang and K. W. Choi, "Quick, practical selection
523 of effective seeds for homology search" (2005).
524 KP Choi, et. al., "Good spaced seeds for homology search" (2004).
525