Paper Info
Title
Multiple Alignments of Data Objects and Generalized Center Star Algorithm.
Abstract
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.
Year
DOI
Venue
2017
10.3233/978-1-61499-828-0-35
Frontiers in Artificial Intelligence and Applications
Keywords
Field
DocType
edit distance,alignment,trees,graphs,center star algorithm
Computer science,Algorithm,Data objects
Conference
Volume
ISSN
Citations 
299
0922-6389
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Shin, K.11310.86
Tetsuji Kuboyama214029.36
Tetsuhiro Miyahara326732.75
Kenji Tanaka452.22