Dataset Information

Improved design and analysis of practical minimizers.

ABSTRACT:

Motivation

Minimizers are methods to sample k-mers from a string, with the guarantee that similar set of k-mers will be chosen on similar strings. It is parameterized by the k-mer length k, a window length w and an order on the k-mers. Minimizers are used in a large number of softwares and pipelines to improve computation efficiency and decrease memory usage. Despite the method's popularity, many theoretical questions regarding its performance remain open. The core metric for measuring performance of a minimizer is the density, which measures the sparsity of sampled k-mers. The theoretical optimal density for a minimizer is 1/w, provably not achievable in general. For given k and w, little is known about asymptotically optimal minimizers, that is minimizers with density O(1/w).

Results

We derive a necessary and sufficient condition for existence of asymptotically optimal minimizers. We also provide a randomized algorithm, called the Miniception, to design minimizers with the best theoretical guarantee to date on density in practical scenarios. Constructing and using the Miniception is as easy as constructing and using a random minimizer, which allows the design of efficient minimizers that scale to the values of k and w used in current bioinformatics software programs.

Availability and implementation

Reference implementation of the Miniception and the codes for analysis can be found at https://github.com/kingsford-group/miniception.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Zheng H

PROVIDER: S-EPMC8248892 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Similar Datasets

Project description:System design is recognized as one of the most critical components of a software system that bridges system requirements and coding. System design also has a significant impact on testing and maintenance activities, and on further improvements during the lifespan of the software system. Software design should reflect all necessary components of the requirements in a clear and understandable manner by all stakeholders of the software system. To distinguish system elements, separation of concerns in software design is suggested. In this respect, identification of the user tasks, i.e., the tasks that need to be performed by the user, is not currently reflected explicitly in system design documents. Our main assumption in this study is that software quality can be improved significantly by clearly identifying the user tasks from those that need to be performed by the computer system itself. Additionally, what we propose has the potential to better reflect the user requirements and main objectives of the system on the software design and thereby to improve software quality. The main aim of this study is to introduce a novel notation for software developers in the frame of UML Activity Diagram (UML-AD) that enables designers to identify the user tasks and define them separately from the system tasks. For this purpose, an extension of UML-AD, named UML-ADE (UML-Activity Diagram Extended) was proposed. Afterwards, it was implemented in a serious game case for which the specification of user tasks is extremely important. Finally, its effectiveness was analyzed and compared to UML-AD experimentally with 72 participants. The defect detection performance of the participants on both diagrams with two real-life serious game scenarios was evaluated. Results show a higher level of understandability for those using UML-ADE, which in turn may indicate a better design and higher software quality. The results encourage researchers to develop specific design representations dedicated to task design to improve system quality and to conduct further evaluations of the impact of these design on each of the above mentioned potential benefits for the software systems.