Scholarlink

<p>Distance-based methods are commonly used to reconstruct phylogenies for various applications owing to their excellent speed, scalability and theoretical guarantees. However, classical de novo algorithms are hindered by cubic time and quadratic memory complexity, making them impractical for emerging datasets containing millions of sequences. Here we present DIPPER, a distance-based tool for phylogenetic reconstruction on graphics processing units (GPUs), designed to maintain high accuracy and a low memory footprint. DIPPER employs a divide-and-conquer strategy, a placement strategy and an on-the-fly distance calculator that improve runtime and memory complexity to <i>O</i>(<i>N</i>.log(<i>N</i>)) and <i>O</i>(<i>N</i>), respectively, with <i>N</i> taxa. DIPPER also maintains a low memory footprint on the GPU that is independent of the number of taxa. DIPPER outperforms existing methods in speed and memory efficiency on both simulated and real-world datasets, enabling the reconstruction of 10 million sequences in under 7 h on a single NVIDIA RTX A6000 GPU.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Ultrafast and ultralarge distance-based phylogenetics using DIPPER

  • 期刊论文

  • 发表日期：

    2026年7月8日

查看全文
  • Sumit Walia,
  • Zexing Chen,
  • Yu-Hsiang Tseng,
  • Yatish Turakhia

摘要

Distance-based methods are commonly used to reconstruct phylogenies for various applications owing to their excellent speed, scalability and theoretical guarantees. However, classical de novo algorithms are hindered by cubic time and quadratic memory complexity, making them impractical for emerging datasets containing millions of sequences. Here we present DIPPER, a distance-based tool for phylogenetic reconstruction on graphics processing units (GPUs), designed to maintain high accuracy and a low memory footprint. DIPPER employs a divide-and-conquer strategy, a placement strategy and an on-the-fly distance calculator that improve runtime and memory complexity to O(N.log(N)) and O(N), respectively, with N taxa. DIPPER also maintains a low memory footprint on the GPU that is independent of the number of taxa. DIPPER outperforms existing methods in speed and memory efficiency on both simulated and real-world datasets, enabling the reconstruction of 10 million sequences in under 7 h on a single NVIDIA RTX A6000 GPU.