快速且可扩展的并行外部内存构建彩色紧de Bruijn图形与乌鱼3
Jamshed Khan1, Laxman Dhulipala1, Rob Patro1
1Department of Computer Science, University of Maryland, MD 20742, USA.
bioRxiv : the preprint server for biology
|February 20, 2025
概括
鱼3是一种新的并行算法,用于构建紧的德布莱恩图形,对于高效分析大型基因组数据集至关重要. 它大大加快了生物信息学管道,用于诸如基因组组装和泛基因组学等任务.
科学领域:
- 生物信息学和计算生物学
- 基因组数据分析 基因组数据分析
- 算法开发 算法开发
背景情况:
- 基因组数据的指数增长需要可扩展的算法来进行序列分析.
- 德布莱恩图形,特别是彩色和紧的变体,对于生物信息学管道至关重要,但在规模上构建具有挑战性.
- 现有的方法在与直接从大规模数据集构建这些图形的计算需求作斗争.
研究的目的:
- 介绍一下Cuttlefish 3,一种新的并行外部内存算法,用于构建彩色紧缩de Bruijn图.
- 解决现有方法在速度和可扩展性方面的局限性,用于大规模的基因组数据分析.
- 为下游应用提供更有效的工具,例如基因组组装,索引和泛基因组学.
主要方法:
- 开发Cuttlefish 3,一个先进的并行外部存储算法.
- 实施新的算法改进,包括优化局部收缩和并行列表排名,用于连接解决方案.
- 包括一个散散化方法来减少对彩色图形计算的数据要求.
主要成果:
- 乌鱼3在构建紧的德布莱恩图表方面展示了最先进的性能.
- 该算法在各种基因组数据集的速度和可扩展性方面取得了显著的改进.
- 它在有色和无色图形构建场景中表现优于现有的方法.
结论:
- 鱼3提供了一个高效和可扩展的解决方案,用于构建彩色紧de Bruijn图.
- 该算法的新策略有效地应对大规模基因组数据带来的挑战.
- 这一进步预计将大大有利于各种生物信息学应用,这些应用需要高效的图形构造.
相关概念视频
02:33Lattice Centering and Coordination Number
13.9K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
Types of Unit Cells
Imagine taking a large number of identical...
13.9K
01:32Assembly of Complex Microtubule Structures
2.1K
Complex microtubule structures are present in resting cells and in dividing cells. In resting cells, they are responsible for maintaining the cellular architecture, tracks for intracellular transport, positioning of organelles, assembly of cilia and flagella. They mediate the bipolar spindle assembly for chromosomal segregation and positioning of the cell division plate in dividing cells. The formation of microtubule complex structures depends on the cell type, cell stage, and cell function.
2.1K
01:05Maxam-Gilbert Sequencing
10.5K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
10.5K
01:10Vector Algebra: Graphical Method
13.7K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
13.7K
01:06Parallel-axis Theorem
6.0K
The parallel-axis theorem provides a convenient and quick method of finding the moment of inertia of an object about an axis parallel to the axis passing through its center of mass. Consider a thin rod as an example. There is a striking similarity between the process of finding the moment of inertia of a thin rod about an axis through its middle, where the center of mass lies, and about an axis through its end using the conventional method. In the conventional method, the concept of linear mass...
6.0K
01:28Graphical Representation of Inequalities
455
The graph of the equation where y equals x squared forms a curve known as a parabola. This curve acts as a boundary in the coordinate plane, dividing it into distinct regions based on the relative position of points.When the equality sign in the equation is replaced with an inequality—such as greater than, less than, greater than or equal to, or less than or equal to—the graphical representation changes from a single curve into a broader shaded area that signifies the set of all...
455