Search

Your search keyword '"Ilia Minkin"' showing total 2 results
Start Over Author "Ilia Minkin" Topic algorithms
2 results on '"Ilia Minkin"'

1. Scalable Pairwise Whole-Genome Homology Mapping of Long Genomes with BubbZ

Author

Ilia Minkin and Paul Medvedev

Subjects
Algorithms, Bioinformatics, Genomics, Science
Abstract

Summary: Pairwise whole-genome homology mapping is the problem of finding all pairs of homologous intervals between a pair of genomes. As the number of available whole genomes has been rising dramatically in the last few years, there has been a need for more scalable homology mappers. In this paper, we develop an algorithm (BubbZ) for computing whole-genome pairwise homology mappings, especially in the context of all-to-all comparison for multiple genomes. BubbZ is based on an algorithm for computing chains in compacted de Bruijn graphs. We evaluate BubbZ on simulated datasets, a dataset composed of 16 long mouse genomes, and a large dataset of 1,600 Salmonella genomes. We show up to approximately an order of magnitude speed improvement, compared with MashMap2 and Minimap2, while retaining similar accuracy.

Published
2020
Full Text
View/download PDF

2. TwoPaCo: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes

Author

Paul Medvedev, Son Pham, and Ilia Minkin

Subjects
0301 basic medicine, Statistics and Probability, FOS: Computer and information sciences, Primates, Theoretical computer science, Computer science, 0206 medical engineering, Population, 02 engineering and technology, Biochemistry, Genome, De Bruijn graph, 03 medical and health sciences, symbols.namesake, Computer Science - Data Structures and Algorithms, Animals, Humans, Quantitative Biology - Genomics, Data Structures and Algorithms (cs.DS), education, Molecular Biology, De Bruijn sequence, Genomics (q-bio.GN), education.field_of_study, Genome, Human, Genomics, Data structure, Graph, Computer Science Applications, Computational Mathematics, 030104 developmental biology, Computational Theory and Mathematics, FOS: Biological sciences, symbols, Human genome, 020602 bioinformatics, Algorithms, Software
Abstract

Motivation de Bruijn graphs have been proposed as a data structure to facilitate the analysis of related whole genome sequences, in both a population and comparative genomic settings. However, current approaches do not scale well to many genomes of large size (such as mammalian genomes). Results In this article, we present TwoPaCo, a simple and scalable low memory algorithm for the direct construction of the compacted de Bruijn graph from a set of complete genomes. We demonstrate that it can construct the graph for 100 simulated human genomes in less than a day and eight real primates in Availability and Implementation Our code and data is available for download from github.com/medvedevgroup/TwoPaCo. Supplementary information Supplementary data are available at Bioinformatics online.

Published
2016

Catalog

Books, media, physical & digital resources
See catalog results