序列比对与 A* 示例
这是使用 A* 路径查找来加速动态规划算法的示例,在本例中是序列比对问题,Levenshtein 距离是其中的一个特定实例。
O(n * e^2)与标准的 Levenshtein 距离算法不同,它运行的时间类似于n输入长度和e编辑距离的时间。它通过使用像 A* 这样的启发式算法来仅探索沿网格对角线的有希望的状态,而不是整个O(n^2)网格。
对于具有少量编辑的大文件,它比O(n^2)它所基于的简单动态编程算法要快得多,但仍然比专门的和高度优化的全局序列比对程序(如Edlib )慢得多。不同之处在于我在两个小时内编写了这个,它有 150 行代码,包括测试、调试例程和示例。
它是用 Rust 编写的,包含两个示例程序:
seqalign:读取 FASTA 格式的基因序列文件并打印对齐距离。
seqalign_plain:读取两个纯文本文件并打印对齐距离。
2022-06-12 14:05:21
5KB
算法
rust