Research Article
Fast Algorithm for the Minimum Chebyshev Distance in RNA Secondary Structure
318 downloads
@INPROCEEDINGS{10.1007/978-3-030-36442-7_16, author={Tiejun Ke and Changwu Wang and Wenyuan Liu and Jiaomin Liu}, title={Fast Algorithm for the Minimum Chebyshev Distance in RNA Secondary Structure}, proceedings={Broadband Communications, Networks, and Systems. 10th EAI International Conference, Broadnets 2019, Xi’an, China, October 27-28, 2019, Proceedings}, proceedings_a={BROADNETS}, year={2019}, month={12}, keywords={RNA secondary structure Minimum Chebyshev distance RNA secondary structure comparison}, doi={10.1007/978-3-030-36442-7_16} }- Tiejun Ke
Changwu Wang
Wenyuan Liu
Jiaomin Liu
Year: 2019
Fast Algorithm for the Minimum Chebyshev Distance in RNA Secondary Structure
BROADNETS
Springer
DOI: 10.1007/978-3-030-36442-7_16
Abstract
Minimum Chebyshev distance computation between base-pair and structures cost most time while comparing RNA secondary structures. We present a fast algorithm for speeding up the minimum Chebyshev distance computation. Based on the properties of RNA dot plots and Chebyshev distance, this algorithm uses binary search to reduce the size of base pairs and compute Chebyshev distances rapidly. Compared with O() time complexity of the original algorithm, the new one takes nearly [O(log), O(1)] time.
Copyright © 2019–2024 ICST
