Table of Contents

• Cigar Aligner
  • Implementation
  • Installation
  • Setup

CIGAR string decompression can be implemented to retrieve paired strand coordinates from a transcript read to a reference genome from SAM/BAM format.

Included features

• Automated data generation as a convenient executable within setup.py
• Retrieval of coordinates (or mapped coordinate ranges) under the following conditions:
  • Forward strand (5'➜3') and reversed strand orientation (3'➜5')
  • Inverted alignment (reference genome aligned to transcript read)
• Documentation across all features
• Unit testing to indicate input constraints and functionality of:
  • Data generation methods within setup.py
  • CIGAR array implementation
  • Algorithm functionality for alignment
  • Main task executation
  • Results output format

A CIGAR representation of SAM-formatted alignment can be decompressed to range elements and operations, respectively (i.e. (11, 'M') from 11M). Coordinate operations in this exercise may either be read-consuming (M, I, S) or reference-consuming (M, D). Other operations exist in real-world CIGAR encoding. The read index start site begins at a known non-zero coordinate of the reference index. The CIGAR string may be reversed.

import utils from Utils
cigar = '8M7D6M2I2M11D7M'

# Cigar in forward 5'->3' orientation
Utils(cigar, direction='F')._groups()
>>> [(8, 'M'), (7, 'D'), (6, 'M'), (2, 'I'), (2, 'M'), (11, 'D'), (7, 'M')]

# Cigar in reversed 3'->5' orientation
Utils(cigar, direction='R')._groups()
>>> [(7, 'M'), (11, 'D'), (2, 'M'), (2, 'I'), (6, 'M'), (7, 'D'), (8, 'M')]

# Read and references arrays created with a specified site
c = Utils(cigar, direction='F', start_site=3)
c.index('read')
>>> [0, 8, 0, 6, 2, 2, 0, 7]
c.index('reference')
>>> [3, 8, 7, 6, 0, 2, 11, 7]

Prefix sums allows for counting in O(n) time complexity and the storage of sums of contiguous elements in an array. For the purpose of this exercise, the input arrays contain the numeric range elements from either the read or reference indices encoded within the CIGAR grouping. Resulting arrays may be created using the Map.prefix_sums(A) class method. The arrays are stored in a tuple for optional inversion of the template.

# Read and references arrays (summed and stored)
read = [0, 0, 8, 8, 14, 16, 18, 18, 25]
reference = [0, 3, 11, 18, 24, 24, 26, 37, 44] 
inverted = (read, reference)[::-1]

The complimentary strand coordinate may be queried with a value less than the maximum of the template strand. Map conditions apply within the alignment function as the read and reference arrays are reversed or inverted. A single coordinate of a range of coordinates may be queried.

from map import Map

m = Map(cf, direction='R', start_site=3, inverted=False)
m.align(14)
>>> 26

m.map_ranger(start=7, end=13)
>>> [(7, 10), (8, 22), (9, 23), (10, None), (11, None), (12, 24), (13, 25)]

Orientation resource table

1. Create a virtual conda (Python 3) environment called cigar-env with Python and pip

➜  conda create --name cigar-env python=3.6 pip
➜  source activate cigar-env
(cigar-env) ➜

2. Clone the repository and install package requirements.

(cigar-env) ➜ git clone https://github.com/foadgr/cigar_aligner.git
(cigar-env) ➜ cd cigar_aligner
(cigar-env) ➜ python setup.py install

1. Execute the create_data setup command to create the tab-delimited data files necessary for the main specification and tests.

(cigar-env) ➜ python setup.py create_data
(cigar-env) ➜ ls -R

2. Run the main specification alongside bells and whistles. Note: these will write results to a tab-delimited file in the relative path. ls -R to view results output in directory tree.

(cigar-env) ➜ python cigar_aligner/task.py
(cigar-env) ➜ ls -R

Output

./cigar_aligner/data/main_spec:
input_01.tsv    input_02.tsv    output_{output_type}.tsv

./cigar_aligner/data/tests:
input_01.tsv    input_02.tsv    output_{output_type}.tsv

3. Run unit tests on main specification and bells and whistles.

(cigar-env) ➜ python cigar_aligner/test_task.py

Output

..
----------------------------------------------------------------------
Ran 2 tests in 0.029s

OK