拽线法:一个构建系统发育树的新算法(英文)

DragLine(DL) method:a new algorithm to built phylogenetic tree

这篇文章要讨论的拽线法(DL)是贪婪算法的一种。和Fitch-Margoliash(FM)一样,DL也是基于距离矩阵构建系统发育树,但是和FM算法相比,DL具有低复杂度、较高的容错性和准确度高的优点。当存在误差时,DL算法只是加大了不在同一个父节点下的基因序列的距离,但能够准确的判断序列的亲缘关系,进而得到完美的进化树拓扑结构;相比之下,FM算法让各个基因序列间的距离均摊了这种误差,从而有可能将本应该具有相同父节点的基因序列分到不同的分支。

The DL Method we will present in this paper is one kind of Greedy Algorithm . As Fitch-Margoliash （FM）, DL creates the phylogenetic tree based on distance matrix, but has lower computational complexity （the complexity of DL is O（nlgn）, the complexity of FM is O（n2） ）. It is much faster, more accurate and better faulttolerant. When bias exists, DL method increases the distance between two nodes not sharing the same parent node., This results it a perfect method when it comes to the topological structure of phylogenetic tree. FM algorithm, by contrast, uses the average distance of one node to all the other nodes, which may assign two nearest gene sequences which share the same parent node into different branches.