來源：麥?zhǔn)寰幊?

作者：麥?zhǔn)?

1.10人一組混檢

到了過年的時候了，你要回老家過年嗎？如果回老家過年，需要做核算檢測。我也正在猶豫中。你們做了嗎？

核酸檢測本身是一個比較費時，費力，費錢的復(fù)雜過程，所以現(xiàn)在低風(fēng)險地區(qū)都是采用的10人一組混合檢驗的。

具體來說就是將采集自10個人的10支拭子樣本集合于1個采集管中進(jìn)行核酸檢測。

混檢篩查中一旦發(fā)現(xiàn)陽性或弱陽性，將會立即進(jìn)行追溯，通知相關(guān)部門對該混采管的10個受試者暫時單獨隔離，

并重新采集單管拭子進(jìn)行復(fù)核，再確定這10個人當(dāng)中到底哪一個是陽性。

如果檢測結(jié)果是陰性，意味著這10個樣本全是陰性，混檢的10個人都是安全的。

看到這個過程后，作為程序員的我禁不住拍了一下自己的大腿，這不就是個很簡單算法嘛！

但是這個小小的算法把檢驗的成本降低了接近90%，把檢驗的速度提高了近10倍！算法真是太奇妙了！

順著這個思路，有沒有更好的算法，進(jìn)一步加快這個過程呢？理論上來說，如果用二分法，

可以把14億次檢測減少到大概23萬次左右。而現(xiàn)在10比1混合檢驗的次數(shù)大約是1.4億次。

關(guān)于算法，本文下面再討論。咱們先說一個大家關(guān)心的問題。

2.混檢是否安全

把10個人的樣本混在一起，咋一聽覺得很不靠譜，實際上還是很靠譜的。但是會不會出現(xiàn)檢驗不準(zhǔn)的情況呢？確實存在一些潛在問題。

以下專業(yè)分析來自知乎，作者：返樸https://www.zhihu.com/question/404866690/answer/1326422005

假陰性率會增加，準(zhǔn)確度下降。舉兩個假設(shè)的情況給大家解釋為什么假陰性率會增加：

情況1：假設(shè)使用的是飽受爭議的美國CDC的核酸RT-PCR檢測試劑盒。這個試劑盒一共測三個新冠基因片段，

其中兩個是新冠特異的基因片段，第三個是所有類似于SARS的冠狀病毒都有的基因片段。

除此以外，還包括一個控制探針 (control probe)針對人的RNase P基因。這個探針的目的是用來保障取樣足夠和RNA提純過程沒有出錯。

如果取樣不夠，或者RNA純化出錯導(dǎo)致RNA降解，探針就讀不出數(shù)值，檢測結(jié)果就是“無效（invalid）”，還需要重新再測。

如果有位陽性感染者，在鼻咽拭子取樣的時候，樣本量取得不夠。如果對這個樣本用美國CDC的核酸試劑盒進(jìn)行單獨的核酸檢測，雖然新冠基因是陰性，RNase P控制探針的結(jié)果也是陰性，最終結(jié)果就顯示“無效（invalid）”，還需要重新再測。

然而，如果把這個人的樣本和其他4個人混合在一起，進(jìn)行混合核酸測試——其他4位都是核酸陰性，且取到了足夠的樣本。這時，用美國CDC的核酸試劑盒去檢測5個人的混合樣本，測出新冠基因是陰性，RNase P的控制探針是陽性（表明樣本取樣提純沒有出錯），因此得出結(jié)論：這5位都是核酸陰性。那位陽性感染者得到的就是一個“假陰性”結(jié)果。

情況2：不同核酸檢測的設(shè)計不同，導(dǎo)致試劑盒的敏感度和特異性也不同。假設(shè)所用核酸試劑盒的敏感度是500個新冠RNA/毫升。有一位陽性感染者取樣，提純樣本里面的RNA以后，用1μg總RNA量來做RT-PCR，里面包含了500個新冠RNA/毫升，那么檢測結(jié)果是陽性?？墒侨绻臉颖竞推渌?個人混在一起檢測，還是用1μg總RNA量來做RT-PCR，假設(shè)是等量混合，那么他的RNA實際只占~20%。1μg總混合RNA里面大約只有100個新冠RNA/毫升。受試劑盒敏感度的限制，結(jié)果會是假陰性。

但這不是說混檢就不能實行，而是有一定的限制：

（1）每個樣本的采集量要足，否則會出現(xiàn)稀釋后出現(xiàn)假陰性的問題

（2）只對低風(fēng)險地區(qū)實行混檢

3.混檢的算法

下面用算法簡單模擬采樣數(shù)量和檢測數(shù)量，其實也不是什么算法，就是兩個數(shù)學(xué)公式：

total_pop = 1400000000  #總?cè)丝?/span> rate = 0.00001  #感染率 group_size = 10  

#每組人數(shù) check_num = 0
caiyang_num = 0 #計算采用數(shù)量：總?cè)藬?shù) + 要重復(fù)采樣的數(shù)量 caiyang_num = total_pop 

+ (total_pop * rate) * 

group_size #計算檢測次數(shù)：人數(shù)除以10 + 重復(fù)檢測數(shù) check_num = total_pop / group_size 

+ (total_pop * rate) * 

group_size print(f'采用數(shù)：{caiyang_num:,}, 檢測數(shù)量：{check_num:,}') 

運行結(jié)果：采用數(shù)：1,400,140,000.0, 檢測數(shù)量：140,140,000.0

假設(shè)感染率為10萬分之一的情況下，要采樣14億零14萬次；要檢測1億4千萬零14萬次。

如果調(diào)整每100人一組檢測：采用數(shù)：1,401,400,000.0, 檢測數(shù)量：15,400,000.0

采用數(shù)增加了100多萬次，而檢測次數(shù)減少了1億2千多萬次。也就是說分組能極大的減少檢測次數(shù)。

但是受制于準(zhǔn)確度的影響，我們這里只是探討一下算法。這些算法在計算機(jī)的數(shù)據(jù)處理上，確實起到了把效率提高幾萬，甚至幾十幾百萬次的效果。

4.用二分查找混檢

如果用二分查找法，可以進(jìn)一步減少檢測次數(shù)減少到23萬次。

這里仍然假設(shè)10萬人有一個感染，也就是10萬個人里面找一個人出來。用二分法需要找約17次，那么總的檢測次數(shù)就是：

group_size = 100000  #10萬人一組 group_num = 1400000000 / 100000 # 共1400組 from math 

import log # 

用2分法每10萬人只需要log(10w,2)，大約16次檢測 check_num = round(log(group_size, 2) * group_num)
print(f'檢測數(shù)量：{check_num:,}')

計算結(jié)果：檢測數(shù)量：232,535

雖然由于檢測準(zhǔn)確度的問題，二分法不能實施，但算法的世界真的很奧妙。大家都應(yīng)該學(xué)點編程，學(xué)點算法。

下面是二分查找法的Python非遞歸實現(xiàn)：

#二分查找法，非遞歸實現(xiàn) def binary_search(arr, x): 
    low = 0     high = len(arr) - 1     mid = 0   
    while low <= high: 
        mid = (high + low) // 2         if arr[mid] < x: 
            low = mid + 1 
        elif arr[mid] > x: 
            high = mid - 1         else: 
            return mid 
    return -1   
   arr = [ 2, 3, 4, 10, 40 ]  x = 10 result = binary_search(arr, x) 

下面是遞歸實現(xiàn)：

def binary_search(arr, low, high, x): 
      if high >= low: 
        mid = (high + low) // 2         if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
        else: 
            return binary_search(arr, mid + 1, high, x) 
    else: 
        return -1   
arr = [ 2, 3, 4, 10, 40 ] 
x = 10 result = binary_search(arr, 0, len(arr)-1, x)