msbwt 0.2.6

Allows for merging and querying of multi-string BWTs for genomic strings

Introduction
============

Msbwt is a package for combining strings from sequencing into a data structure known as the multi-string BWT (MSBWT).
This structure allows for querying a k-mer in O(k) time regardless of how many strings are present in the MSBWT. This
particular package was created originally for merging MSBWTs after creation. In short, this allows for multiple data
sets to be combined into a single structure which allows for queries over both data sets simultaneously.

Included in this package are implementations of MSBWT creation algorithms as described by Bauer et al. in "Lightweight
BWT construction for very large string collections" for different file types. Furthermore, the algorithm for merging
these MSBWTs from Holt and McMillan in "Merging of Multi-String BWTs with Applications" is also implemented.

Currently, some rudimentary query utilities are also in place on the command line interface. However, we recommend to
anyone wishing to perform some dynamic/interactive queries to use the API provided by the source code.

For detailed usage, please type after installation:

msbwt -h

References
==========

Holt, James, and Leonard McMillan. "Merging of multi-string BWTs with applications." Bioinformatics (2014): btu584.

Holt, James, and Leonard McMillan. "Constructing burrows-wheeler transforms of large string collections via merging."
Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics. ACM, 2014.

System Requirements
===================

Msbwt and its modules have been tested under Python 2.7. The package is distributed with both Cython and the
corresponding C files. We recommend using installing Cython prior to installing this package.

Two Python modules are required to run the code.

*[pysam] - Tested with pysam 0.7.4

As a wrapper of Samtools, the pysam module facilitates the manipulation of SAM/BAM files in Python. Its latest
package can be downloaded from:

http://code.google.com/p/pysam/


*[argparse] - Tested with argparse 1.2.1

The argparse module is used to parse the command line arguments of the module. It has been maintained in Python
Standard Library since Python 2.7. Its latest package can be downloaded from:

http://code.google.com/p/argparse/

Installation
============

It is recommended to use easy-install (http://packages.python.org/distribute/easy_install.html) for the
installation.

easy_install msbwt

Alternatively, users can download the tarball of source from

https://github.com/holtjma/msbwt

and then type:

easy_install msbwt-<version>.tar.gz

By default, the package will be installed under the directory of Python dist-packages, and the executable of
msbwt can be found under '/usr/local/bin/'.

If you don't have permission to install it in the system-owned directory, you can install it in locally following
the next steps:

(1) Create a local package directory for python:

mkdir -p <local_dir>

(2) Add the absolute path of <local_dir> to the environment variable PYTHONPATH:

export PYTHONPATH=$PYTHONPATH:<local_dir>

(3) Use easy_install to install the package in that directory:

easy_install -d <local_dir> msbwt-<version>.tar.gz

For example, if you want to install the package under the home directory in
a Linux system, you can type:

mkdir -p /home/$USER/.local/lib/python/dist-packages/
export PYTHONPATH=$PYTHONPATH:/home/$USER/.local/lib/python/dist-packages/
easy_install -d /home/$USER/.local/lib/python/dist-packages/ msbwt-<version>.tar.gz

After installation, msbwt will be located in '/home/$USER/.local/lib/python/dist-packages/'.


Detailed Description
===========

The msbwt package is primarily focused on creation, merging, and querying of MSBWTs. To perform a query, several
data structures are useful and stored with the MSBWT. To handle this, each MSBWT is grouped into a directory which
contains standardized filenames. Here is the description of what each file contains:

seqs.npy Contains the raw input strings in a sorted, numerical format. It can be safely deleted after
msbwt.npy has been fully instantiated.
offsets.npy Contains meta-data regarding seq.npy. For strings of uniform length, this file is very small.
If strings have variable size, it will be O(S) where S is the number of strings. This file can
be safely deleted after msbwt.npy has been fully instantiated.
about.npy Contains information regarding the origin of the sorted strings to be stored in the MSBWT. For
example, if multiple FASTQ files are used for input, this file includes both the source file and
which read it was in that file. For paired end reads, this can be useful for finding mates.
If deleted, this file is NOT recoverable from msbwt.npy.
msbwt.npy Contains the full, uncompressed MSBWT. Each symbol in the MSBWT takes one byte of space. If
deleted, the MSBWT is NOT recoverable except from comp_msbwt.npy.
fmIndex.npy Contains a sampled FM-index for msbwt.npy. This is derived from msbwt.npy and must be created
for any queries to work. If deleted, the file will be automatically re-created if a query is
performed on the data set.
comp_msbwt.npy Contains the compressed MSBWT. Each byte contains 3 bits for the symbol and 5 bits for a count.
Each run is compressed into a symbol/length pairs and lengths too big for 5 bits expanded to
multiple bytes such that one byte contains lengths < 32, two bytes < 32^2, three bytes < 32^3,
and so on for as many bytes are necessary to store the run length. If deleted, this file is NOT
recoverable except from msbwt.npy.
comp_fmIndex.npy Contains a sampled FM-index for comp_msbwt.npy. This is derived from comp_msbwt.npy and must be
created for any queries to work. If deleted, this file will be automatically re-created if a query
is performed on the data set.
comp_refIndex.npy Contains offset information for the sample FM-index. This is derived from comp_msbwt.npy and must
be created for any queries to work. If deleted, this file will be automatically re-created if a
query if performed on the data set.

The msbwt package is broken down into various sub-functions which include MSBWT creation, merging, and querying. Below is a
list of each along with the expected output.

cffq Create From FASTQ. This function takes a list of input FASTQ files and will create the MSBWT from
the strings contained in them to be stored in the end result of msbwt.npy. This is functionally the
same as doing 'pp' followed by 'cfpp'. Note that strings of uniform length can be processed faster
than strings of non-uniform length.
pp Pre-Process. This function takes a list of input FASTQ files and will create the seqs.npy, offsets.npy,
and about.npy files for those FASTQ files. Note that strings of uniform length can be processed faster
than strings of non-uniform length.
cfpp Create From Pre-Process. This function takes a pre-processed directory and creates the MSBWT from the
strings contained in seqs.npy to create msbwt.npy.
merge This function takes a list of input MSBWT directories and merges them into a single output MSBWT. The
resulting BWT will always be stored in msbwt.npy of the output directory.
query This function is for performing a single query of a specific k-mer within the data. Options exist for
dumping the associated strings containing that k-mer as well.
massquery This function takes a list of queries in a line separated file and performs those searches storing counts
for each query in a CSV file.
compress This function takes an uncompressed MSBWT and converts it to the compressed version. The auxiliary
FM-index will need to be reconstructed for the new data format.
decompress This function takes a compressed MSBWT and converts it back into its original uncompressed format.
The auxiliary FM-index will need to be reconstructed for this format.

The latest release also includes installation of the Cython library used to load the MSBWTs and perform merges. After
installation, the libraries are available through regular Python imports like so:

import MUSCython.MultiStringBWTCython as MultiStringBWT
msbwt = MultiStringBWT.loadBWT('/path/to/directory')
msbwt.countOccurrencesOfSeq('CAT')

Other commands are available as well. For more information, refer to the code available at https://code.google.com/p/msbwt/.