基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).

An Improved Algorithm for the Translocation Sorting Problem of Genomes

Translocation is a canonical kind of rearrangement process in the evolution of living things. The translocation sorting problem is first proposed by Sankoff. This problem is important because it is the foundation to carry out other advanced information processing of DNA sequences. Keceioglu and Ravi first presents an approximation algorithm with ratio 2 to solve translocation sorting problem. Then Hanneihalli presents a polynomial algorithm which uses break point graph to represent the translocation distance so that to compute the translocation sequence of two genome. In this paper, an improved polynomial algorithm for the Translocation sorting problem is presented. Hanneihalli's algorithm takes O(n) space complexity to solve the problem in O(n 3) time. The improved algorithm also takes O(n) space complexity but to complete the computation in O(n 2 log n ) time. In more concretely saying, the time complexity of computing the translocation distance is improved from O(n 3) to O(n 2) ; and the time complexity of computing the translocation sequence is improved from O(n 3) to O(n 2 log n) . The improved algorithm also employs break point graph to represent the translocation distance of two genome and compute their translocation sequence. It can easily improve the time complexity to compute the translocation distance from O(n 3) to O(n 2) by designing new data structures to store the break point graphs as well as their cycles, minimum sub permutations and even isolations. The key part to improve the algorithm is how to compute the translocation sequence of two genome. This paper employs a new property in the translocation operation for the break point graph so that a new method to compute a valid translocation is found. The new property is only used for the case of existing feasible edges, which guarantees to find a feasible and valid translocation in O(n log n) time. Other cases are all easier than this specific case so the overall time complexity to compute the translocation sequences becomes O(n 2 log n).