| Chinese abstract | 第1-11页 |
| English abstract | 第11-16页 |
| Notation index | 第16-17页 |
| Chapter 1. Introduction | 第17-26页 |
| §1.1 Motivation: background of the research | 第17-18页 |
| §1.2 The mathematics model in genome rearrangements | 第18-21页 |
| §1.2.1 Chromosome, genome and transformation | 第18-20页 |
| §1.2.2 Reversals on signed permutations | 第20-21页 |
| §1.3 The media problem | 第21-22页 |
| §1.4 Protein similarities search | 第22页 |
| §1.5 Some key concepts of algorithms | 第22-23页 |
| §1.6 Related work and new results | 第23-26页 |
| Chapter 2. Translocation Distance between Signed Genomes | 第26-43页 |
| §2.1 Introduction | 第26页 |
| §2.2 Problem formulation and preliminary results | 第26-35页 |
| §2.2.1 Translocation on signed genomes | 第26-29页 |
| §2.2.2 Problem formulation and preliminary results | 第29-35页 |
| §2.3 Linear algorithm to compute the translocation distance | 第35-42页 |
| §2.4 Conclusion | 第42-43页 |
| Chapter 3. Genomic Distance Between Signed Genomes | 第43-61页 |
| §3.1 Introduction | 第43页 |
| §3.2 Preliminary results | 第43-50页 |
| §3.2.1 Transformations on uni-chromosomal genomes | 第44-45页 |
| §3.2.2 Transformations on multi-chromosomal genomes | 第45-50页 |
| §3.2.2.1 SBRT-limited to internal reversals and translocations | 第45-46页 |
| §3.2.2.2 SBRT-the general case | 第46-50页 |
| §3.3 Linear algorithm to compute the genomic distance | 第50-60页 |
| §3.3.1 A property of a partial set | 第50-51页 |
| §3.3.2 The linear algorithm in general case | 第51-60页 |
| §3.3.3 The special case -cotailed genomes | 第60页 |
| §3.4 Conclusion | 第60-61页 |
| Chapter 4. Evolution Sequence between Signed Genomes | 第61-75页 |
| §4.1 Introduction | 第61页 |
| §4.2 Preliminaries | 第61-65页 |
| §4.2.1 Mimicking multi-chromosomal rearrangements by reversals | 第61-63页 |
| §4.2.2 Flipping | 第63-65页 |
| §4.3 Faster algorithm for SBRT | 第65-74页 |
| §4.3.1 Optimal cappings | 第65页 |
| §4.3.2 Optimal flipping | 第65-69页 |
| §4.3.3 Optimal concatenation | 第69-74页 |
| §4.4 Conclusion | 第74-75页 |
| Chapter 5. The Translocation Median Problem | 第75-86页 |
| §5.1 Introduction | 第75-76页 |
| §5.2 The median problem with unsigned data | 第76-80页 |
| §5.3 The median problem with signed data | 第80-85页 |
| §5.4 Conclusion | 第85-86页 |
| Chapter 6. Sorting Binary Strings by Reversals and by Transpositions | 第86-93页 |
| §6.1 Introduction | 第86页 |
| §6.2 Terminology and notation | 第86-87页 |
| §6.3 Reversal distance between binary strings | 第87-90页 |
| §6.4 Transposition distance between binary strings | 第90-93页 |
| Chapter 7. Approximation Algorithm of Protein Similarity Search | 第93-105页 |
| §7.1 Introduction | 第93-95页 |
| §7.2 Preliminaries | 第95-96页 |
| §7.3 Decision version of MRSOS | 第96-99页 |
| §7.4 Approximation algorithms for MRSOS-d1 | 第99-105页 |
| References | 第105-110页 |
| Acknowledgements | 第110-111页 |
| Curriculum Vitae | 第111-113页 |
| 学位论文评阅及答辩情况表 | 第113页 |
