配列比較 by RY

• ２配列の比較は基本的な操作
• ２配列の中に一致する部分配列があるかどうかを探索するときに、配列が作る空間中の折れ線の「平行」な部分を探索するとする

# 配列１，配列２の長さ
L1<-20
L2<-10
# 配列は４要素からなる→４次元空間に配置できる
parts<-c("A","T","G","C")
# ランダムに２配列を作成
seq1<-sample(parts,replace=TRUE,L1)
seq2<-sample(parts,replace=TRUE,L2)
#配列１の中に配列２を埋め込む
randomloc<-round(runif(1)*L1)
seq1<-c(seq1[1:randomloc],seq2,seq1[(randomloc+1):L1])
#配列を空間中の折れ線座標にする関数
makeAccumMat<-function(seq,pt){
 ret<-matrix(0,length(seq),length(pt))
 basenum<-which(pt==seq[1])
 ret[1,basenum]<-1
 for(i in 2:length(ret[,1])){
  ret[i,]<-ret[i-1,]
  basenum<-which(pt==seq[i])
  ret[i,basenum]<-ret[i,basenum]+1
 }
 ret
}
#２配列を折れ線座標化する
mat1<-makeAccumMat(seq1,parts)
mat2<-makeAccumMat(seq2,parts)
#２配列の頭を揃えて、比較する関数
#２配列の距離(マンハッタン距離)の増加の様子をベクトルで返す
calcDistance<-function(mat1,mat2){
 ret<-rep(0,min(length(mat1[,1]),length(mat2[,1])))
 ret[1]<-sum(abs(mat1[1,]-mat2[1,]))
 for(i in 2:length(ret)){
  ret[i]<-ret[i-1]+sum(abs(mat1[i,]-mat2[i,]))
 }
 ret
}
#２配列の頭を揃えずに比較する
calcDistance2D<-function(mat1,mat2){
 L1<-length(mat1[,1])
 L2<-length(mat2[,1])
 shorter<-min(L1,L2)[1]
 longer<-max(L1,L2)[1]
 ret<-matrix(0,longer-shorter+1,shorter)
 
 for(i in 1:(longer-shorter+1)){
  if(shorter==L1){
   partialmat2<-mat2[i:(shorter+i-1),]
   if(i!=1){
    partialmat2<-t(t(partialmat2)-mat2[(i-1),])
   }
   ret[i,]<-calcDistance(mat1,partialmat2)
  }else{
   partialmat1<-mat1[i:(shorter+i-1),]
   if(i!=1){
    partialmat1<-t(t(partialmat1)-mat1[(i-1),])
   }

   ret[i,]<-calcDistance(partialmat1,mat2)
  }
 }
 ret
}
#seq1 seq2を比較する
DistVector<-calcDistance2D(mat1,mat2)
#最も「平行」な比較は、次の図で、y=0を示す
#ミスマッチが少ない比較は、y=0から余り離れない
matplot(t(DistVector),type="b",pch=20)