Bioinformatic Algorithms

some scripts and algorithm implementations based on the content of the Bioinformatic Algorithms course AA 2021/2022

De-bruijn.py

This is a script that generates a De-Bruijn graph constructed from a DNA sequence. The script will output two .dot files.

1. graph.dot generates only the de-bruijn graph
2. graph_path.dot will generate, if possibile, an Eulerian path.
   • this file will not be created if the graph is not traversable.

The example is generated by the sequence TCATTCTTCAGGTCAAA.

how to run the script

$ python3 de-bruijn.py 

In order to generate the .svg image of the graph install graphwiz. Then run

$ dot -Tsvg (filename).dot > (output_name).svg

minimum_edit_distance.py

It will find possibile alignments based on a minimum edit distance criteria. The metric used is the Levenshtein distance.

$ python3 minimum_edit_distance.py