Description
Ngila is a global alignment program that can align pairs of sequences using logarithmic and affine gap penalties.
Contact
I can be emailed at racartwr@ncsu.edu or reed@scit.us. Please be sure to include "Ngila" in the subject line.
Citation
Cartwright RA (2007) Ngila: global pairwise alignments with logarithmic and affine gap costs. Bioinformatics. 23(11):1427-1428 [ link (free)]
Download Supplemental Material (pdf)
News: 2007/08/23
Version 1.2.1 has been released. This version fixes two bugs in the previous release.
- Spaces in Fasta sequence names converted to underscores.
- Sequence names are now properly truncated for output.
News: 2007/08/22
Version 1.2 has been released. This version adds two new evolutionary models for specifying costs, while redesigning much of the code to be more modular. Specific changes:
- Changed license to GPL
- Reorganized source code to a more modular framework.
- Compiling from source now requires GSL and Boost Libraries
- Added two evolutionary models: K2P+Zeta and K2P+Geometric
- Command line options changed
- Only FASTA supported for input
- Tie breaking has changed
- The Clustal output format has been altered
- Man page updated and tied to cmds file
- Added pairs setting for more control of sequential alignments
- Several Bug fixes
Download and Install
Download portable source code. Extract the archive and run './configure && make install'.
For Windows, I have a binary distribution. Just unzip and move to where ever you want.
Example Usage
ngila -m zeta -t 0.1 -k 2.0 -r 0.05 -z 1.65 sequences.fasta
Manual
See NgilaManual.
Algorithm
Ngila implements a Miller and Myers (1988) candidate list method of sequence alignment with the gap cost being of the form g(x) = a + b*x + c*ln x. Ngila will return the alignment with the minimum cost and has rules for breaking ties. Ngila's main alignment algorithm is divide-and-conquer, which requires O(M) memory; but slower than a holistic, O(MN) memory algorithm.
Ngila implements a secondary, holistic algorithm for alignment, which is faster. The options -M and -N (-M is for the larger sequence) allow users to specify thresholds for when the holistic algorithm is used instead of the DnC algorithm. For example, command 'ngila -M 5000 -N 5000 seqs.fasta' will align the sequences in 'seqs.fasta' via the divide-and-conquer algorithm, but when subsequences less than or equal to 5000-5000 are being aligned, the holistic algorithm will be used.
