*** RazerS 3 - Faster, fully sensitive read mapping ***
http://www.seqan.de/projects/razers.html

------------------------------------------------------------------------------
Table of Contents
------------------------------------------------------------------------------
  1.   Overview
  2.   Installation
  3.   Usage
  4.   Output Formats
  5.   Examples
  6.   Contact
  7.   References

------------------------------------------------------------------------------
1. Overview
------------------------------------------------------------------------------

RazerS 3 is a tool for mapping millions of short genomic reads onto a
reference genome. It was designed with focus on mapping next-generation
sequencing reads onto whole DNA genomes. RazerS 3 searches for matches of
reads with a percent identity above a given threshold (-i X), whereby it
detects alignments with mismatches as well as gaps.

RazerS 3 consists of a filtration part, in which a k-mer filter scans the
genome for regions that possibly contain read matches, and a verification
part, where results from the filtration are then subjected to a verification
algorithm. The user can choose between two filters: (1) a seed-based filter
based on the pigeonhole principle or (2) a k-mer counting filter based on the
SWIFT algorithm (Rasmussen et al., 2006). The pigeonhole filter (default) is
faster for a broad range of read sets and error rates, whereas the swift
filter (-fl swift) is faster for short reads (<50bp) and high error rates
(10-20%).

Both filters can be run in full-sensitive mode (-rr 100), i.e. given a maximal
error rate they will output every match as a match candidate, or in lossy mode
with a user-defined sensitivity (-rr X) at higher speeds. To exceed the
specified minimal sensitivity, RazerS 3 computes the expected loss rates of
different filter settings, based on base-call qualities of the reads and a
user-defined mutation rate, and chooses the most performant setting.

To verify the found candidates, we devised a banded version of the
bit-parallel approximate string search algorithm proposed by Myers (1999). The
found matches are recorded, duplicate-filtered, and ranked by the number of
errors (and deviation from a given paired-end insert size). At the end, the
results are written to an output file (-o FILENAME). Besides others, RazerS 3
supports a very efficient native format (.razers) and the commonly used SAM
and BAM formats (.sam or .bam).

------------------------------------------------------------------------------
2. Installation
------------------------------------------------------------------------------

To install RazerS 3, you can either compile the latest version from the Git
version or use a precompiled binary.

------------------------------------------------------------------------------
2.1. Compilation from source code
------------------------------------------------------------------------------

Follow the "Getting Started" section on http://trac.seqan.de/wiki and check
out the latest Git repo. Instead of creating a project file in Debug mode,
switch to Release mode (-DCMAKE_BUILD_TYPE=Release) and compile razers3. This
can be done as follows:

  1)  git clone https://github.com/seqan/seqan.git
  2)  mkdir seqan/buld; cd seqan/build
  3)  cmake .. -DCMAKE_BUILD_TYPE=Release
  4)  make razers3
  5)  ./bin/razers3 --help

If RazerS 3 will be run on the same machine it is compiled on, you may
consider to optimize for the given system architecture. For gcc or llvm/clang
compilers this can be done with:

  cmake .. -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS:STRING="-march=native"
  make razers3

After compilation, copy the binary to a folder in your PATH variable, e.g.
/usr/local/bin:

  sudo cp bin/razers3 /usr/local/bin


------------------------------------------------------------------------------
2.2. Precompiled binaries
------------------------------------------------------------------------------

We also provide a precompiled binary of RazerS 3 for 64bit Linux. It was
succesfully tested on Debian GNU/Linux 6.0.5 (squeeze) and Ubuntu 12.04.
Please download the binary from: http://www.seqan.de/projects/razers.html

------------------------------------------------------------------------------
3. Usage
------------------------------------------------------------------------------

To get a short usage description of RazerS 3, you can execute razers3 -h or
razers3 --help.

Usage: razers3 [OPTION]... <GENOME FILE> <READS FILE>
       razers3 [OPTION]... <GENOME FILE> <PE-READS FILE1> <PE-READS FILE2>

RazerS 3 expects the names of two or three FASTA or FASTQ files. The first
contains a reference genome and the second (and third) contain genomic reads
that should be mapped onto the reference. If two read files are given, both
have to contain exactly the same number of reads, which are considered as read
pairs.

------------------------------------------------------------------------------
3.1. Main Options
------------------------------------------------------------------------------

  [ -fl STRING ],  [ --filter STRING ]

  Use the seed-based pigeonhole filter (-fl pigeonhole, default) or the k-mer
  counting SWIFT filter (-fl swift). See Section 3.3, for filter-specific
  parameters.

  [ -tc NUM ],  [ --thread-count NUM ]

  Use NUM threads (default: 1). Set to 0 to use the old RazerS 1/2 code path.

  [ -i NUM ],  [ --percent-identity NUM ]

  Set the percent identity threshold. NUM must be a value between 50 and
  100 (default is 95). RazerS 3 searches for matches with a percent identity
  of at least NUM. A match of a read R with e errors has percent identity
  of 100*(1 - e/|R|), whereby |R| is the read length. In other words, a
  read is allowed to have not more than |R|*(100-NUM)/100 errors.
  The maximal error rate is the direct opposite of the identity threshold,
  e.g. an error rate of 4% corresponds to an identity of 96%.

  [ -rr NUM ],  [ --recognition-rate NUM ]

  Set the percent recognition rate. NUM must be a value between 80 and 100
  (default is 99). The recognition rate controls the sensitivity of RazerS 3.
  The higher the recognition rate the more sensitive is RazerS 3. The lower
  the recognition rate the faster runs RazerS 3. A value of 100 corresponds
  to a lossless read mapping. The recognition rate corresponds to the
  expected fraction of matches RazerS 3 will find compared to a lossless
  mapping. Depending on the desired recogition rate, the percent identity
  and the read length the filter is configured to run as fast as possible.
  For this purpose, it either computes the sensitivities of different
  pigeonhole filter settings on runtime or (due to the much larger search
  space) uses precomputed sensitivies of the SWIFT filter. The latter are
  precompiled in RazerS but can be replaced by user-specific settings in a
  parameter directory (-pd).
  The recognition rate value (and also the automatic sensitivity control) is
  disabled if filtration parameters, i.e. overlap length (-ol), shape (-s),
  or minimum threshold (-t), are set manually.

  [ -ng ],  [ --no-gaps ]

  Consider only mismatches as errors (Hamming distance). By default,
  insertions, deletions and mismatches are considered as errors (edit
  distance).

  [ -f ],  [ --forward ]

  Only map reads onto the positive/forward strand of the genome. By
  default, both strands are scanned.

  [ -r ],  [ --reverse ]

  Only map reads onto the negative/reverse-complement strand of the
  genome. By default, both strands are scanned.

  [ -m NUM ],  [ --max-hits NUM ]

  Output at most NUM of the best matches, default value is 100.

  [ --unique ]

  Output only unique best matches (like ELAND). This flag is equivalent to
  '-m 1 -dr 0 -pa'.

  [ -tr NUM ],  [ --trim-reads NUM ]

  Trim reads to length NUM bp.

  [ -ll NUM ],  [ --library-length NUM ]

  Set the mean library size, default is 220. The library size is the outer
  distance of the two mapped reads of a read pair. This value is used only for
  paired-end read mapping.

  [ -le NUM ],  [ --library-error NUM ]

  Set the tolerated absolute deviation of the library size, default value is
  50. This value is used only for paired-end read mapping.

  [ -o FILE ],  [ --output FILE ]

  Change the output filename to FILE. By default, this is the (first) read
  filename extended by the suffix '.razers'.

  [ -v ],  [ --verbose ]

  Verbose. Print extra information and running times.

  [ -vv ],  [ --vverbose ]

  Very verbose. Like -v, but also print filtering statistics like number of
  candidates and successful verifications.

  [ --version ]

  Print version information.

  [ -h ],  [ --help ]

  Print a brief usage summary.

------------------------------------------------------------------------------
3.2. Output Format Options
------------------------------------------------------------------------------

  [ -a ],  [ --alignment ]

  Dump the alignment for each match in the ".result" file (only for razer or
  fasta format). The alignment is written directly after the match and has the
  following format:
  #Read:   CAGGAGATAAGCTGGATCGTTTACGGT
  #Genome: CAGGAGATAAGC-GGATCTTTTACG--

  [ -pa ],  [ --purge-ambiguous ]

  Omit reads with more than <max-hits> matches.

  [ -dr NUM ], [ --distance-range NUM ]

  If the best match of a read has E errors, only consider hits with
  E <= X <= E+NUM errors as matches. Disabled by default.

  [ -gn NUM ],  [ --genome-naming NUM ]

  Select how genomes are named in the output file. If NUM is 0, the Fasta
  ids of the genome sequences are used (default). If NUM is 1, the genome
  sequences are enumerated beginning with 1.

  [ -rn NUM ],  [ --read-naming NUM ]

  Select how reads are named in the output file. If NUM is 0, the Fasta ids
  of the reads are used (default). If NUM is 1, the reads are enumerated
  beginning with 1. If NUM is 2, the read sequence itself is used. If NUM is
  3, Fasta ids are used without a /L or /R suffix in paired-end mode.

  [ --full-readid ]

  Use the whole Fasta id of each read in the output file. By default, only the
  prefix up to the first space (excluding) is used.

  [ -so NUM ],  [ --sort-order NUM ]

  Select how matches are ordered in the output file.
  If NUM is 0, matches are sorted primarily by the read number and
  secondarily by their position in the genome sequence (default).
  If NUM is 1, matches are sorted primarily by their position in the genome
  sequence and secondarily by the read number.

  [ -pf NUM ],  [ --position-format NUM ]

  Select how positions are stored in the output file.
  If NUM is 0, the gap space is used, i.e. gaps around characters are
  enumerated beginning with 0 and the beginning and end position is the
  postion of the gap before and after a match (default).
  If NUM is 1, the position space is used, i.e. characters are enumerated
  beginning with 1 and the beginning and end position is the postion of the
  first and last character involved in a match.

  Example: Consider the string CONCAT. The beginning and end positions
  of the substring CAT are (3,6) in gap space and (4,6) in position space.

------------------------------------------------------------------------------
3.3. Filtration Options
------------------------------------------------------------------------------

  [ -fl STRING ],  [ --filter STRING ]

  Described in section 3.1.

  [ -mr NUM ],  [ --mutation-rate NUM ]

  Set the percent mutation rate used by the pigeonhole sensitivity estimation.
  The mutation rate specifies the rate of differences between sequenced and
  the reference genome, i.e. all errors except sequencing errors. These errors
  include small variants (SNPs, indels) or errors in the assembly of the
  reference. Default value is 5 (=5%).

  [-ol NUM ],  [ --overlap-length NUM ]

  Manually set the overlap length of adjacent k-mer seeds used in the
  pigeonhole filter. If the overlap is 0, non-overlapping k-mers of the
  specified shape (-s) are used. For overlaps of NUM > 0, the shape is
  extended to the right by NUM characters that overlap with the next seed.
  The seed positions in the reads are not affected by the overlap.
  This option disables the automatic sensitivity control.

  [ -pd DIR ],  [ --param-dir DIR ]

  Read user-computed parameter files of the SWIFT filter given in the
  directory <DIR>. These parameters can be computed based on a machine
  specific error distribution file and the param_chooser tool.

  [ -t NUM ],  [ --threshold NUM ]

  Depending on the percent identity and the length, the SWIFT filter computes
  for read a threshold of common k-mers between read and reference genome.
  These thresholds determine the filtration strictness and are crucial to the
  overall running time. With this option the threshold values can manually be
  raised to a minimum value to reduce the running time at cost of the mapping
  sensitivity. All threshold values smaller than NUM are raised to NUM. The
  default value is 1.
  This option disables the automatic sensitivity control.

  [ -tl NUM ],  [ --taboo-length NUM ]

  The taboo length is the minimal distance two k-mer must have in the
  reference genome when counting common k-mers between reads and reference
  genome (default is 1).

  [ -s BITSTRING ],  [ --shape BITSTRING ]

  Define the k-mer shape. BITSTRING must be a sequence of bits beginning
  and ending with 1, e.g. 1111111001101. A '1' defines a relevant and a
  '0' an irrelevant position. Two k-mers are equal, if all characters at
  relevant postitions are equal.
  This option disables the automatic sensitivity control.

  [ -oc NUM ],  [ --overabundance-cut NUM ]

  Remove overabundant read k-mers from the k-mer index. k-mers with a
  relative abundance above NUM are removed. NUM must be a value between
  0 (remove all) and 1 (remove nothing, default).

  [ -rl NUM ],  [ --repeat-length NUM ]

  The repeat length is the minimal length a simple-repeat in the
  genome sequence must have to be filtered out by the repeat masker of
  RazerS 3. Simple repeats are tandem repeats of only one repeated
  character, e.g. AAAAA. Independently of this parameter, N characters in
  the genome are filtered out automatically. Default value is 1000.

  [ -lf NUM ],  [ --load-factor NUM ]

  Set the load factor for the open addressing k-mer index. Defines how many
  entries should be used in the hash table. If the index stores at most X
  different k-mers, X * NUM entries will be reserved for the hash table.

------------------------------------------------------------------------------
3.4. Verification Options
------------------------------------------------------------------------------

  [ -mN ],  [ --match-N ]

  By default, 'N' characters in read or genome sequences equal to nothing,
  not even to another 'N'. They are considered as errors. By activating this
  option, 'N' equals to every other character and produces no mismatch in
  the verification process. The filtration is not affected by this option.

  [ -ed FILE ],  [ --error-distr FILE ]

  Produce an error distribution file containing the relative frequencies of
  mismatches for each read position. If the "--indels" option is given, the
  relative frequencies of insertions and deletions are also recorded.

  [ -mf FILE ],  [ --mismatch-file FILE ]

  Produce a mismatch file containing for each read alignment a line of
  tab-seperated 0's and 1's representing a match (0) or a mismatch (1).


------------------------------------------------------------------------------
4. Output Formats
------------------------------------------------------------------------------

RazerS 3 supports currently 5 different output formats which are automatically
chosen from the output filename suffix.

  .razers    = Razer Format
  .fa|.fasta = Enhanced Fasta Format
  .eland     = Eland Format
  .sam|.bam  = Sequence Alignment and Mapping Format (SAM)
  .afg       = AMOS assembler format

------------------------------------------------------------------------------
4.1. Razer Format
------------------------------------------------------------------------------

The output file is a text file whose lines represent matches. A line
consists of different tab separated match values in the following format:

RNAME RBEGIN REND GSTRAND GNAME GBEGIN GEND PERCID [PAIRID PAIRSCR MATEDIST]

Match value description:

  RNAME        Name of the read sequence (see --read-naming)
  RBEGIN       Beginning position in the read sequence (0/1 see -pf option)
  REND         End position in the read sequence (length of the read)
  GSTRAND      'F'=forward strand or 'R'=reverse strand
  GNAME        Name of the genome sequence (see --genome-naming)
  GBEGIN       Beginning position in the genome sequence
  GEND         End position in the genome sequence
  PERCID       Percent identity (see --percent-identity)

For paired-end read mapping 3 additional values are dumped:

  PAIRID       Unique number to identify the two corresponding mate matches
  PAIRSCR      The sum of the negative number of errors in both matches
  MATEDIST     Relative outer distance to the mate match
               The absolute value is the insert size

For matches on the reverse strand, GBEGIN and GEND are positions on the
related forward strand. It holds GBEGIN < GEND, regardless of GSTRAND.

------------------------------------------------------------------------------
4.2. Enhanced Fasta Format
------------------------------------------------------------------------------

The matches are stored in the same order as in the Razer format. Each match
is stored in two lines:

>GBEGIN,GEND[KEY1=VALUE1,KEY2=VALUE2,...]
READSEQ

Match value description:

  GBEGIN       Beginning position in the genome sequence
  GEND         End position in the genome sequence
  READSEQ      Read sequence.

The following keys are output:

  id           ID value of the input file Fasta header (>..[id=ID,..]..)
  fragId       Fragment ID value (>..[..,fragId=FRAGID,..]..)
  contigId     Name of the genome sequence (see --genome-naming)
  errors       Absolute numbers of errors in this match
  percId       Percent identity (see --percent-identity)
  ambiguity    Number of matches of this read as good as or better than this

If the ID or fragment ID values of a read couldn't be found in the reads file
the read number (beginning with 0) is used instead. For matches on the
reverse strand, GBegin and GEnd are positions on the related forward strand
and GBEGIN > GEND.

------------------------------------------------------------------------------
4.3. Eland Format
------------------------------------------------------------------------------

Each line of the output file corresponds to a read appearing in the same
order as they are stored in the reads file. A line consists of the following
tab separated values:

>RNAME READSEQ TYPE N0 N1 N2 GNAME GBEGIN* GSTRAND '..' SUBST1 SUBST2 ...

Additional value description:

  TYPE         NM = No match found
               QC = No matching done (too many Ns in read sequence)
               Ux = Best match found was unique with x errors
               Rx = Multiple best matches found having x errors
  N0 N1 N2     Number of exact, 1-error, and 2-error matches
  GBEGIN*      Minimum of GBEGIN and GEND
  SUBSTx       Position and type of the x'th mismatch (not for --indels)
               (e.g. 12A: 12'th base was A in the genome)

------------------------------------------------------------------------------
4.4. SAM or BAM Output Format
------------------------------------------------------------------------------

The SAM output format has established itself as the standard output format for
read alignments. Altough SAM is capable of representing a multiple alignment
between reads and contig (with paddings), RazerS 3 only outputs pairwise
alignments as this way has established to be the defacto standard.
The BAM format is the binary representation of SAM compressed with gzip.
Whenever possible the more compact BAM format should be preferred over SAM.

See http://samtools.sourceforge.net/ for more details.

------------------------------------------------------------------------------
4.5. AMOS Output Format
------------------------------------------------------------------------------

The AMOS assembly format (aka AFG format) is used by the AMOS assembler and
represents a multiple global alignment between reads and contig and also
stores the consensus sequences (including gaps).

See http://www.cbcb.umd.edu/research/contig_representation.shtml#AMOS for more
details.

------------------------------------------------------------------------------
5. Examples
------------------------------------------------------------------------------

To map single-end reads with 4% error rate using 12 threads call:

 razers3 -i 96 -tc 12 -o map.result hg18.fa reads.fq

To map paired-end reads with up to 6% errors, 95% sensitivity, 12 threads, and
only output aligned pairs with an outer distance of 200-360bp call:

 razers3 -i 94 -rr 95 -tc 12 -ll 280 --le 80 -o map.result hg18.fa r1.fq r2.fq

------------------------------------------------------------------------------
6. Contact
------------------------------------------------------------------------------

For questions or comments, contact:
  David Weese <david.weese@fu-berlin.de>

------------------------------------------------------------------------------
7. References
------------------------------------------------------------------------------

Weese, D., Holtgrewe M., & Reinert, K. (2012). RazerS 3: Faster, fully
sensitive read mapping. Bioinformatics, 28(20), 2592–2599.