###### tags: `ADA 6.4`
# ADA 6.4: Space-Efficient Sequence Alignment 省空間的序列比對

### Space-Efficient
就是在表格上走 shortest-path(最短路徑)

### Shortest path in Graph
假設可以有一個中間點位置，可以讓起點到中間，中間到終點，是最短的路徑。

### The Problem is which intermediate point is the shortest
所以還是必須要逐點計算

#### step1

### step2

### step3

### step4

### step5

### step6

### step7

### step8

### step9

### step10

### step11

### step12

## Conclusion

一次只計算一個小區域，最差的狀況下只有step7，用到的記憶體空間最多。
但遠比直接計算起點到終點來的少。所以才是省空間的演算法。而且時間複雜度並未增加。