零樣本距離問題 The Zero Exemplar Distance Problem
所謂零樣本距離問題是給定兩個包含重複基因的基因組，尋找這兩個基因組各自的樣本基因組，滿足得到的兩個樣本基因組之間的距離為零。對於任何合理的距離度量，兩個樣本基因組之間的距離為0，意味著這兩個樣本基因組相同。因此，零樣本距離問題也可以理解為給定任意兩個序列，這兩個序列可能包含重複的元素，兩個序列能否得到一個相同的子序列，這個子序列滿足對於序列中的每個元素恰好出現一次。每個元素出現多於一次不行，少於一次也不行。
為了度量這個問題的難度，人們考慮這個問題的子問題。人們想到的一種方法是限制每個序列中重複元素可以重複的次數，假如每個序列中每個重複元素至多可以重複出現三次，有人用3SAT問題歸約到此問題，證明此問題是NP-hard的。當每個序列都不出現重複元素，這個問題很好解決，只要看看兩個序列是否相等便可。當兩個序列中，其中一個序列不出現重複元素，另一個序列可以出現重複元素，這個問題也可以解決，只需求這兩個序列的最長公共子序列，並且看看得到的最長公共子序列是否包含序列中所有的元素。當兩個序列中，每個元素在一個序列中出現一次，在另一個序列中出現至少一次，這個問題也可以多項式求解。當兩個序列中，每個重複元素至多可以重複出現兩次，那麼這個問題的複雜度如何呢？這個問題也被別人證明是NP-hard的。因為零樣本距離問題是NP-hard的。所以樣本距離問題不存在近似比的近似算法。
分享到:
閱讀更多 zhexuewei 的文章
