Skip to content
hondoumachi edited this page Jan 14, 2021 · 20 revisions

stmsa的核心为星比对策略,主要步骤如下:

  1. 选择一条中心序列,构建后缀树。

  2. 通过后缀树得到中心序列和其它序列中的同源子序列对,刨除这些子序列后得到差异子序列对。

  3. 之后完成这些差异子序列对的比对,和同源子序列对进行拼接,得到中心序列和当前序列的完整比对结果。

  4. 最后以中心序列为媒介,融合前一步中所有序列的比对结果。

在新版本中,stmsa加入了聚类的特性,以使比对更加精确。

双序列比对中,stmsa使用了needleman-wunsch算法。

星比对基于这样一个假设:当模式串和文本串包含大于一定长度的相同子串时,该子串即为模式串和主串的同源子序列。同源区段匹配中会更详细地讨论该问题。

此外,stmsa也对软件进行了一些优化

目前,实验室正在撰写关于多序列比对的资料,目前由另一名同学维护。

Clone this wiki locally