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.

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 arithmetic 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 arithmetic 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)

--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:
    

--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:

--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 initial 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>

--memorybalance|-a <B>

--distmerge|-< <B>

--distcollect|-> <B>

--mpiredirectoutput <B>

--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.

.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 tuple 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 tuples 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 occurred 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.

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).