Fast Algorithm for the Minimum Chebyshev Distance in RNA Secondary Structure

Tiejun Ke; Changwu Wang; Wenyuan Liu; Jiaomin Liu

Broadband Communications, Networks, and Systems. 10th EAI International Conference, Broadnets 2019, Xi’an, China, October 27-28, 2019, Proceedings

Research Article

Fast Algorithm for the Minimum Chebyshev Distance in RNA Secondary Structure

Download

189 downloads

Cite: BibTeX Plain Text

@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

Tiejun Ke¹, Changwu Wang¹^,*, Wenyuan Liu¹, Jiaomin Liu¹

1: Yanshan University

*Contact email: wcw@ysu.edu.cn

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.

Keywords: RNA secondary structure Minimum Chebyshev distance RNA secondary structure comparison

Published: 2019-12-02
Appears in: SpringerLink

: http://dx.doi.org/10.1007/978-3-030-36442-7_16