一种新的相似性度量及其在DNA序列相似性分析中的应用(英文)

A New Similarity Measure and Its Application in Similarity Analysis of DNA Sequences

衡量序列之间距离的传统方法是通过局部比对或者全局比对来实现的,其运算的时间复杂度和空间复杂度随着序列长度的增加而急剧上升.本文提出一种新的相似性度量,它是建立在Lempel-Ziv复杂度基础之上的,不需要通过序列之间的比对来实现,其时间和空间复杂度比传统方法降低了很多.用这种新的相似性度量的方法可以算出序列间的相似性矩阵,以此来刻画不同序列之间的距离.为了说明此方法的可靠性,最后对多个物种DNA序列作了相似性分析.

Traditional measure of sequences distance require a local or global alignment and therefore its time and space complexity will increase with the length of sequences increasing. Here, we propose a new similarity measure based on Lempel-Ziv complexity. It works on unaligned sequences and therefore decrease the time and space complexity . A similarity matrix deduced from our method is then outlined to illustrate the similarity of different sequences. In order to demonstrate its validity, we constrcted a phylogenetic tree at last.