CLAGen: a tool for clustering and annotating gene sequences using a suffix tree algorithm

Most multiple gene sequence alignment methods rely on conventions regarding the score of a multiple alignment in pairwise fashion. Therefore, as the number of sequences increases, the runtime of sequencing expands exponentially. In order to solve the problem, this paper presents a multiple sequence alignment method using a linear-time suffix tree algorithm to cluster similar sequences at one time without pairwise alignment. After searching for common subsequences, cross-matching common subsequences were generated, and sometimes inexact matching was found. So, a procedure aimed at masking the inexact cross-matching pairs was suggested here. In addition, BLAST was combined with a clustering tool in order to annotate the clusters generated by suffix tree clustering. The proposed method for clustering and annotating genes consists of the following steps: (1) construction of a suffix tree; (2) searching and overlapping common subsequences; (3) grouping subsequence pairs; (4) masking cross-matching pairs; (5) clustering gene sequences; (6) annotating gene clusters by the BLAST search. The performance of the proposed system, CLAGen, was successfully evaluated with 42 gene sequences in a TCA cycle (a citrate cycle) of bacteria. The system generated 11 clusters and found the longest subsequences of each cluster, which are biologically significant.     

Calculating the SNP-effective sample size from an alignment

MOTIVATION: The number of Single Nucleotide Polymorphisms (SNPs) detectable in an alignment is a function of the length and the number of the aligned sequences. The latter is called sample size. However, a typical alignment, for instance obtained as a BLAST-search result of a query sequence against an EST database, does not evenly cover the query sequence. Therefore, it is usually not clear what the actual sample size is. RESULTS: We present a method to calculate the effective sample size, called n(eff), for a given BLAST alignment. This method takes into account that multiple coverage contributes only logarithmically to the SNP yield of a given sequence stretch. We show that the effective sample size n(eff) is usually much smaller than would be expected for a given amount of coverage and illustrate this with two typical examples.     

一种新的EST聚类方法

该研究发展了一种EST（expressed sequence tag）聚类方法（ESTClustering）,用于分析大规模EST测序中所产生的大量数据,以获得高质量,非重复表达序列,该方法在聚类过程中采用MEGABLAST工具对一致序列进行序列同源比较,并用phrap程序对每一EST簇进行拼接检验。这一聚类策略能降低测序错误带来的影响,有效识别基因家族成员,并避免选择性剪接的干扰,与NCB（National Center for Biotechnology Information）的UniGene clustering）方法相比,ESTClustering的聚类结果可以更好地反映表达序列的多样性,用ESTClustering对112256条拟南芥EST聚类测试,产生23581个EST簇,其中13597个EST簇有对应拟南芥基因组编码序列,与该基因组中有EST作为依据的预测基因数目接近。应用该方法对收集的147191条水稻EST序列进行聚类,形成33896个EST簇。     

蛋白质序列与EST序列的反翻译联配

随着大规模技术的进步,收录到数据库中的序列很快,其中大多是未知功能的ＥＳＴｓ（表达序列标签,Ｅｘｐｒｅｓｓｅｄ Ｓｅｑｕｅｎｃｅ Ｔａｇｓ）,一般通过蛋白南－ＥＳＴ序列联配来实验ＥＳＴ的功能提示。由于ＥＳＴ含有５％左右的误差,特别严重的是其中的移框误差,用通常的方法将ＥＳＴ按６个框翻译为蛋白南序列再进行联配难以处理移框误差问题。通过考虑ＥＳＴ序列各种可能的误差,将氨基酸序列反翻译为核苷酸序列,在核     

Estimating and comparing the rates of gene discovery and expressed sequence tag (EST) frequencies in EST surveys

MOTIVATION: Expressed sequence tag (EST) surveys are an efficient way to characterize large numbers of genes from an organism. The rate of gene discovery in an EST survey depends on the degree of redundancy of the cDNA libraries from which sequences are obtained. However, few statistical methods have been developed to assess and compare redundancies of various libraries from preliminary EST surveys. RESULTS: We consider statistics for the comparison of EST libraries based upon the frequencies with which genes occur in subsamples of reads. These measures are useful in determining which one of several libraries is more likely to yield new genes in future reads and what proportion of additional reads one might want to take from the libraries in order to be likely to obtain new genes. One approach is to compare single sample measures that have been successfully used in species estimation problems, such as coverage of a library, defined as the proportion of the library that is represented in the given sample of reads. Another single library measure is an estimate of the expected number of additional genes that will be found in a new sample of reads. We also propose statistics that jointly use data from all the libraries. Analogous formulas for coverage and the expected numbers of new genes are presented. These measures consider coverage in a single library based upon reads from all libraries and similarly, the expected numbers of new genes that will be discovered by taking reads from all libraries with fixed proportions. Together, the statistics presented provide useful comparative measures for the libraries that can be used to guide sampling from each of the libraries to maximize the rate of gene discovery. Finally, we present tests for whether genes are equally represented or expressed in a set of libraries. Binomial and chi2 tests are presented for gene-by-gene comparisons of expression. Overall tests of the equality of proportional representation are presented and multiple comparisons issues are addressed. These methods can be used to evaluate changes in gene expression reflected in the composition of EST libraries prepared from different tissue types or cells exposed to different environmental conditions. AVAILABILITY: Software will be made available at http://www.mathstat.dal.ca/~tsusko     

trEST, trGEN and Hits: access to databases of predicted protein sequences

High throughput genome (HTG) and expressed sequence tag (EST) sequences are currently the most abundant nucleotide sequence classes in the public database. The large volume, high degree of fragmentation and lack of gene structure annotations prevent efficient and effective searches of HTG and EST data for protein sequence homologies by standard search methods. Here, we briefly describe three newly developed resources that should make discovery of interesting genes in these sequence classes easier in the future, especially to biologists not having access to a powerful local bioinformatics environment. trEST and trGEN are regularly regenerated databases of hypothetical protein sequences predicted from EST and HTG sequences, respectively. Hits is a web-based data retrieval and analysis system providing access to precomputed matches between protein sequences (including sequences from trEST and trGEN) and patterns and profiles from Prosite and Pfam. The three resources can be accessed via the Hits home page (http://hits. isb-sib.ch).     

Fast sequence clustering using a suffix array algorithm

MOTIVATION: Efficient clustering is important for handling the large amount of available EST sequences. Most contemporary methods are based on some kind of all-against-all comparison, resulting in a quadratic time complexity. A different approach is needed to keep up with the rapid growth of EST data. RESULTS: A new, fast EST clustering algorithm is presented. Sub-quadratic time complexity is achieved by using an algorithm based on suffix arrays. A prototype implementation has been developed and run on a benchmark data set. The produced clusterings are validated by comparing them to clusterings produced by other methods, and the results are quite promising. AVAILABILITY: The source code for the prototype implementation is available under a GPL license from http://www.ii.uib.no/~ketil/bio/.     

基于PC/Linux的核酸序列电子延伸系统的构建及其应用

新基因全长cDNA序列的获得常常是分子生物学工作者面临的难题。人类基因组计划及其相关计划的实施导致了大量表达序列标签(EST)的产生。利用一定的生物信息学算法,这些EST序列往往可用来对新基因片段进行延伸。采用Linux操作系统,利用Blast软件和Phrap软件以及EST数据库在微机上构建了EST序列的电子延伸系统,并对来自于人胎肝的11386条EST序列和511条插入片段全长cDNA序列进行了电子延伸,结果显示8373条EST序列和389条插入片段全长cDNA序列得到了程度不等的延伸,部分结果通过RACE实验得到证实。该套系统可高效地、规模化进行EST序列的延伸,可为通过实验获得新基因全长cDNA序列提供重要线索。 Abstract:Normally it is difficult to obtain full-length cDNA sequence of novel genes.More and more expressed sequence tags(ESTs) have been obtained since the start-up of human genome project.Powerful system is badly needed for data mining on these EST sequences.Based on a personal computer coupled with Linux operating system and EST database,the Blast software and Phrap software were used to construct a platform for in silico elongation of ESTs in our lab.The performance was tested using 11386 EST sequences and 511 partial-length cDNA sequences.Results demonstrated that 8373 EST and 389 cDNA sequence were elongated using this system.Thus the platform seems to be a fast way for full-length cDNA sequence cloning of new genes.     

Estimation of P-values for global alignments of protein sequences.

MOTIVATION: The global alignment of protein sequence pairs is often used in the classification and analysis of full-length sequences. The calculation of a Z-score for the comparison gives a length and composition corrected measure of the similarity between the sequences. However, the Z-score alone, does not indicate the likely biological significance of the similarity. In this paper, all pairs of domains from 250 sequences belonging to different SCOP folds were aligned and Z-scores calculated. The distribution of Z-scores was fitted with a peak distribution from which the probability of obtaining a given Z-score from the global alignment of two protein sequences of unrelated fold was calculated. A similar analysis was applied to subsequence pairs found by the Smith-Waterman algorithm. These analyses allow the probability that two protein sequences share the same fold to be estimated by global sequence alignment. RESULTS: The relationship between Z-score and probability varied little over the matrix/gap penalty combinations examined. However, an average shift of +4.7 was observed for Z-scores derived from global alignment of locally-aligned subsequences compared to global alignment of the full-length sequences. This shift was shown to be the result of pre-selection by local alignment, rather than any structural similarity in the subsequences. The search ability of both methods was benchmarked against the SCOP superfamily classification and showed that global alignment Z-scores generated from the entire sequence are as effective as SSEARCH at low error rates and more effective at higher error rates. However, global alignment Z-scores generated from the best locally-aligned subsequence were significantly less effective than SSEARCH. The method of estimating statistical significance described here was shown to give similar values to SSEARCH and BLAST, providing confidence in the significance estimation. AVAILABILITY: Software to apply the statistics to global alignments is available from http://barton.ebi.ac.uk. CONTACT: geoff@ebi.ac.uk     

Genetic mapping of the wheat dimeric α-amylase inhibitor multi-gene family using allele-specific primers based on intergenomic SNPs

Single nucleotide polymorphisms (SNPs) identified in EST sequences can be used to map expressed genes. Though SNPs are useful markers for genetic mapping, SNP mapping of genes in common wheat is challenging because the genetic complement of wheat consists of three closely related genomes (designated A, B, and D), and most genes are present in triplicate sets. Mapping multi-gene family members is further complicated by the fact that it is difficult to distinguish SNP differences between the various paralogs from those between the different genomes. We have developed a PCR-based method for assigning wheat EST sequences to their proper genetic loci by first identifying and mapping SNPs that distinguish the three genomes. To develop this method, we focused on EST sequences encoding the dimeric α-amylase inhibitors (WDAI), The WDAI coding regions of hexaploid wheat were aligned. The sequences were classified into three groups based on nucleotide variations. Twenty-two SNPs were identified that distinguish the three groups. Group-specific primers based on these SNPs were designed to permit selective amplification of each group. The chromosomal location of each group was then determined using Group 3 ditelosomic lines of Chinese Spring. Groups 1 and 2 were assigned to chromosome locations 3DS and 3BS, respectively, whereas no sequence could be assigned to 3AS. A remarkable feature of this method is the ability to discriminate the location of homoeologous multigenes in the three genomes of wheat. This strategy can be useful for assigning unknown wheat EST sequences to specific chromosomes.     

Support vector machines for separation of mixed plant-pathogen EST collections based on codon usage

MOTIVATION: Discovery of host and pathogen genes expressed at the plant-pathogen interface often requires the construction of mixed libraries that contain sequences from both genomes. Sequence identification requires high-throughput and reliable classification of genome origin. When using single-pass cDNA sequences difficulties arise from the short sequence length, the lack of sufficient taxonomically relevant sequence data in public databases and ambiguous sequence homology between plant and pathogen genes. RESULTS: A novel method is described, which is independent of the availability of homologous genes and relies on subtle differences in codon usage between plant and fungal genes. We used support vector machines (SVMs) to identify the probable origin of sequences. SVMs were compared to several other machine learning techniques and to a probabilistic algorithm (PF-IND) for expressed sequence tag (EST) classification also based on codon bias differences. Our software (Eclat) has achieved a classification accuracy of 93.1% on a test set of 3217 EST sequences from Hordeum vulgare and Blumeria graminis, which is a significant improvement compared to PF-IND (prediction accuracy of 81.2% on the same test set). EST sequences with at least 50 nt of coding sequence can be classified using Eclat with high confidence. Eclat allows training of classifiers for any host-pathogen combination for which there are sufficient classified training sequences. AVAILABILITY: Eclat is freely available on the Internet (http://mips.gsf.de/proj/est) or on request as a standalone version. CONTACT: friedel@informatik.uni-muenchen.de.     

GS-Aligner: a novel tool for aligning genomic sequences using bit-level operations

A novel algorithm, GS-Aligner, that uses bit-level operations was developed for aligning genomic sequences. GS-Aligner is efficient in terms of both time and space for aligning two very long genomic sequences and for identifying genomic rearrangements such as translocations and inversions. It is suitable for aligning fairly divergent sequences such as human and mouse genomic sequences. It consists of several efficient components: bit-level coding, search for matching segments between the two sequences as alignment anchors, longest increasing subsequence (LIS), and optimal local alignment. Efforts have been made to reduce the execution time of the program to make it truly practical for aligning very long sequences. Empirical tests suggest that for relatively divergent sequences such as sequences from different mammalian orders or from a mammal and a nonmammalian vertebrate GS-Aligner performs better than existing methods. The program and data can be downloaded from http://pondside.uchicago.edu/~lilab/ and http://webcollab.iis.sinica.edu.tw/~biocom.     

PALMA: mRNA to genome alignments using large margin algorithms

MOTIVATION: Despite many years of research on how to properly align sequences in the presence of sequencing errors, alternative splicing and micro-exons, the correct alignment of mRNA sequences to genomic DNA is still a challenging task. RESULTS: We present a novel approach based on large margin learning that combines accurate splice site predictions with common sequence alignment techniques. By solving a convex optimization problem, our algorithm-called PALMA-tunes the parameters of the model such that true alignments score higher than other alignments. We study the accuracy of alignments of mRNAs containing artificially generated micro-exons to genomic DNA. In a carefully designed experiment, we show that our algorithm accurately identifies the intron boundaries as well as boundaries of the optimal local alignment. It outperforms all other methods: for 5702 artificially shortened EST sequences from Caenorhabditis elegans and human, it correctly identifies the intron boundaries in all except two cases. The best other method is a recently proposed method called exalin which misaligns 37 of the sequences. Our method also demonstrates robustness to mutations, insertions and deletions, retaining accuracy even at high noise levels. AVAILABILITY: Datasets for training, evaluation and testing, additional results and a stand-alone alignment tool implemented in C++ and python are available at http://www.fml.mpg.de/raetsch/projects/palma     

Sequencing RNA by a combination of exonuclease digestion and uridine specific chemical cleavage using MALDI-TOF.

The determination of DNA sequences by partial exonuclease digestion followed by Matrix-Assisted Laser Desorption Time of Flight Mass Spectrometry (MALDI-TOF) is a well established method. When the same procedure is applied to RNA, difficulties arise due to the small (1 Da) mass difference between the nucleotides U and C, which makes unambiguous assignment difficult using a MALDI-TOF instrument. Here we report our experiences with sequence specific endonucleases and chemical methods followed by MALDI-TOF to resolve these sequence ambiguities. We have found chemical methods superior to endonucleases both in terms of correct specificity and extent of sequence coverage. This methodology can be used in combination with exonuclease digestion to rapidly assign RNA sequences.     

Resolving tylenchid evolutionary relationships through multiple gene analysis derived from EST data

Sequence-based phylogenetic analyses typically are based on a small number of character sets and report gene trees which may not reflect the true species tree. We employed an EST mining strategy to suppress such incongruencies, and recovered the most robust phylogeny for five species of plant-parasitic nematode (Meloidogyne arenaria, M. chitwoodi, M. hapla, M. incognita, and M. javanica), three closely related tylenchid taxa (Heterodera glycines, Globodera pallida, and G. rostochiensis) and a distant taxon, Caenorhabditis elegans. Our multiple-gene approach is based on sampling more than 80,000 publicly available tylenchid EST sequences to identify phylum-wide orthologues. Bayesian inference, minimum evolution, maximum likelihood and protein distance methods were employed for phylogenetic reconstruction and hypothesis tests were constructed to elucidate differential selective pressures across the phylogeny for each gene. Our results place M. incognita and M. javanica as sister taxa, with M. arenaria as the next closely related nematode. Significant differences in selective pressure were revealed for some genes under some hypotheses, though all but one gene are exclusively under purifying selection, indicating conservation across the orthologous groups. This EST-based multi-gene analysis is a first step towards accomplishing genome-wide coverage for tylenchid evolutionary analyses.