77 0

Finding consensus and optimal alignment of circular strings

Title
Finding consensus and optimal alignment of circular strings
Author
박희진
Keywords
Consensus strings; Circular strings; Multiple alignments; EFFICIENT ALGORITHMS; SUBSTRING PROBLEMS; CLOSEST; PEPTIDES
Issue Date
2013-01
Publisher
Elsevier Science B.V., Amsterdam.
Citation
Theoretical Computer Science, 14 January 2013, 468, p.92-101
Abstract
Circular strings are different from linear strings in that the last symbol is considered to precede the first symbol. Even though circular strings are biologically important, only a few efforts have been made to solve computational problems on circular strings. In this paper, we introduce consensus problems for circular strings of length n and present the first non-trivial algorithms to find a consensus and an optimal alignment for circular strings by the Hamming distance. They are O(n(2) log n)-time algorithms for three circular strings and an O(n(3) log n)-time algorithm for four circular strings. Our algorithms are O(n/ log n) times faster than the naive algorithms directly using the solutions for the linear consensus problems, which take O(n(3)) time for three circular strings and O(n(4)) time for four circular strings. This speedup was achieved by reducing the problems into correlations and by formulating and solving systems of linear equations. Moreover, our algorithms use only O(n) space. (C) 2012 Elsevier B.V. All rights reserved.
URI
https://www.sciencedirect.com/science/article/pii/S0304397512010481http://repository.hanyang.ac.kr/handle/20.500.11754/69782
ISSN
0304-3975
DOI
10.1016/j.tcs.2012.11.018
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE