Scholarlink

The Cosine Distance on Minimal Absent Word Sets, CD-MAWS in short, was recently introduced for alignment-free phylogeny estimation. Here we introduce a refined CD-MAWS method, significantly reducing computational complexity from \(\mathcal {O}(km^3 n + km^2 n \log n)\) to \(\mathcal {O}(knm+nm^2)\) while maintaining tree quality. Here, m is the number of species, n is the size of the whole genome of a species, and k is the maximum length of a minimal absent word (MAW). This advancement is achieved through a revised cosine distance calculation method, binary encoding of MAWs, and the adoption of suffix automata for MAW generation, addressing the main computational bottleneck and setting a better runtime for alignment-free phylogenetic analysis.

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

An Efficient Implementation of Cosine Distance on Minimal Absent Word Sets Using Suffix Automata

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Mohammad Tamimul Ehsan,
  • Sk. Sabit Bin Mosaddek,
  • M Saifur Rahman

摘要

The Cosine Distance on Minimal Absent Word Sets, CD-MAWS in short, was recently introduced for alignment-free phylogeny estimation. Here we introduce a refined CD-MAWS method, significantly reducing computational complexity from \(\mathcal {O}(km^3 n + km^2 n \log n)\) to \(\mathcal {O}(knm+nm^2)\) while maintaining tree quality. Here, m is the number of species, n is the size of the whole genome of a species, and k is the maximum length of a minimal absent word (MAW). This advancement is achieved through a revised cosine distance calculation method, binary encoding of MAWs, and the adoption of suffix automata for MAW generation, addressing the main computational bottleneck and setting a better runtime for alignment-free phylogenetic analysis.