区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム 北陸先端科学技術大学院大学（ＪＡＩＳＴ） 情報科学研究科 斎藤 寿樹　 清見 礼 　 上原 隆平

発表内容 区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム 区間表現 MPQ-tree 1 2 2, 4 4 3 2 2, 4 4 3 5 6 7 8 12 9 10 11 1 2 9 12 3 4 10 11 5 6 7 8 区間表現 MPQ-tree

区間グラフとは 1950年代後半に数学者の Hajös と，分子生物学者の Benzer とが独立に考えたグラフクラス 区間表現をもつグラフ それぞれの区間は各頂点に対応 2つの区間が重なっている　⇔ 　　対応する2つの頂点間に辺が存在する 1 2 3 4 5 6 1 2 3 4 I3 I1 I2 I4

区間グラフの応用 区間をDNAの断片や時間と考える 数十万～数百万の区間を処理 高速なアルゴリズムが必要 バイオインフォマティクス スケジューリング問題など 数十万～数百万の区間を処理 高速なアルゴリズムが必要 x1: ACGGTTTA x2: ATCGGAACG x3: AACGGTTTAC x4: TTTACGTGGT 断片の文字列 x1 x2 x3 x4 区間グラフ ATCGGGAACGGTTTACGTGGT 区間表現

PQ-tree 1976年にBoothらによって提案 区間グラフ用の補助データ構造 木構造(順序木) 内部ノードにはPまたはQのラベル 葉には極大クリークを割り当てる O(n)領域 区間グラフの認識(O(n+m)時間) ○：Pノード □：Qノード C1 C2 C3 C4 C7 C5 C6 PQ-tree

MPQ-tree(Modified PQ-tree) 1989年にKorteらによって提案 区間グラフを表現するデータ構造 PQ-treeの改良 各ノードに頂点集合を割り当てる O(n)領域 区間グラフの認識 区間グラフの同型性判定（O(n+m)時間） ○：Pノード □：Qノード 1 2 2, 4 4 3 5 6 7 8 12 9 10 11 MPQ-tree

MPQ-tree 葉およびPノードとQノードと呼ばれる節点を持つ順序木 Qノードはセクションと呼ばれるまとまりに分割 根から葉までのパス上に存在する頂点集合は区間グラフ上で極大クリーク Qノード 1 2 3 4 5 6 7 8 9 10 11 12 Pノード 1 2 2, 4 4 9 12 3 5 6 10 11 :P-node :Q-node 7 8 葉 MPQ-tree 区間グラフ

MPQ-tree 葉およびPノードとQノードと呼ばれる節点を持つ順序木 Qノードはセクションと呼ばれるまとまりに分割 根から葉までのパス上に存在する頂点集合は区間グラフ上で極大クリーク Qノード 1 2 3 4 5 6 7 8 9 10 11 12 Pノード 1 2 2, 4 4 9 12 3 5 6 10 11 :P-node :Q-node 7 8 葉 MPQ-tree 区間グラフ

MPQ-tree 区間表現と密接な関係がある MPQ-treeの親は区間表現において子を内包 1 10 2 3 4 5 6 7 8 9 11 12 1 2 2, 4 4 9 12 3 5 6 10 11 7 8

MPQ-tree 区間表現と密接な関係がある MPQ-treeの親は区間表現において子を内包 1 10 2 3 4 5 6 7 8 9 11 12 1 2 2, 4 4 9 12 3 5 6 10 11 7 8

MPQ-tree 対応する区間グラフが変化しない操作 Pノードの子の順序を任意に入れ替える Qノードのセクションの順序を逆順にする 1 2 2, 4 4 3 5 6 7 8 12 9 10 11 1 10 2 3 4 5 6 7 8 9 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 2, 4 4 3 5 6 7 8 12 9 10 11 1 10 9 11 12 2 3 4 5 6 7 8

今回の問題について 効率がよく単純なアルゴリズムは重要 入力:区間表現 出力: MPQ-tree 応用上の多くの問題の入力は区間表現 入力される区間の数は大量 構成する既存のアルゴリズムは複雑 グラフ表現経由 直接（PQ-tree用） 効率がよく単純なアルゴリズムは重要

既存の手法(グラフ表現経由) グラフ表現から構成 区間表現をグラフ表現に変換 グラフ表現からMPQ-treeを構成 O(n+m)時間かかる 場合分けが多く実装が複雑 1 2 区間表現 グラフ表現 MPQ-tree O(n)領域 O(n+m)時間 O(n+m)領域 O(n)領域 O(n+m)時間 1 2　 2, 4 　 4 3 5 6 7 8 12 9 10 11 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

既存の手法(区間表現からPQ-tree) O(n log n)時間 端点がソートされているときO(n)時間 decomposition tree という概念を使用するため複雑 1 2 3 4 5 6 7 8 9 10 11 12 C7 O(n log n)時間 C1 C2 C5 C6 区間表現 C3 C4 O(n)領域 PQ-tree O(n)領域

提案手法 区間表現から直接MPQ-treeを構成 O(n log n)時間 端点がソートされているときO(n)時間 単純なデータ構造（スタックなど）を用いたアルゴリズム 1 2 3 4 5 6 7 8 9 10 11 12 1 2　 2, 4 　 4 3 5 6 7 8 12 9 10 11 O(n log n)時間 区間表現 O(n)領域 MPQ-tree O(n)領域

提案手法 区間表現 コンパクトな区間表現 区間をP/Qノードおよび葉に分類 MPQ-tree 冗長性がある O(n)時間 冗長性がない 12 3 2 1 4 5 6 7 8 10 9 11 区間表現 O(n)時間 コンパクトな区間表現 1 2 3 4 5 6 7 8 9 10 11 12 区間をP/Qノードおよび葉に分類 冗長性がない 番号は規則を持つ MPQ-tree

提案手法 区間表現 コンパクトな区間表現 区間をP/Qノードおよび葉に分類 MPQ-tree O(n)時間 O(n)時間 1 3 5 6 7 2 3 4 5 6 7 8 9 10 11 12 区間表現 O(n)時間 コンパクトな区間表現 O(n)時間 1 3 5 6 7 8 12 9 10 11 区間をP/Qノードおよび葉に分類 2, 4 2 2, 4 4 O(n)時間 MPQ-tree

区間をP/Qノードおよび葉に分類 葉に分類される区間 Qノードに分類される区間 Pノードに分類される区間 区間の長さが0 他の異なる区間と互いに一部分だけ交差 Pノードに分類される区間 その他の区間

区間をP/Qノードおよび葉に分類 左から端点をスイープ 左端点iLを読み込んだとき PUSH(S,iL) 右端点iRを読み込んだとき スタックの先頭とiを比較 整合性が取れていなければQノード 例 1 一致しない 2 3Ｌ 1R 整合性が取れていないのでQノード 3 2Ｌ 1Ｌ スタック

区間をP/Qノードおよび葉に分類 左から端点をスイープ 左端点iLを読み込んだとき PUSH(S,iL) 右端点iRを読み込んだとき スタックの先頭とiを比較 整合性が取れていなければQノード 例 1 2 3Ｌ 2R 3 2Ｌ 1Ｌ スタック

区間をP/Qノードおよび葉に分類 右の端点iRを読み込んだとき Qノードに分類されている区間の右端点がすべて読み込まれたとき 例 1 2 3Ｌ 3R 3 2Ｌ 1 , 2 , 3 1Ｌ Qノードに確定 スタック

区間をP/Qノードおよび葉に分類 右の端点iRを読み込んだとき スタックの先頭とiが異なるQノード Qノードをマージ 例 1 5Ｌ 3R 2 4Ｌ 3 3Ｌ 1R 2R 4 2Ｌ 5 1Ｌ スタック

区間をP/Qノードおよび葉に分類 同じQノードに含まれる区間はスタック上で連続に存在 O(n)時間 iR O(1)時間 O(1)時間 iL アルゴリズムの実行時間 O(n)時間 …

結論 今後の課題 区間表現からMPQ-treeを構成するアルゴリズム 区間グラフの列挙（ランダム生成） 高速であることを実験的に示す O(n log n)時間で実行できる ソートされていればO(n)時間 単純なアルゴリズム 今後の課題 区間グラフの列挙（ランダム生成） 高速であることを実験的に示す