# suffix_tree_alignment

**Repository Path**: yfljx/suffix_tree_alignment

## Basic Information

- **Project Name**: suffix_tree_alignment
- **Description**: 基于后缀树的生物基因序列比对
某高级算法课的作业
- **Primary Language**: Python
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2021-05-10
- **Last Updated**: 2023-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Suffix-Tree-Alignment
这是高级算法课程(天津大学)的作业源代码，在知网上有相应的论文，此程序是复现...

### 摘要
成对序列比对是两个DNA序列、RNA序列或者蛋白质序列的比对。序列比对是基因组分析和蛋白质组分析的最常用的手段之一，能够有效发掘多个序列中的相似性。作为其他算法的基础，序列比对软件必须具备快速比对数以十亿计的高度相似序列的能力，才能满足其他序列分析工具对性能和吞吐量的需求。目前大多数的相关软件并不能解决这一问题。

本文设计并实现了基于后缀树的双序列比对算法，该算法是对传统动态规划算法的改进。针对高度相似序列的特殊性质，该算法利用后缀树最强大的字符串处理能力加速度双序列的比对，通过一次查找序列，找出两序列中所有相互匹配的片段，大幅度减少使用动态规划的算法比对片段程度，降低了时间复杂度和空间复杂度。使用真实世界的数据集，并将实验结果与生物学中最常使用的BLAST和FASTA程序对比。实验结果表明，基于后缀树的序列比对算法具有最高的比对精度和较好的比对速度。

如果您喜欢此项目或觉得还不错，欢迎star...