Research And Implementation Of Algorithm For Minimum Breakpoint Median From PQ-trees

Bioinformatics is a complex subject which contains a variety of related knowledge such as biology, computer science and so on. Bioinformatics is an interdisciplinary which blend of biology, computer science, mathematics, information science and many other disciplines. According to Darwin’s evolutionary biology, biologists generally agree that there is a genetic pedigree relationship between species, in order to describe the genetic pedigree relationship, scientists have proposed biological evolutionary tree. Biological evolutionary tree is a tree diagram and the structure or the information can represent different species is stored in the biological evolutionary tree branch. According to genetic distance, different species will be placed on different branches of the tree diagram to form the evolutionary tree which can show relationships and evolutionary history of different species. However, when constructing evolutionary trees, what kind of information to represent the species is a problem which is worth thinking, now it is widely recognized that we can construct evolutionary trees with genomic sequences, and genomic sequences can represent its corresponding species.With the advances in technology, humans get a lot of genome sequences with biological experiments. The genome sequences are useful for the study of biological evolution history. Given this, biologists have proposed that we can use genomic sequences to construct evolutionary trees.When constructing evolutionary trees, we can measure the genetic relationship between species according to the similarity of genome sequences. Because ancestral species has elapsed, we can not obtain the complete genome of ancestral species, and we can only obtain genomic fragments of the ancestral species, then we can speculate consecutive genetic region of ancestral genomes. Therefore when store ancestral genomes, we should consider the characteristics of ancestral genomes. This paper use PQ-tree to store ancestral genomes. PQ-tree is a particular data structure wchic can encode large sets of permutations. And for existing genomes, this paper will store the existing genomes with permutations.The degree of homology between different species has a great relationship with the similarity of genome sequences, so that we can compare the degree of similarity between genome sequences of different species, and to analyze the evolutionary history. In measuring the degree of similarity among different genome sequences, we can use sequence alignment to determine the differences between the genomic sequences. When compare genomic sequences, we should have a standard to quantify the degree of similarity between the genomic sequences, this paper will measure the similarity of genomic sequences based on the breakpoint distance.In evolutionary tree, leaf nodes represent existing species genomes, and this paper uses permutations to store the existing species genomes. The internal nodes represent ancestral genomes, and we use PQ-tree to store ancestral genomes. It is because the ancestral genomes and existing genomes have same basic constituent elements, PQ-tree and permutations contain the same elements. In order to determine the evolutionary relationships between ancestral species and existing species, we need to measure the degree of similarity between the ancestral genomes and existing genomes, namely we need to measure the distance between PQ-tree and the known permutations. In this article, we will analyze and solve minimum breakpoint median from PQ-trees based on the measurement of breakpoint distance.The main contents of this paper are as follows:1. this paper will analyze and prove the complexity of the minimum breakpoint median from PQ-trees, the conclusion is when p≥2 the problem is NP-Complete.2. This paper will prove when p= 1, the problem is fixed papermeters teactable and this paper will propose a algorithm. And we will implement and verify the algorithm.