De Bruijn系列に属するCR系列の実現と次世代シーケン

2014 年度国立六大学連携コンソーシアム新技術説明会
De Bruijn 系列に属する CR 系列の実現と次世代シーケン
サーへの応用
藤崎礼志
金沢大学理工研究域電子情報学系准教授
2014 年 11 月 14 日
従来技術とその問題点
擬似乱数生成とその応用
i.i.d. 系列，マルコフ系列: 暗号系，通信系，計算機科学系，経済 (ファイ
ナンス) 系
Dyck 言語，Motzkin 言語: バイオ (遺伝子解析) 系
文脈自由言語
Dyck言語
Motzkin言語
正規言語
i.i.d.
マルコフ
de Bruijn系列
DNA 塩基: A(アデニン)–T(チミン)
G(グアニン)–C(シトニン)
de Bruijn グラフ Gn = (Vn, An) は頂点集合 Vn = {0, 1}n−1 と辺集合
An = {0, 1}n を有するオイラーグラフである．
1100
11100
11000
01100
11110
11111
1111
1110
11101
11010
1101
10100
1010
0111
11011
10111
1011
0110
10101
10110
01010
0101
01011
0100
01001
01101
01110
01111
11001
1001
00100
10010
00101
0010
01000
1000
10001
00010
0001
00000
10000
0000
00001
10011
00011
00111
0011
図 1
De Bruijn グラフ G5.
n−1 −n
長さ 2n の de Bruijn 系列は，22
与えられる．
個存在し，Gn のオイラー路として
Velvet [D.R.Zerbino and E. Birney, 2008] de nove シーケンス
解析に de Bruijn グラフ，CR(complement reverse) 系列を利用する
アルゴリズム
DNA/RNA リード (read) を頂点とする de Bruijn グラフを構成
↓
n−1
−n 個存在) の中から，CR 系列を利用し，
オイラー路 (22
DNA/RNA シーケンスを推定
このとき，de Bruijn グラフは CR 部分グラフに分割されると仮定される
[P.A.Pevzner, H.Tang, and M.S.Waterman, 2001]
一方，本発明では，n = 2p + 1 において，p が素数の場合に，CR 系列の
総数を陽に与える．
−1
rX は
定義 1 {0, 1} 上の系列 X = (Xi)N
i=0 に対して，X の反転
r X = (X )0
i i=N −1 で定義される．
a ∈ {0, 1} に対して，a を用いて，a の補数を表す，即ち，0 = 1 および
1 = 0．
定義により， r ( r X ) = X , (X ) = X ，および r X = r X ．
X ≃ r X ならば，または同等であるが，X ≃ r X ならば，X は CR
(complement reverse) 系列と呼ばれる．定義により， X が CR 系列で
あれば、X と r X もそうである．ここで，X ≃ Y は X と Y が巡回順序
に関して同値であることを表す．
補題 1 (Fredricksen, SIAM Review, 1982) 偶数 n ≥ 4 に対して，
X ̸≃ r X .
一方， [Fredricksen, SIAM Review, 1982] において， n = 5 に対
して，X ≃ r X が起こると指摘された．実際， n = 5 に対して，32 対の
CR 系列が存在する．その様な CR 系列の一例が与えられた:
例 1 (Fredricksen, SIAM Review, 1982)
X = 11111001000101011101100000110100
は X ≃ r X を満たす．
Fredricksen の問題
n (≥ 3) が奇数であるとき常に CR 系列が存在することを示せ．
任意の奇数 n に対して，長さ 2n の de Bruijn 系列に含まれる全ての CR
系列を生成するアルゴリズムを提案する．
新技術の特徴
de Bruijn グラフから CR グラフを構成し，全ての CR 系列を生成する．
1100
11000
1100
11001
1010 λ 1010
1010
0011 λ 1100
0011 λ 1100
01010
0101
0011
10100
0100
01001
1001
00100
10010
00101
0010
01000
1000
10001
00010
0001
10011
00011
0011
図 2
1010 に同伴する CR グラフ
00000
10000
0000
00001
新技術の従来技術との比較
DNA/RNA シーケンサーを利用して遺伝子解析を行う際，CR 系列は決定
的な役割を果たす．しかしながら，これまで，上記 Fredricksen の問題 (1982)
は未解決であったため，アド・ホックな方法でしか CR 系列を生成することが
できなかった．新技術はこの問題を完全に解決し，高効率な遺伝子解析の基盤
技術を提供する．
想定される用途
· DNA/RNA シーケンサー
· CDMA 用拡散符号
· 擬似乱数生成
想定される業界
· 遺伝子解析を必要とする医療業界
遺伝子レベルでの成人病やがんの検査 · 早期診断 · 予防
患者への負担を少なくする抗癌剤診断薬 (コンパニオン診断薬) の開発
· 遺伝子解析を必要とする医療業界や研究所
遺伝子レベルでの成人病，がん，難病の原因究明
がん遺伝子，ドライバー遺伝子，がん抑制遺伝子の解析
実用化に向けた課題
n = 7 のとき，101010 に同伴する CR グラフに対する実験結果
CR 系列の数 ∆(101010) = 417792.
10101001010000101100011001001000100110000010000000111
λ11100001101000111λ111000101010
↓
Z = 10101001010000101100011001001000100110000010000
00011101001111000101010
↓
Z rZ
↓
X (CR-系列)
n ≥ 9 の場合の系列実現には高性能 WS が必要
企業への期待
DNA/RNA シーケンサーの開発，遺伝子解析システムの開発，遺伝子解析
キット製品開発に関しては，これまで米国が主流であったが，最近，中国での
研究開発が目まぐるしい．
新技術は高効率な遺伝子解析の基盤技術を提供しますので，国内企業による独
自の DNA/RNA シーケンサーの開発，遺伝子解析システムの開発，遺伝子
解析キット製品開発に期待いたします．
本技術に関する知的財産権
·
·
·
·
発明の名称：符号生成装置、符号生成方法、通信装置、解析装置
出願番号：特願 2013-166128
出願人：金沢大学
発明者：藤崎礼志
お問い合わせ先
金沢大学ティ・エル・オー
ライセンシングアソシエイト吉田真弓
ＴＥＬ 076-264-6115
ＦＡＸ 076-234-4018
e-mail [email protected]

Download Report