Combining peak- and chromatogram-based retention time alignment algorithms for multiple chromatography-mass spectrometry data sets
論文はこれ
Background:
- GC-MS,LC-MSデータのRetention Time(RT)のアラインメントは大まかに2つのカテゴリに分けられる
- Peak-based algorithms:事前のpeak detectionに対してとてもsensitiveである。ピークモデルの形やSNR(signal-to-noise ratio)などのクライテリアとの一致でpeak detectする。
- Raw data-based algorithms:uniform matrixと名付けられたbinned MS dataに基づいて実行。Uniform matrixはsignal mapsまたはbinned mass spectra間のペアワイズ類似度でDTW (Dynamic Time Warping) をするuniform matrix。多くのmass tracesを使うことはコンピュータリソースを必要とし、ノイズの傾向を増加させるかもしれない。
Methods:
- この論文では、両者のhybrid methodを2つ紹介
- BIPACEでよく対応するpeaks(Biderectional Best Hits)を抽出し、CEMAPP-DTWでglobal-alignmentを実行
- この流れで実行
Best hIts Peak Assignment and Cluster Extesion(BIPACE)
- Given a chromatogram C = {p1, p2, …, pl} as an ordered set of peaks
- m(m/z), i(intensity)をvectorとし、RT = tのピークをp = (m,i,t)とする
- つまり、RT毎に比較単位となるpを抽出している
- 2つのchromatogram の各々のpeak p,qについてsimilarity function※を定義する
- Dはretention time tolerance:peak matchingの対象となる領域を限定することで計算時間の節約
- CとC'のピークの各々について、最も類似度の高いピークを抽出し、それをBBH (Biderectional Best Hits)とする
- 次にBBHをmergeして集団(clique)にしていく
- Minimal Clique Size(MCS)はパラメータ設定
- peakを頂点、similality valueを辺としたグラフを作り、BBHをグラフ化する。complete subgraphとなるようにmergeする
CEnter-star Multiple Alignment by Pairwise Partitioned Dynamic Time Warping (CEMAPP-DTW)
- Pairwise DTW is a global alignment of two series A=(a1,a2,…,am) and B=(b1,b2,…,bn), where ai, bi∈R^L
- optimal alignmentを行うために(M+1)×(N+1)のmatrix Qを用意
- Q[i, j]には(a1,a2,…,ai) and (b1,b2…,bj)のalignmentの最適なsimilarity valueが格納される
- すると、このようなパスを作ることができる
- 最適なパスは、pairwise similaritiesの和を最大化する。
- つまり、DTW(A,B) := max (Σ pi∈P Q(pi)) (Pはパスの集合)
- 計算時は、i=j=0から始めて、垂直方向に進むか、水平方向に進むか、対角線方向に進むのうち、最もsimilality valueが増加する方向を選択し、Q(M,N)まで辿り着けばそれがDTW(A,B)となる
- パスに柔軟性を持たせるため、垂直方向、水平方向、対角線方向にはウェイトを設定する
- symmetricなDTWの場合、これらのウェイトは過適合の問題を効果的に減らすためにも使われる