---
# System prepended metadata

title: 'ADA 6.4: Space-Efficient Sequence Alignment 省空間的序列比對'
tags: [ADA 6.4]

---

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

### Space-Efficient
就是在表格上走 shortest-path(最短路徑)
![](https://i.imgur.com/0ui4gGQ.png)

### Shortest path in Graph
假設可以有一個中間點位置，可以讓起點到中間，中間到終點，是最短的路徑。
![](https://i.imgur.com/orDYmIr.png)

### The Problem is which intermediate point is the shortest
所以還是必須要逐點計算
![](https://i.imgur.com/JfMDiXt.png)

#### step1
![](https://i.imgur.com/rePMt4C.png)

### step2
![](https://i.imgur.com/5OyOEPU.png)

### step3
![](https://i.imgur.com/neaEYQA.png)

### step4
![](https://i.imgur.com/OE4kus2.png)

### step5
![](https://i.imgur.com/Mw5JCs1.png)

### step6
![](https://i.imgur.com/CrQKlzG.png)

### step7
![](https://i.imgur.com/dvtXtKd.png)

### step8
![](https://i.imgur.com/RcFXecn.png)

### step9
![](https://i.imgur.com/xczTDJy.png)

### step10
![](https://i.imgur.com/730mY9f.png)

### step11
![](https://i.imgur.com/n2ma5xr.png)

### step12
![](https://i.imgur.com/RfHx8i1.png)

## Conclusion

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