DNA配列のプローブ順序固定に必要な最小フラグメント集合

概要

論文の詳細を見る
ゲノム解析の手法のひとつとして、塩基の文字列(プローブ)がDNAの部分配列(フラグメント)に含まれるかどうか調べる方法がある。どのプローブがどのフラグメントに存在するかによって、プローブやフラグメントの順序が決定されていく。また、多くのフラグメントを調べるほど、プローブの順序が正確に判明していく。本稿ではプローブの順序を固定するために、どのような追加フラグメント集合が必要かについて議論する。プローブとフラグメントの関係は、フラグメントの存在するところを1、存在しないところを0として、プローブを列、フラグメントを行に対応させることにより、(0,1)-行列によって表現することができる。本稿で扱う問題は、与えられた(0,1)-行列に,新たに行を追加して、各行の1が連続するような列の順序を一意に固定する問題である。(0,1)-行列における1を連続させうる列の順序集合を表現するには、PQ木というデータ構造を用いると便利である。本稿ではこのPQ木に対し、種々の条件のもとで、プローブの順序を一意に固定するのに必要な追加フラグメント集合の性質を解析し、最小フラグメント集合を求める多項式時間アルゴリズムを示した。
社団法人電子情報通信学会の論文
2003-03-11

DNA配列のプローブ順序固定に必要な最小フラグメント集合

スポンサーリンク

概要

著者

関連論文

スポンサーリンク