プローブ区間グラフの拡張MPQ木表現

• Item type: SIG Technical Reports(1)
• 公開日: 2004-01-30
• タイトル: プローブ区間グラフの拡張MPQ木表現
• タイトル / 言語: en
• タイトル: Extended MPQ - Trees for Probe Interval Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 駒澤大学自然科学教室
• 著者所属(英): en
• 著者所属(英): Komazawa University, Natural Science Faculty
• 著者名: 上原, 隆平
• 著者名(英): Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: プローブ区間グラフはDNAの構造解析のために導入されたグラフクラスで，区間グラフの自然な一般化でもある．本稿ではプローブ区間グラフのための拡張型のMPQ木構造を提案した．この木構造は可能な区間表現を自然に表現するデータ型で，O(n^3)時間で計算できる．この木構造を使うと，プローブ区間グラフの同型性がO(n^3)時間で判定できる．また，二つの未プローブなDNA切片の間の関係を特定することができる．したがってプローブ途中のDNAに対して，次にどの切片をプローブすればよいか，という指標を効率良く計算することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Probe interval graphs are introduced to deal with the physical mapping and sequencing of DNA as a generalization of interval graphs. In this paper, we propose extended MPQ-trees to represent the probe interval graphs. An extended MPQ-tree is canonical, represents all possible permutations of the intervals, and can be constructed in O(n^3) time. Thus we can solve the graph isomorphism problem for the graphs in O(n^3) time. Using the tree, we can determine the relationship of two nonprobes. Therefore, in a sense, we can find the best nonprobe that would be probed in the next experiment.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 10(2003-AL-093), p. 97-104, 発行日 2004-01-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会