Welcome to NextGenMap - The Next Generation of Mapping
Introduction:
The central element of NextGenMap is the banded alignment algorithm that allows for a sensible adjustment of the scores, when for example evolutionary diverged reads orreads, where a high error rate is suspected are mapped to a reference genome. NextGenMap supports a Smith- Waterman (SW) and a Needleman-Wunsch (NW) banded alignment mode, thus allowing for a user-defined maximal number of admissible consecutive insertions and deletions.
To reduce computation time, we preprocess the read data. A lookup table is computed that assigns putative genomic positions to a read based on a short exact matching word.
However, the number of alignments is still high, thus we implemented the SW and NW algorithm on a GPU to run several computations in parallel. To gain further speed and to obtain linear space requirement we discarded the backtracking step of the algorithm and only compute the optimal scores.
For the alignment with the highest score, we finally compute a banded alignment with backtracking.
NextGenMap is part of the NG* workbench.
Availability:
Requirements:
- CUDA able graphics card (here is the list of all usable graphic cards CUDA Cards
- A Linux operating system
- A PC with at least 2 GB of memory
Latest Version NextGenMap 0.0.1 (14th December 2010):
- Please read the User Manual carefully before using NextGenMap the first time or when you upgrade the new version!!
Download:
- Source package for Linux are available in gzipped TAR format. The current version of NextGenMap is just tested and released under Linux. Further versions will also be available under Windows and Macs.
Type | LinkS |
Source code | ngm-src-0.2.0.tar.bz2 |
Linux Binary (x64) | ngm-0.2.0.tar.bz2 |
Alignment libraries Linux Binary (x64) | ngm-alignment-libs-0.2.0.tar.bz2 |
Reference:
The method is currently submitted.Note:
- Please, let us know if you download this program by sending an email to {fritz.sedlazeck,arndt.von.haeseler}@univie.ac.at