論文

査読有り
2017年

Multiple alignments of data objects and generalized center star algorithm

Frontiers in Artificial Intelligence and Applications
  • Kilho Shin
  • ,
  • Tetsuji Kuboyama
  • ,
  • Tetsuhiro Miyahara
  • ,
  • Kenji Tanaka

299
開始ページ
35
終了ページ
45
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.3233/978-1-61499-828-0-35
出版者・発行元
IOS Press

Multiple alignments of strings have been extensively studied as an effective tool to study string-type data such as DNA. In this paper, we generalize the notion of multiple alignments of strings and introduce M -alignments. M -alignments can be defined for arbitrary data objects that consist of a finite number of components. Such objects can be strings, ordered and unordered trees, rooted and unrooted trees, directed and undirected graphs, partially ordered sets and so on. On the other hand, when we introduce costs of M -alignments, the problem to find optimal M -alignments that minimize their costs proves to be NP-hard. To solve this computational problem, we show that the center star algorithm, which is well known approximation algorithm for optimal multiple alignments of strings, can be generalized to M -alignments. When we applied the generalized center star algorithm to a real dataset of glycans, we were successful in identifying effective structural patterns of glycans that characterize the disease of leukemia.

リンク情報
DOI
https://doi.org/10.3233/978-1-61499-828-0-35
DBLP
https://dblp.uni-trier.de/rec/conf/fsdm/ShinKMT17
URL
http://dblp.uni-trier.de/db/conf/fsdm/fsdm2017.html#conf/fsdm/ShinKMT17
ID情報
  • DOI : 10.3233/978-1-61499-828-0-35
  • ISSN : 0922-6389
  • DBLP ID : conf/fsdm/ShinKMT17
  • SCOPUS ID : 85034239650

エクスポート
BibTeX RIS