Sort Algorithm Based On The First Descending Squad Flip Design And Realization

The genome reversal sorting is of great importance in research and practice field. This paper mainly discusses the sorting algorithm. The genome reversal sorting aims at calculating the least reversal sorting times between genomes, which is called the reversal distance between genomes. Hannenhalli and his group put forward the oriented genome reversal sorting through polynomial-time solutions, and the best-known arithmetic time complexity is O (n~2). And Capara has testified the unoriented genome reversal sorting to NP-Hard.The present unoriented genome reversal sorting algorithms are often too complex and unimplemented. The paper puts forward a new heuristic algorithm named FDSR Algorithm, and implements the algorithm by programming. FDSR can calculate a genome permutation sized 193 within 0.01 second and 5000 within 1.282 seconds under PentiumIII800/256M platform. It should be noted that the correctness of our algorithm has been demonstrated in this paper. We validate the optimization by program and the result shows that 68 values are best ones derived from 100 lesser genomes by FDSR method.The soul of FDSR Algorithm is finding the descending strip in permutation and then make a corresponding reversal operation between the last item and the con-adjacent one every time. However, the difficulty shows that permutation needs to transform to acquire decreasing strips when they do not present.Our program is outlined as follows: setting and initializing certain memory space for the permutation, then reading the items and checking the validity of permutation. If the validity check passes the program will make break-points conversion and sorting by reversal is continued. Otherwise, the procedure will stop.The innovations of this paper can be described in four aspects.(1) This research brings forward the concept of breakpoint-form, which is the part between two break points. By reversing the breakpoint-form, the number of the break points can be reduced little by little and reaches the target genome.