التفاصيل البيبلوغرافية
العنوان: |
Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k-mer sets. |
المؤلفون: |
Martayan, Igor, Cazaux, Bastien, Limasset, Antoine, Marchet, Camille |
المصدر: |
Bioinformatics; 2024 Supplement, Vol. 40, pi48-i57, 10p |
مصطلحات موضوعية: |
ROTATIONAL motion, KNIVES, LIBRARIES, VOCABULARY |
مستخلص: |
Summary In this article, we introduce the Conway–Bromage–Lyndon (CBL) structure, a compressed, dynamic and exact method for representing k -mer sets. Originating from Conway and Bromage's concept, CBL innovatively employs the smallest cyclic rotations of k -mers, akin to Lyndon words, to leverage lexicographic redundancies. In order to support dynamic operations and set operations, we propose a dynamic bit vector structure that draws a parallel with Elias-Fano's scheme. This structure is encapsulated in a Rust library, demonstrating a balanced blend of construction efficiency, cache locality, and compression. Our findings suggest that CBL outperforms existing dynamic k -mer set methods. Unique to this work, CBL stands out as the only known exact k -mer structure offering in-place set operations. Its different combined abilities position it as a flexible Swiss knife structure for k -mer set management. Availability and implementation https://github.com/imartayan/CBL. [ABSTRACT FROM AUTHOR] |
|
Copyright of Bioinformatics is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
قاعدة البيانات: |
Complementary Index |