| 基因组重排的反转排序的近似算法 |
| |
| 引用本文： | 李玉,李德荣,何莉敏,张勇. 基因组重排的反转排序的近似算法[J]. 洛阳师范学院学报, 2010, 29(2): 8-10 |
| |
| 作者姓名： | 李玉 李德荣 何莉敏 张勇 |
| |
| 作者单位： | 1. 内蒙古科技大学数理与生物工程学院,内蒙古,包头,014010
2. 内蒙古科技大学信息工程学院,内蒙古,包头,014010 |
| |
| 基金项目： | 内蒙古自然科学基金资助项目,内蒙古科技大学教学(教改)研究项目 |
| |
| 摘 要： | 本文主要研究基因无方向的基因组重排的反转排序问题.本文算法基于断点图的概念,给出一个时间复杂性为O(maxb3(π),nb(π)),空间复杂性为O(n)的求解近似最优解的算法,其中n为基因组中基因个数,π=(π1,π2,...πn)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据试验的结果表明,该近似算法可以求得较好的结果.
|
| 关 键 词： | 基因组重排 反转 反转排序 近似算法 |
An Approximation Algorithm for Sorting by Reversals of Genome Rearrangement |
| |
| LI Yu,LI De-rong,HE Li-min,ZHANG Yong. An Approximation Algorithm for Sorting by Reversals of Genome Rearrangement[J]. Journal of Luoyang Teachers College, 2010, 29(2): 8-10 |
| |
| Authors: | LI Yu LI De-rong HE Li-min ZHANG Yong |
| |
| Affiliation: | 1.School of Mathematics,Physics and Biological Engineering,Inner Mongolia University of Science and Technology,Baotou 014010,China;2.School of Information Engineering,Inner Mongolia University of Science and Technology,Baotou 014010,China) |
| |
| Abstract: | In the paper,we consider the problem of genome rearrangements of the unoriented gene by reversals in molecular biology.Based on the concept of a breakpoint graph,we develop an approximation algorithm for problem.The algorithm has an O（maxb^3（π）,nb（π）） time complexity and an O（n）space complexity,where n is the number of genes in genome,π=（π1,π2,...πn） is a permutation of n genes and b（π） is the number of breakpoints in permutation π.The experiments show that in most cases,our approximation algorithm can find better solution. |
| |
| Keywords: | genome rearrangement sorting by reversals reversal approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
