Research On The Two-Species Small Phylogeny Problem Based On Simulated Annealing Algorithm

With the rapid development of molecular biology and whole-genome sequencing technology, a large amount of gene data have been produced, which make it possible to study the evolution of gene families at the molecular level. Reconstructing the genealogy of gene families based on existing biological gene can infer a reliable Phylogeny,it plays a critical role in revealing the gene family evolution. Reconstructing evolutionary histories of gene families not only contribute to studying evolutionary histories of biological.Having an evolutionary perspective of gene families is a key step towards answering many fundamental biological questions. Infer evolutionary histories of gene families has received extensive attention in recent years and developed into one of the important research areas in comparative genomics. Infer evolutionary histories of gene families has become a comparative genomics is an important research direction Research Area.In this paper,we focus on studying the Two-Species Small Phylogeny Problem based on Simulated Annealing Algorithm. Details are as follows:In order to solve the two-species SmallPhylogeny Problem in the duplication-loss model,a simulated annealing algorithm named SA2SP was showed. Firstly, an alignment algorithm named ALIGN is proposed by using the principle of maximum matching characters. An alignment is get for two given gene sequences from inserting a certain number of spaces into them. Secondly, a labeling algorithm named LABLE is presented for a given sequence alignment. The algorithm of LABLE lables the given alignment with a duplicaton-loss.An alignment algorithm was introduced to construct the initial solution;An labeling algorithm was used to construct the object function and obtain the evolution cost; and three intelligent neighborhood functions were introduced to generate neighborhood solutions by using the evolutionary characteristics of gene sequences. The ribosomal RiboNucleic Acid(rRNA) and transfer Ribonucleic Acid (tRNA) of four real bacterium were used to test the performance of SA2SP and PBLP algorithm.The experimental results show that the SA2SP algotithm has smaller evolution cost, and it is an effective method for soling the two-species SPP in the duplication-loss model.Further,we study an evolutionary model restricted to Duplications and Losses and provide the multiSA2SP algorithm to solve the two-species Small Phylogeny Problem in the duplication-loss-inversion model. Firstly, an alignment algorithm multiALIGN is proposed based on dynamic programming approach to get an alignment.Secondly,this paper present an algorithm to find an evolutionary label of minimum duplication-loss cost that is in agreement with the alignment..In order to solve the two-species Small Phylogeny Problem in the duplication-loss-inversion model,a simulated annealing algorithm named multiSA2SP was devised for the duplication-loss-inversion alignment problem.An alignment algorithm was introduced to Construct the initial solution.a labeling algorithm named multiLABLE was used to construct the object function and obtain the evolution cost.Three intelligent neighborhood functions were introduced to generate neighborhood solutions by using the evolutionary characteristics of gene sequences. The ribosomal RiboNucleic Acid(rRNA) and transfer Ribonucleic Acid (tRNA) of four real bacterium were used to test the performance of SA2SP and PBLP algorithm under restricted to duplication and loss.The experimental results show that the SA2SP algotithm has smaller evolution cost, and it is an effective method for soling the two-species SPP in the duplication-loss model. The experimental results show that themulti SA2SP algotithm has smaller evolution cost, and it is an effective method for soling the two-species SPP in the duplication-loss model.In summary, In order to solve the two-species small phylogeny problem in the duplication-loss model, a simulated annealing algorithm named SA2SP is devised based on the duplication-loss alignment problem. It can be seen from the experimental results that the SA2SP algorithm can obtain fewer evolution cost than the PBLB algorithm. In addition,we add inversion operation to duplication-loss model and present a model named duplication-loss-inversion. In order to solve the two-species small phylogeny problem in the duplication-loss-inversion model, a simulated annealing algorithm named multiSA2SP is devised for the duplication-loss-inversion aligment problem.This paper provide two algorithm to solve the two-species small phylogeny problem.