Human Genome Center, Institute of Medical Science, University of Tokyo
SMAD (Statistical Model-based Algorithm Design) is a strategy that we propose
to use for designing faster algorithms against inputs that follow some
For example, we designed very fast expected linear time searching algorithms  for the fundamental problem of searching over protein 3-D structure databases, considering that the 3-D structures in the databases follow the famous statistical molecular model called the `freely-jointed chain model'. The algorithm in  runs in O(Nm) time for arbirary inputs in the worst case (where N is the database size and m is the query size), but it runs in O(N) time in average against the databases that statistically follows the model. (According to the experiments on the PDB database, the algorithm *actually* runs in linear time and is practically much faster than previous algorithms.)
 Tetsuo Shibuya, Searching Protein 3-D Structures in Linear Time, Proc.
13th Annual International Conference on Research in Computational Molecular
Biology (RECOMB 2009), 2009 LNBI 5541, pp 1-15. (Best Paper Award) (PDF file)
 Tetsuo Shibuya, Jesper Jansson and Kunihiko Sadakane, Linear-Time Protein 3-D Structure Searching with Insertions and Deletions, 9th Workshop on Algorithms in Bioinformatics (WABI 2009), LNCS, vol. 5724, pp. 310-320, 2009.
 Tetsuo Shibuya, Jesper Jansson, and Kunihiko Sadakane, Linear-Time Protein 3-D Structure Searching with Insertions and Deletions, BMC Algorithms for Molecular Biology, to appear.
 Tetsuo Shibuya, Searching Protein 3-D Structures in Linear Time, Journal of Computational Biology, to appear.
 Tetsuo Shibuya, Searching Protein 3-D Structures in Faster Than Linear Time, Journal of Computational Biology, to appear.