A Novel Model for DNA Sequence Similarity Analysis Based on Graph Theory

Determination of sequence similarity is one of the major steps in computational phylogenetic studies. As we know, during the evolution history, not only DNA mutations for individual nucleotide but also subsequence rearrangements occurred. It has been one of major tasks for computational biologists to develop novel mathematical descriptors for similarity analysis such that various of mutation phenomena information would be involved simultaneously. In this paper, different from traditional ways (eg, nucleotide frequency, geometric representations) as bases for construction of mathematical descriptors, we will construct a novel mathematical descriptors based on graph theory. In particular, for each DNA sequence, we will set up a weighted directed graph. The adjacency matrix of the directed graph will be used to induce a representative vector for DNA sequence. This new approach measures similarity based on both ordering and frequency of nucleotides so that much more information are involved. As an application, the method is tested on a set of 0.9-kb mtDNA sequences of twelve different primate species. All output phylogenetic trees with various distance estimations have the same topology, and are generally consistent with the reported results from early studies, which proves the new method's efficiency; we also test the new method on simulated data set, which shows our new method performs better than traditional globally alignment method when subsequence rearrangements happen a lot during evolutionary history.