mds演算法

A. 請教各位 matlab mds演算法的問題，希望各位慷慨解囊，感激不盡。

調用函數在哪？主函數呢？

B. （十一）MDS演算法

 從降維的層面來說，由於MDS是一種降維方法，那麼它和PCA等其他降維方式有什麼不同呢，什麼樣的場景適用於使用MDS呢？與PCA不同的是， MDS保證了原始數據點之間的距離與降維後數據點的距離一致 。
 另一方面，假如我們只知道一組點之間的距離，我們如何反演出它的相對坐標？這也是MDS可以做到的。
 MDS的這種降維是繼承了原始數據空間中的歐式距離度量。使得數據點能在低維空間重構其相對位置。
 舉個例子，比如如果用歐式距離度量兩種商品的相似度，那麼，商品特徵繁多，我們就需要在不破壞商品之間的這種相似度的情況下對數據進行降維。
 再比如我們手頭只有一個鄰接矩陣，代表飛機墜機後的殘骸之間的距離，現在新來了一個殘骸，多個聲吶探測後能夠計算出這個殘骸與其他所有殘骸的距離，但是我們無法得知其具體位置，那麼我們可以通過MDS反演出其相對距離，那麼我們只要知道其中一個殘骸的位置，這個殘骸的位置也就很明朗了。根據這個相對距離縮放到真實距離就行。

 我們現在給出構造性證明：
 首先是必要性：
即：

 證明：
 
 矩陣A的列平均:
 矩陣A的行平均:
 矩陣A的整體平均:
 那麼：

 所以：


由此可得，B一定是一個對稱半正定矩陣，必要性證畢。

 接著證明充分性：
即：

證明：
假設特徵值對應的矩陣為：
令 因為
那麼 ;
所以可以將 特徵分解為：
即： ;
我們算一下第 個特徵向量和第 個特徵向量的歐式距離，以確定其確實可以由距離矩陣給出。

因為
那麼
那麼
且：
所以：

這恰好證明了那麼在 維歐式空間中,點集 之間的距離可由距離矩陣 給出。充分性證畢。

那麼也就是說只要 是半正定的矩陣，那麼我們總能找到它的特徵向量 ，將對應的坐標 求出。
我們還能發現一些好玩的性質，比如因為 所以：
由於不同特徵值對應的特徵向量是正交的，那麼這個式子就告訴我們 是其中一個特徵向量。且對應特徵值為0。
也就是說：

這表明實際上，我們在保持其歐式距離結構的前提下，將坐標原點定在了所有點的均值處。
 回顧一下我們做了什麼，我們有一個距離矩陣 ，這個距離矩陣的來源可以是我們手上有一堆已有數據產生的，或者是直接給出的；我們試圖在低維或者同維度下重構它的數據點，我們首先通過 矩陣找到 矩陣， 矩陣構成 矩陣，由於距離矩陣一定是對稱半正定的， 矩陣一定也是對稱半正定的。由於 是對稱的，所以我們一定可以對它進行特徵分解: ;如果此時需要在低維下重構，那麼對特徵值排序後剔除小的，如果在同維度下重構，那麼保持原樣即可。我們最後就直接還原出其相對坐標： 。

 我們要是新來一個數據點，或者說新來一點，我只是知道它與其他所有點的距離，這樣的情況怎麼辦。
 我們可能會不假思索的回答說，這個很簡單啊，只要把點加入矩陣D中，由 變成 就好了，其他重頭再來一遍得到一個新的坐標點集 就好了。
 在數據量不是很大的情況下，這確實不失為一種好方法，但是萬一數據量很大，重頭再來的代價就讓人有點頭疼了，這就是為什麼我們要看看有什麼辦法可以繞過這樣重頭再來的過程。
假設我們新的數據點是
我們得計算一下它和已有的第 個點之間的距離：

這裡面我們什麼是已知的，什麼是未知的呢？
是我們未知的，其他都是已知的。
我們對 求和，看看是否能將一個未知量給表示成另一個未知量。

由於上面我們有說過：
所以：
因此：


將這個結果代入原式：


我們令

寫成矩陣形式：

因為
所以新加入的數據點可以由下面公式導出：

C. 新的遺傳作圖工具PolyGembler

利用遠緣作圖群體組裝多倍體植物全染色體假分子

為多倍體和高雜合植物基因組提供一種新方法

Despite advances in sequencing technologies, assembly of complex plant genomes remains elusive e to polyploidy and high repeat content. Here we report PolyGembler for grouping and ordering contigs into pseudomolecules by genetic link- age analysis. Our approach also provides an accurate method with which to detect and fix assembly errors. Using simulated data, we demonstrate that our approach is of high accuracy and outperforms three existing state-of-the-art genetic mapping tools. Particularly, our approach is more robust to the presence of missing genotype data and genotyping errors. We used our method to construct pseudomolecules for allotetraploid lawn grass utilizing PacBio long reads in combination with restric- tion site-associated DNA sequencing, and for diploid Ipomoea trifida and autotetraploid potato utilizing contigs assembled from Illumina reads in combination with genotype data generated by single-nucleotide polymorphism arrays and genotyping by sequencing, respectively. We resolved 13 assembly errors for a published I. trifida genome assembly and anchored eight unplaced scaffolds in the published potato genome.

盡管測序技術取得了進步，但由於多倍體和高重復含量，復雜植物基因組的組裝仍然難以捉摸。在這里，我們報告了通過遺傳連鎖分析將contigs分組和排序為假分子的多聚體.我們的方法也提供了一個准確的方法來檢測和修復裝配錯誤。利用模擬數據，我們證明我們的方法是高精度的，並優於現有的三種最先進的遺傳作圖工具。特別是，我們的方法對缺失基因型數據和基因型錯誤的存在更為穩健。我們利用我們的方法，利用PacBio long reads結合限制性位點相關的DNA測序，構建了異源四倍體草坪草的假分子，利用Illumina reads組裝的contigs，結合單核苷酸多態性陣列產生的基因型數據和測序法進行基因分型，對二倍體甘薯和同源四倍體馬鈴薯進行分析。我們解決了一個已發表的三裂頭馬鈴薯基因組組裝的13個裝配錯誤，並在已發表的馬鈴薯基因組中錨定了8個未定位的支架。

Introction

高質量的基因組組裝在植物基因組和遺傳分析中起著至關重要的作用。盡管近年來第三代長讀測序技術的發展顯著提高了基因組組合的連續性，但由於多倍體和高重復性，僅利用序列數據構建完整的多倍體植物基因組是不可能的。長距離連鎖信息，如物理圖譜、遺傳圖譜、光學圖譜、共線圖譜syntenic maps 、染色質相互作用和Hi-C接觸圖譜，對構建完整的基因組組合至關重要。遺傳圖譜因提供染色體尺度連鎖信息而被廣泛採用。許多高質量的植物染色體水平基因組組裝的構建涉及到遺傳連鎖圖作為構建假分子的最後一步。這個想法很簡單：構建一個與支架相關的遺傳標記的遺傳圖譜，然後用這個圖譜來錨定支架折疊來構建假分子。假分子的完整性很大程度上取決於遺傳連鎖圖的密度。為了獲得完整的染色體圖譜，遺傳標記應該覆蓋盡可能多的基因組。然而，對於一個具有大量個體的作圖群體來說，全基因組遺傳標記的發現是非常重要的。提出了利用成本效益高的下一代測序技術進行高通量遺傳標記發現的幾種方法，如表達庫的減少、限制位點相關DNA序列（radseq）和測序基因分型（GBS）。

基於NGS的高通量遺傳標記發現方法（包括簡化表示庫、RAD-seq和GBS）產生的基因型數據通常規模較大，存在大量缺失值和基因分型錯誤。對這樣的數據集進行遺傳連鎖分析是一個挑戰。傳統的遺傳作圖工具，如mamaker和R/qtl，已經針對相對較小但質量較高的標記集進行了優化。此外，這些工具是為自交系設計的。然而，自交系的發展是困難的、昂貴的和耗時的，尤其是多倍體。近年來，人們提出了幾種方法，包括OneMap、JoinMap和Lep-MAP2，但僅限於二倍體。TetraploidMap 是第一個專門設計的基於顯性和共顯性標記信息的四倍體遠緣種圖譜工具。為了充分利用單核苷酸多態性（SNP）的劑量數據，該工具後來擴展到TetraploidSNPMap 中。polymapR是另一種利用SNP劑量數據進行遠緣多倍體遺傳定位的工具。由於設計的原因，這些方法本質上對缺失值和基因分型錯誤非常敏感，因此需要對輸入的遺傳標記進行嚴格的質量控制。對於全染色體假分子的構建，這可以顯著降低遺傳連鎖圖覆蓋的基因組比例。

本文介紹了一種利用遺傳作圖技術構建多倍體全染色體假分子的新方法。這種方法依賴於一個高密度標記集在F1雜種群體和參考容器或支架上的可用性。我們首先在支架水平上對映射群體進行單倍型階段化。然後根據階段分析結果估計每對支架之間的遺傳距離，並進一步進行鏈年齡分析，構建用於構建整染色體假分子的支架的遺傳連鎖圖。該方法計算效率高，對大量缺失的基因型數據和基因分型錯誤具有魯棒性，因此可以很好地處理基於NGS的高通量遺傳標記發現方法生成的數據。利用模擬數據集，我們證明我們的方法比現有的遺傳作圖演算法有了實質性的改進，並且能夠為二倍體和四倍體基因組構建全染色體假性分子。我們將我們的方法應用於多個真實數據集的假性分子的構建，包括二倍體三葉草的GBS數據、同源四倍體馬鈴薯的SNP陣列數據和異源四倍體結縷草的RAD-seq數據。所合成的假分子與參考基因組具有很高的共線性。

Result

方法概述。 我們已經開發了一種稱為PolyGembler（多倍體遺傳連鎖裝配體）的新方法，用於通過遺傳連鎖分析來組裝多倍體基因組。圖1提供了PolyGembler的概述。該方法假設可獲得用於基因分型的全基因組數據，例如在F1遠緣家庭中收集的GBS、RAD-seq和陣列數據，以及在參考樣本或一組參考樣本或支架上高覆蓋率（即大於30倍）的全基因組序列數據。首先，將定位群體的基因分型數據映射到參考支架以調用變體（圖1a）。所得的基因型數據或等位基因深度數據用於推斷每個支架的單倍型。單倍型被用來檢測裝配誤差和計算每對支架之間的重組分數（RFs）（圖1b-d）。接下來，將支架對之間的鏈接信息用於用於構建鏈接組的基於圖的聚類演算法（圖1e）。理想情況下，每個連鎖群中的支架都來自同一染色體。通過運行多維縮放（MDS）演算法來確定每個連接組中支架的順序，並通過解決精心設計的旅行商問題（TSP）來計算支架的方向，以最小化沿鏈接圖的相鄰RFs的總和（圖1f）。最後，利用基於支架的遺傳連鎖圖來構建假分子。

discussion

我們已經描述了一種遺傳錨定方法，它利用來自繪圖群體和參考基因組組裝的基因型數據來構建染色體規模的假分子。在這個框架下已經提出了一些方法，如POPSEQ和RPGC。這些方法主要集中在集成已建立的讀映射、變數調用和遺傳映射工具，以構建組織容器或支架的計算管道。由於這些方法很大程度上依賴於傳統的遺傳映射演算法，因此它們有一些局限性。首先，它們需要高質量的遺傳標記，對基因分型錯誤和缺失數據缺乏魯棒性。然而，從全基因組基因分型序列數據，特別是低覆蓋率序列數據中，需要這樣高質量的遺傳標記的變體並不常見。其次，這些方法不能擴展到大型數據集。傳統的遺傳作圖工具被設計用來處理多達幾千個遺傳標記的數據集，但不能擴展到使用當前全基因組基因分型方法生成的數十萬個遺傳標記。最後，這些方法很少用於多倍體基因組。為了解決這些問題，我們採用了分而治之的基因錨定策略。我們首先使用隱馬爾可夫模型（HMM）在支架水平上進行單倍型分期。然後根據單倍型估計每對支架之間的遺傳距離，並進一步用於進行支架水平的連鎖分析。最後，將支架的遺傳連鎖圖譜轉化為全染色體假分子。腳手架級連接分析有效地降低了計算復雜度。由於這是一個非確定性的多項式硬問題，可能需要一個設計良好的啟發式演算法來對每個連鎖群中的標記進行排序。然而，在我們的方法中，問題的規模大大減小，這使得我們能夠將MDS演算法與精確TSP解算器CONCORDE相結合，高效、准確地排序標記。支架水平的設計也使我們能夠以高度並行的方式進行單倍型分期。在本研究中，該方法用於處理多達3348個支架的數據集。此外，單倍型分期所需的計算時間和資源與遺傳標記的數量幾乎呈線性關系，並且該方法可以輕松處理多達10000個遺傳標記的支架（擴展數據圖7）。這種高可擴展性使得該方法可以應用於其他更廣泛的基因分型技術，如全基因組或轉錄組重測序方法，這些方法可能有數百萬個遺傳標記。該方法可直接推廣到高倍體基因組。本研究以二倍體和四倍體為研究對象。然而，這種方法可以構建高倍體基因組的遺傳連鎖圖。在處理高倍性物種時，我們最大的挑戰是計算，特別是在單倍型階段化步驟。對於六倍體，隱馬爾可夫模型的隱藏狀態數增加到14400個。這是大量的狀態，但在計算上仍然是可處理的。然而，對於更高水平的倍性，計算變得困難。

單倍型定相的基本思想是用一條沿著染色體的第一個遺傳標記開始，最後一個遺傳標記結束的馬爾可夫鏈來模擬父母配子形成的過程。在PolyHap和TetraOrigin中使用了類似的模型。 PolyHap假定目標群體共享給定數量的祖先單倍型。允許在任何祖先單倍型之間進行重組，隨著祖先單倍型和倍性的增加，導致難以解決的大狀態空間。 TetraOrigin的狀態空間和我們的方法幾乎相同，除了TetraOrigin還考慮了雙歸約。在我們的方法中未考慮雙重還原，主要是因為准確鑒定它們需要高質量的基因分型數據。 TetraOrigin使用SNP陣列數據檢測了兩次還原。但是，對於低覆蓋率的GBS或RAD-seq數據，很難在不濾除可觀標記的情況下獲得如此高質量的基因型，如果我們要覆蓋整個基因組，這是不希望的。即使雙倍減少會在RF估計中引入一些偏差，但是如果四價配對很少見，則可以安全地忽略它。為了組織組裝支架，可以忽略不計。

我們已經證明了我們的方法在構建基因組組裝的全染色體假分子方面的能力。在真實的數據集中，偽分子的基因組覆蓋率從二倍體的45%到異源四倍體的92%。產生這種巨大差異的原因是輸入基因組的質量，尤其是相鄰性。輸入基因組組合的支架N50統計值分別約為43kb和2.6mb。盡管生成高質量的植物基因組組合仍然具有挑戰性，但測序技術和相關計算工具的最新進展有助於構建高度相鄰的基因組組合，即使對於非常復雜的植物基因組也是如此。在基因組組裝技術迅速發展的背景下，我們希望我們的方法能夠成為完成基因組組裝的一種選擇。

文章中主要使用了有遺傳群體的物種進行分析，但對於難於構建遺傳群體的多年生植物和一些種系復雜的自然群體是否有效還有待考證。

前三種遺傳作圖工具:OneMap, Lep-MAP2 and tetraploidSNPMap

outbred mapping populations

allotetraploid:異源四倍體

GBS：測序基因分型

RADseq：限制性位點相關DNA測序

文章鏈接： https://doi.org/10.1038/s41588-020-00717-7

D. 如何用Word製作紅頭文件和電子公章

1、打開word文檔，在插入菜單中選擇「形狀」，在下拉形狀中選擇「橢圓形」。

E. 為什麼在drtoolbox中MDS 和PCA演算法一樣的那麼MDS 不是名不符實了嗎

當mds中的矩陣採用的是距離矩陣時，降維跟PCA方法本質上是一樣的。

F. MDS加密是什麼意思

是MD5加密吧

MD5的全稱是Message-Digest Algorithm 5，在90年代初由MIT的計算機科學實驗室和RSA Data Security Inc發明，經MD2、MD3和MD4發展而來。

Message-Digest泛指位元組串(Message)的Hash變換，就是把一個任意長度的位元組串變換成一定長的大整數。請注意我使用了「位元組串」而不是「字元串」這個詞，是因為這種變換只與位元組的值有關，與字元集或編碼方式無關。

MD5將任意長度的「位元組串」變換成一個128bit的大整數，並且它是一個不可逆的字元串變換演算法，換句話說就是，即使你看到源程序和演算法描述，也無法將一個MD5的值變換回原始的字元串，從數學原理上說，是因為原始的字元串有無窮多個，這有點象不存在反函數的數學函數。

MD5的典型應用是對一段Message(位元組串)產生fingerprint(指紋)，以防止被「篡改」。舉個例子，你將一段話寫在一個叫readme.txt文件中，並對這個readme.txt產生一個MD5的值並記錄在案，然後你可以傳播這個文件給別人，別人如果修改了文件中的任何內容，你對這個文件重新計算MD5時就會發現。如果再有一個第三方的認證機構，用MD5還可以防止文件作者的「抵賴」，這就是所謂的數字簽名應用。

MD5還廣泛用於加密和解密技術上，在很多操作系統中，用戶的密碼是以MD5值（或類似的其它演算法）的方式保存的，用戶Login的時候，系統是把用戶輸入的密碼計算成MD5值，然後再去和系統中保存的MD5值進行比較，而系統並不「知道」用戶的密碼是什麼。

一些黑客破獲這種密碼的方法是一種被稱為「跑字典」的方法。有兩種方法得到字典，一種是日常搜集的用做密碼的字元串表，另一種是用排列組合方法生成的，先用MD5程序計算出這些字典項的MD5值，然後再用目標的MD5值在這個字典中檢索。

即使假設密碼的最大長度為8，同時密碼只能是字母和數字，共26+26+10=62個字元，排列組合出的字典的項數則是P(62,1)+P(62,2)….+P(62,8)，那也已經是一個很天文的數字了，存儲這個字典就需要TB級的磁碟組，而且這種方法還有一個前提，就是能獲得目標賬戶的密碼MD5值的情況下才可以。

在很多電子商務和社區應用中，管理用戶的Account是一種最常用的基本功能，盡管很多Application Server提供了這些基本組件，但很多應用開發者為了管理的更大的靈活性還是喜歡採用關系資料庫來管理用戶，懶惰的做法是用戶的密碼往往使用明文或簡單的變換後直接保存在資料庫中，因此這些用戶的密碼對軟體開發者或系統管理員來說可以說毫無保密可言，本文的目的是介紹MD5的Java Bean的實現，同時給出用MD5來處理用戶的Account密碼的例子，這種方法使得管理員和程序設計者都無法看到用戶的密碼，盡管他們可以初始化它們。但重要的一點是對於用戶密碼設置習慣的保護。

有興趣的讀者可以從這里取得MD5也就是RFC 1321的文本。http://www.ietf.org/rfc/rfc1321.txt

G. 請問當今比較流行的數據降維演算法有哪些

這個要看你的需求和數據的data distribution，找到最合適的演算法解決你的問題。
如果數據分布比較簡單，線性映射降維就夠了，比如PCA、ICA。
如果數據分布比較復雜，可能需要用到manifold learning，具體演算法比如SOM、MDS、ISOMAP、LLE，另外deep learning也可以用來做降維。