LCSkPOA:通过通过扩展的LCSk+实现带式半全球部分顺序对齐,通过高效准确的骨干生成实现带式半全球部分顺序对齐
Minindu Weerakoon1, Christopher T Saunders2, Haynes Heaton3
1Auburn University, Auburn, AL, 36849, USA. wmw0016@auburn.edu.
BMC bioinformatics
|November 25, 2025
概括
这项研究适应了最长的共同次序与kmer匹配 (LCSk++) 算法用于部分顺序对齐 (POA) 图形. 新方法显著减少了序列对齐的内存和运行时间,而不会牺牲准确性.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 基因组学就是基因组学.
背景情况:
- 大多数多重序列对齐算法专注于全球对齐,限制了半全球和本地对齐的应用.
- 长读序列对传统的动态编程对齐方法提出了内存和运行时挑战.
- 现有的图形对齐算法如ABPOA和SPOA在对齐模式和并行处理方面存在局限性.
研究的目的:
- 为了适应最长的共同次序与kmer匹配 (LCSk++) 算法用于部分顺序对齐 (POA) 图形.
- 通过结合SIMD,带化和并行处理来提高序列对齐的效率.
- 为了在图形结构上实现灵活的对齐模式 (全球,半全球,本地).
主要方法:
- 扩展了LCSk++算法以处理图形结构,特别是POA图形.
- 综合动态编程和图形穿越以确定保护区域 (LCSk++骨干).
- 实现 SIMD,带化和并行处理,以提高计算效率.
主要成果:
- 扩展的LCSk++算法可以在POA图中为所有对齐模式 (全球,半全球,本地) 提供精确的带划分.
- 在长序列 (>30,000 bp) 中实现了显著的内存节省 (高达98%) 和运行时间减少 (高达25倍).
- 在各种数据集和长度中展示了高准确度的对齐,并行处理可提高速度150倍.
结论:
- 扩展的LCSk++算法代表了基于图形的序列对齐的重大进步.
- 为POA中的全球,本地和半全球对齐模式提供了强大的解决方案,减少内存和优化运行时间.
- 增强了POA在诸如多序列对齐和基于图的参考对齐等领域的应用.
更多相关视频
08:03Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
2.7K
07:08Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
Published on: July 14, 2015
7.6K
相关概念视频
Lattice Centering and Coordination Number
11.3K
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...
11.3K
Ligand Binding and Linkage
5.4K
Allosteric proteins have more than one ligand binding site; the binding of a ligand to any of these sites influences the binding of ligands to the other sites. When a protein is allosteric, its binding sites are called coupled or linked. In the case of enzymes, the site that binds to the substrate is known as the active site and the other site is known as the regulatory site. When a ligand binds to the regulatory site, this leads to conformational changes in the protein that can influence...
5.4K
Ligand Binding and Linkage
3.9K
3.9K
Generation of Straight or Branched Actin Filaments
3.7K
The straight or branched structure formation of actin filaments is controlled by nucleating proteins such as the formins and Arp2/3 complex. Formin-mediated assembly results in straight filaments, whereas Arp2/3 protein complex-mediated assembly results in branched actin filaments.
Arp2/3 Complex
Arp2/3 complex is a seven-subunit complex consisting of two proteins similar to actin- Arp2 and Arp3, and five other subunits that help keep Arp2 and Arp3 inactive. When required, the complex is...
Arp2/3 Complex
Arp2/3 complex is a seven-subunit complex consisting of two proteins similar to actin- Arp2 and Arp3, and five other subunits that help keep Arp2 and Arp3 inactive. When required, the complex is...
3.7K
Structural Classification of Joints
6.9K
Joints, also known as articulations, are classified based on their structural characteristics, i.e., based on whether the articulating surfaces of the adjacent bones are directly connected by fibrous connective tissue or cartilage, or whether the articulating surfaces contact each other within a fluid-filled joint cavity. These differences serve to divide the joints of the body into three structural classifications.
A fibrous joint is where the adjacent bones are united by fibrous connective...
A fibrous joint is where the adjacent bones are united by fibrous connective...
6.9K
Adaptability of Cytoskeletal Filaments
5.6K
The cytoskeleton is a complex dynamic structure performing varied functions based on cellular requirements. The adaptability of the individual filaments in the cytoskeleton determines their ability to perform various functions within the cell. It can undergo rapid reorganization during processes like cell division or remain stable for several hours as in the interphase. The adaptability of these filaments depends on stringent regulatory mechanisms. The microfilament and microtubules of the...
5.6K
