Biological database indexing and its applications.

Cheung Ching Fung.Thesis (M.Phil.)--Chinese University of Hong Kong, 2002.Includes bibliographical references (leaves 71-73).Abstracts in English and Chinese.Chapter 1 --- Introduction --- p.1Chapter 1.1 --- Biological Sequences --- p.2Chapter 1.2 --- User Queries on Biological Sequences --- p.4Chapter 1.3 --- Research Contributions --- p.6Chapter 1.4 --- Organization of Thesis --- p.6Chapter 2 --- Background --- p.7Chapter 2.1 --- What is a Suffix-Tree? --- p.7Chapter 2.2 --- Disk-Based Suffix-Trees --- p.9Chapter 3 --- Disk-Based Suffix Tree Constructions --- p.11Chapter 3.1 --- An Existing Algorithm: PrePar-Suff ix --- p.11Chapter 3.1.1 --- "Three Issues: Edge Splitting, Random Access and Data Skew" --- p.13Chapter 3.2 --- DynaCluster-Suffix: A New Novel Disk-Based Suffix-Tree Construction Algorithm --- p.18Chapter 4 --- Suffix Links Rebuilt --- p.29Chapter 4.1 --- Suffix-links and Least Common Ancestors --- p.29Chapter 5 --- q-Length Exact Sequence Matching --- p.35Chapter 5.1 --- q-Length Exact Sequence Matching by Suffix-Tree --- p.35Chapter 6 --- Implementation --- p.38Chapter 6.1 --- System Overview --- p.38Chapter 6.1.1 --- Index Builder --- p.39Chapter 6.1.2 --- Exact Query Processor --- p.39Chapter 6.1.3 --- Suffix Links Regenerator --- p.40Chapter 6.1.4 --- Tandem Repeats Finder --- p.40Chapter 6.2 --- Data Structures --- p.40Chapter 6.2.1 --- Representation of a Node --- p.40Chapter 6.2.2 --- An Alternative Node Representation --- p.42Chapter 6.2.3 --- Representation of a Leaf --- p.43Chapter 6.3 --- Buffering --- p.44Chapter 6.3.1 --- Page Format --- p.44Chapter 6.3.2 --- Address Translation --- p.45Chapter 6.3.3 --- Page Replacement Strategies --- p.45Chapter 7 --- A Performance Studies --- p.48Chapter 7.1 --- When Everything Can be Held In Memory --- p.52Chapter 7.2 --- When Main Memory Is Limited --- p.54Chapter 7.3 --- The Effectiveness of DNA Lengths with Fixed Memory Sizes . --- p.56Chapter 7.4 --- The Effectiveness of Memory Sizes --- p.57Chapter 7.5 --- Answering q-Length Exact Sequence Matching Queries --- p.60Chapter 7.6 --- Suffix Link Rebuilt --- p.61Chapter 8 --- Conclusions and Future Works --- p.69Chapter 8.1 --- Conclusions --- p.69Chapter 8.2 --- Future Works --- p.70Bibliography --- p.7