MAlign

MALIGN是一个对不同领域的序列执行多重对齐的库，允许使用非对称得分矩阵。多重对齐是真正的多重对齐，根据每个对齐位的整体概率进行得分，而不是一系列逐步组合的成对对齐。

尽管主要用于语言学，但它可以用于对任何类型的序列表示进行对齐，只要每个领域的元素都是可哈希的。它特别适合作为没有对得分矩阵有先验假设的情况的通用工具，这些假设可以从推断或从可观察的例子中优化（包括从不完全的数据中），以找到可以用来解释序列之间关系的局部和全局最小值。

安装和使用

该库可以作为任何标准Python库使用pip进行安装，最好是在虚拟环境中

$ pip install malign

对于大多数目的，只需将要对齐的序列传递给指定的一种可用方法（目前是默认的anw和yenksp），并将其传递给.multi_align()函数，同时指定要返回的对齐最大数量（k）即可

>> import malign                                                                                                      
>> alms = malign.multi_align(["ATTCGGAT", "TACGGATTT"], k=2)                                                   
>> print(malign.tabulate_alms(alms))                                                                                  
| Idx   | Seq   |   Score |  #0  |  #1  |  #2  |  #3  |  #4  |  #5  |  #6  |  #7  |  #8  |  #9  |
|-------|-------|---------|------|------|------|------|------|------|------|------|------|------|
| 0     | A     |   -0.29 |  A   |  T   |  T   |  C   |  G   |  G   |  A   |  -   |  T   |  -   |
| 0     | B     |   -0.29 |  -   |  T   |  A   |  C   |  G   |  G   |  A   |  T   |  T   |  T   |
|       |       |         |      |      |      |      |      |      |      |      |      |      |
| 1     | A     |   -0.29 |  A   |  T   |  T   |  C   |  G   |  G   |  A   |  -   |  -   |  T   |
| 1     | B     |   -0.29 |  -   |  T   |  A   |  C   |  G   |  G   |  A   |  T   |  T   |  T   |

得分矩阵可以由辅助方法计算得出，包括各种优化，或从JSON文件中读取

>> ita_rus = malign.ScoringMatrix()
>> ita_rus.load("docs/ita_rus.matrix")
>> alms = malign.multi_align(["Giacomo", "Яков"], k=4, method="anw", matrix=ita_rus)
>> print(malign.tabulate_alms(alms))
| Idx   | Seq   |   Score |  #0  |  #1  |  #2  |  #3  |  #4  |  #5  |  #6  |  #7  |
|-------|-------|---------|------|------|------|------|------|------|------|------|
| 0     | A     |    2.86 |  G   |  i   |  a   |  c   |  o   |  m   |  o   |      |
| 0     | B     |    2.86 |  -   |  Я   |  -   |  к   |  о   |  в   |  -   |      |
|       |       |         |      |      |      |      |      |      |      |      |
| 1     | A     |    2.29 |  G   |  i   |  a   |  c   |  o   |  m   |  o   |      |
| 1     | B     |    2.29 |  -   |  Я   |  -   |  к   |  о   |  -   |  в   |      |
|       |       |         |      |      |      |      |      |      |      |      |
| 2     | A     |    2.12 |  G   |  i   |  a   |  c   |  o   |  m   |  o   |  -   |
| 2     | B     |    2.12 |  -   |  Я   |  -   |  к   |  о   |  -   |  -   |  в   |
|       |       |         |      |      |      |      |      |      |      |      |
| 3     | A     |    2.12 |  G   |  i   |  a   |  c   |  o   |  m   |  o   |  -   |
| 3     | B     |    2.12 |  -   |  Я   |  -   |  к   |  -   |  -   |  о   |  в   |

更复杂的示例（包括矩阵插补和优化）可以在文档中找到。

变更日志

版本0.1

• 首次发布，用于内部公告、测试和社区推广

版本 0.2

• 重大修订，包括非对称的Needleman-Wunsch和Yen的k最短路径实现
• 添加评分矩阵对象
• 以一致和可重现的方式对对齐进行排序，即使对齐得分相同

版本 0.3

• 代码改进，包括类型注解和一些重构
• 允许使用任何可哈希的Python对象（不仅仅是字符串）
• 添加矩阵插补方法
• 更新文档
• 为公开公告做准备

待办事项

• 完成文档和设置readthedocs
• 考虑实现UPGMA和NJ多重对齐
• 添加用于可视化yenksp方法所用的图的函数/方法
• 在anw和yenksp中实现块和局部搜索，具有不同的起始/结束位置
• 尽可能实现记忆化
• 考虑通过添加随机间隙（pad_align）来扩展dumb_malign，作为另一个基线方法
• 允许anw在最佳得分的阈值百分比内工作
• 实现结合不同算法结果的合并方法
• 添加矩阵优化方法和演示
• 迁移到GitHub Actions

社区指南

尽管作者可以直接联系以获得支持，但建议第三方使用GitHub标准功能，例如问题报告和拉取请求，以做出贡献、报告问题或寻求支持。

贡献指南，包括行为准则，可在CONTRIBUTING.md文件中找到。

作者和引用

该库由Tiago Tresoldi开发（tiago.tresoldi@lingfil.uu.se）。

作者已从Riksbankens Jubileumsfond获得资金（协议ID：MXM19-1087:1，Cultural Evolution of Texts）。

在开发初期，作者从欧洲研究委员会（ERC）获得了欧洲联盟“地平线2020”研究和创新计划的支持（协议号：ERC Grant #715618，Computer-Assisted Language Comparison）。

如果您使用malign，请引用如下

Tresoldi, Tiago (2021). MALIGN，用于不同域上的多重非对称对齐的库。版本0.3。乌普萨拉：乌普萨拉大学。

BibTeX

@misc{Tresoldi2021malign,
  author = {Tresoldi, Tiago},
  title = {MALIGN, a library for multiple asymmetric alignments on different domains. Version 0.3},
  howpublished = {\url{https://github.com/tresoldi/malign}},
  address = {Uppsala},
  publisher = {Uppsala Universitet}
  year = {2021},
}