title: An incremental algorithm for Z-value computations.
abstract: The Z-value (Comput. Chem. 23 (1999) 333) is an extension of the Z-score that is classically used to compare sets of biological sequences. The Z-value has been successfully used to handle complete genome studies as well as analyze large sets of proteins. The Z-value computation is based on a Monte Carlo approach to estimate the statistical significance of a Smith & Waterman alignment score. Comet et al. (Comput. Chem. 23 (1999) 333) have shown that, in contrast to the alignment score, the Z-value largely reduces the bias due to the lengths and compositions of the sequences. They also described an estimator of the deviation of Z-values, that we extend in this paper in order to optimize Z-values computation. The incremental algorithm described here provides two characteristics which are usually incompatible: (i) it improves the accuracy of Z-values calculation; (ii) it reduces the time complexity (this algorithm has been named incremental because it iteratively adds random sequences to the Monte-Carlo process when needed). Results are presented, originating from the all-by-all comparison of the proteins from Saccharomyces cerevisiae and Escherichia coli.
authors.affiliation: CEA/DSV/DBJC, CEA Saclay, Gif-sur-Yvette, France. jean-christophe.aude@cea.fr
authors.forename: J C
authors.initials: JC
authors.lastname: Aude
authors.forename: A
authors.initials: A
authors.lastname: Louis
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D029968:Escherichia coli Proteins / Q000737:chemistry / Q000235:genetics; D016680:Genome, Bacterial; D016681:Genome, Fungal; D009010:Monte Carlo Method; D020543:Proteome; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D029968:Escherichia coli Proteins; D020543:Proteome; D029701:Saccharomyces cerevisiae Proteins