title: Filtering redundancies for sequence similarity search programs.
abstract: Database scanning programs such as BLAST and FASTA are used nowadays by most biologists for the post-genomic processing of DNA or protein sequence information (in particular to retrieve the structure/function of uncharacterized proteins). Unfortunately, their results can be polluted by identical alignments (called redundancies) coming from the same protein or DNA sequences present in different entries of the database. This makes the efficient use of the listed alignments difficult. Pretreatment of databases has been proposed to suppress strictly identical entries. However, there still remain many identical alignments since redundancies may occur locally for entries corresponding to various fragments of the same sequence or for entries corresponding to very homologous sequences but differing at the level of a few residues such as ortholog proteins. In the present work, we show that redundant alignments can be indeed numerous even when working with a pretreated non-redundant data bank, going as high as 60% of the output results according to the query and the bank. Therefore the accuracy and the efficiency of the post-genomic work will be greatly increased if these redundancies are removed. To solve this up to now unaddressed problem, we have developed an algorithm that allows for the efficient and safe suppression of all the redundancies with no loss of information. This algorithm is based on various filtering steps that we describe here in the context of the Automat similarity search program, and such an algorithm should also be added to the other similarity search programs (BLAST, FASTA, etc...).
authors.affiliation: Groupe Bioinformatique, Génomique et Traitement des Pathologies du Système Immunitaire, INSERM EMI0355, 15 rue de l'Ecole de Médecine, 75006 Paris, France.
authors.forename: Hubert
authors.initials: H
authors.lastname: Cantalloube
authors.forename: Jacques
authors.initials: J
authors.lastname: Chomilier
authors.forename: Sylvain
authors.initials: S
authors.lastname: Chiusa
authors.forename: Mathieu
authors.initials: M
authors.lastname: Lonquety
authors.forename: Jean-Louis
authors.initials: JL
authors.lastname: Spadoni
authors.forename: Jean-François
authors.initials: JF
authors.lastname: Zagury
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D017360:Arabidopsis / Q000201:enzymology / Q000235:genetics; D016384:Consensus Sequence; D004247:DNA / Q000737:chemistry; D003628:Database Management Systems; D016208:Databases, Factual; D016680:Genome, Bacterial; D018745:Genome, Plant; D006867:Hydrolases / Q000737:chemistry; D016247:Information Storage and Retrieval; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017386:Sequence Homology, Amino Acid
chemical_list: D011506:Proteins; D004247:DNA; D006867:Hydrolases