Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 박희진 | - |
dc.date.accessioned | 2018-04-19T11:30:31Z | - |
dc.date.available | 2018-04-19T11:30:31Z | - |
dc.date.issued | 2013-01 | - |
dc.identifier.citation | Theoretical Computer Science, 14 January 2013, 468, p.92-101 | en_US |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | https://www.sciencedirect.com/science/article/pii/S0304397512010481 | - |
dc.identifier.uri | https://repository.hanyang.ac.kr/handle/20.500.11754/69782 | - |
dc.description.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. | en_US |
dc.description.sponsorship | This work was supported by NAP of Korea Research Council of Fundamental Science & Technology. The ICT at SeoulNational University provides research facilities for this study. This research was supported by Basic Science ResearchProgram through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science andTechnology (2012-0003214). This work was supported by the National Research Foundation of Korea (NRF) grant funded bythe Korea government(MEST) (No. 2012-0006999) and the Proteogenomic Research Program through the National ResearchFoundation of Korea funded by the Korean Ministry of Education, Science and Technology. This work was supported by theNational Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 20120006492). This workwas partly supported by the IT R&D program of MKE/KEIT [10038768, The Development of Supercomputing System for theGenome Analysis] and the Industrial Strategic technology development program (10041971, Development of Power EfficientHigh-Performance Multimedia Contents Service Technology using Context-Adapting Distributed Transcoding) funded bythe Ministry of Knowledge Economy (MKE, Korea) and Basic Science Research Program through the National ResearchFoundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2009-0090441 & 2012-014892)and Inha University Research Grant. | en_US |
dc.language.iso | en | en_US |
dc.publisher | Elsevier Science B.V., Amsterdam. | en_US |
dc.subject | Consensus strings | en_US |
dc.subject | Circular strings | en_US |
dc.subject | Multiple alignments | en_US |
dc.subject | EFFICIENT ALGORITHMS | en_US |
dc.subject | SUBSTRING PROBLEMS | en_US |
dc.subject | CLOSEST | en_US |
dc.subject | PEPTIDES | en_US |
dc.title | Finding consensus and optimal alignment of circular strings | en_US |
dc.type | Article | en_US |
dc.relation.no | 14 | - |
dc.relation.volume | 468 | - |
dc.identifier.doi | 10.1016/j.tcs.2012.11.018 | - |
dc.relation.page | 92-101 | - |
dc.relation.journal | THEORETICAL COMPUTER SCIENCE | - |
dc.contributor.googleauthor | Lee, T. | - |
dc.contributor.googleauthor | Na, J. C. | - |
dc.contributor.googleauthor | Park, H. | - |
dc.contributor.googleauthor | Park, K. | - |
dc.contributor.googleauthor | Sim, J. S. | - |
dc.relation.code | 2012209449 | - |
dc.sector.campus | S | - |
dc.sector.daehak | COLLEGE OF ENGINEERING[S] | - |
dc.sector.department | DEPARTMENT OF COMPUTER SCIENCE | - |
dc.identifier.pid | hjpark | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.