Sequence alignment

deterministic_alignment.py

• Needleman-Wunsch algorithm: global alignment
• Smith-Waterman algorithm: local alignment
• Levenshtein distance: minimum number of operations (insertion, deletion, modification) to transform one sequence to an other sequence

phmm.py : Pair Hidden Markov Model implementation

blast.py : heuristics to find local alignments in very long chains

main.py : examples of presented algorithms

data_retrieval.py : word retrieval thanks to nltk

1. Install nltk with # apt-get install nltk
2. Download Swadesh corpus with

>>> import nltk
>>> nltk.download()

utils.py : some useful functions which are unclassified

TODO: learning to align pairs of sequences with a Pair Hidden Markov Model.