Draft code for GASMA

[GZHoffie]

• [x] Draft code in Python
• [x] Give results on simulated data
• [x] Analysis of when this algorithm will fail
• [x] Slides for meeting

[GZHoffie]

Situations where this algorithm could go wrong:

• There are a lot of single matches, for example,

  A-C-G-G
  AGCTGTG

  In this case, my algorithm will just ignore all those matches and choose to mismatch those sequences. Possible solution: adjust the threshold of ignoring single matches according to the settings of hurdle cost and leap penalty.

• There are multiple single matches that are on the same column, for example, in the following hurdle matrix,

   011000
  0011000
  11100000
  0000000
   000000

  We may choose the wrong highway (e.g. the two 1s on the top lane) into our optimal path. Possible solution: put all highways that have the same score into our set for optimal path, then select the right one while linking.

• There are a lot of errors that the number is larger than k. Possible solution: adjust k to see how the cost changes.

[GZHoffie]

Problems with the current implementation:

• Not written in C++,
• Almost all of the time is used to find hurdle matrix and the highways.