| Chinese abstract | 第1-12页 |
| English abstract | 第12-18页 |
| Notation index | 第18-19页 |
| Chapter 1. Introduction | 第19-31页 |
| ·Motivation: background of the research of genome rearrangement | 第19-20页 |
| ·Some key concepts of algorithms | 第20-21页 |
| ·Mathematical dcnotations | 第21-22页 |
| ·Combinatoric problems in genome rearrangements | 第22-29页 |
| ·Sorting by reversals | 第22-25页 |
| ·Sorting by transpositions | 第25-26页 |
| ·Sorting by reciprocal translocations | 第26-27页 |
| ·Sorting by bounded operations | 第27-28页 |
| ·Sorting by weighted operations | 第28页 |
| ·Sorting by mixed operations | 第28-29页 |
| ·Thesis outline | 第29-31页 |
| Chapter 2. Sorting signed permutation by fixed-length reversals | 第31-50页 |
| ·Introduction | 第31页 |
| ·Preliminaries | 第31-33页 |
| ·Equivalent Transformations | 第33-38页 |
| ·Equivalence Classes under Fixed-length Signed Reversals | 第38-49页 |
| ·For special k=1, n-1 and n | 第38-41页 |
| ·Equivalence Classes in SLPG(k, n) | 第41-43页 |
| ·Equivalence Classes in SCPG(k, n) | 第43-49页 |
| ·Conclusion | 第49-50页 |
| Chapter 3. Sorting by length weighted transpositions | 第50-66页 |
| ·Introduction | 第50页 |
| ·Preliminaries | 第50-51页 |
| ·Upper bounds on the minimum cost sufficient to sort any sequence | 第51-53页 |
| ·Lower bounds on the minimum cost sufficient to sort any sequence | 第53-57页 |
| ·Algorithms | 第57-64页 |
| ·Approximation algorithm when 0≤α＜1 | 第57-59页 |
| ·Approximation algorithms when α=1 | 第59-62页 |
| ·Approximation algorithms when 1＜α＜2 | 第62-64页 |
| ·Efficient algorithm when α≥2 | 第64页 |
| ·Conclusions and Open problems | 第64-66页 |
| Chapter 4. Sorting signed genomes by translocations and deletions/insertions | 第66-87页 |
| ·Introduction | 第66-67页 |
| ·Preliminaries | 第67-73页 |
| ·The cycle graph | 第68-69页 |
| ·The sub-permutation | 第69-70页 |
| ·The forest of SPs | 第70页 |
| ·Effects of a translocation on SPs | 第70-71页 |
| ·The translocation distance | 第71-73页 |
| ·On sorting by translocations and deletions | 第73-75页 |
| ·New definition for the cycle graph | 第73-74页 |
| ·New definition for the translocation | 第74-75页 |
| ·A lower bound on d_(td) (Π,Γ) | 第75-77页 |
| ·An approximation algorithm for sorting by translocations and deletions | 第77-83页 |
| ·Failed cases and corresponding sub-procedures | 第77-79页 |
| ·Main lemmas | 第79-82页 |
| ·The approximation algorithm | 第82-83页 |
| ·Analysis of the algorithm | 第83-85页 |
| ·Conclusions and open problem | 第85-87页 |
| Bibliography | 第87-93页 |
| Acknowledgements | 第93-94页 |
| Curriculum Vitae | 第94-96页 |
| 学位论文评阅及答辩情况表 | 第96页 |
