Dataset Information

Fast local fragment chaining using sum-of-pair gap costs.

ABSTRACT:

Background

Fast seed-based alignment heuristics such as BLAST and BLAT have become indispensable tools in comparative genomics for all studies aiming at the evolutionary relations of proteins, genes, and non-coding RNAs. This is true in particular for the large mammalian genomes. The sensitivity and specificity of these tools, however, crucially depend on parameters such as seed sizes or maximum expectation values. In settings that require high sensitivity the amount of short local match fragments easily becomes intractable. Then, fragment chaining is a powerful leverage to quickly connect, score, and rank the fragments to improve the specificity.

Results

Here we present a fast and flexible fragment chainer that for the first time also supports a sum-of-pair gap cost model. This model has proven to achieve a higher accuracy and sensitivity in its own field of application. Due to a highly time-efficient index structure our method outperforms the only existing tool for fragment chaining under the linear gap cost model. It can easily be applied to the output generated by alignment tools such as segemehl or BLAST. As an example we consider homology-based searches for human and mouse snoRNAs demonstrating that a highly sensitive BLAST search with subsequent chaining is an attractive option. The sum-of-pair gap costs provide a substantial advantage is this context.

Conclusions

Chaining of short match fragments helps to quickly and accurately identify regions of homology that may not be found using local alignment heuristics alone. By providing both the linear and the sum-of-pair gap cost model, a wider range of application can be covered. The software clasp is available at http://www.bioinf.uni-leipzig.de/Software/clasp/.

SUBMITTER: Otto C

PROVIDER: S-EPMC3072320 | biostudies-literature | 2011 Mar

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Fast local fragment chaining using sum-of-pair gap costs.

Otto Christian C Hoffmann Steve S Gorodkin Jan J Stadler Peter F PF

Algorithms for molecular biology : AMB 20110318

<h4>Background</h4>Fast seed-based alignment heuristics such as BLAST and BLAT have become indispensable tools in comparative genomics for all studies aiming at the evolutionary relations of proteins, genes, and non-coding RNAs. This is true in particular for the large mammalian genomes. The sensitivity and specificity of these tools, however, crucially depend on parameters such as seed sizes or maximum expectation values. In settings that require high sensitivity the amount of short local match ...[more]

PMID: 21418573

Similar Datasets

Project description:Korean is a language with the verb at the end of a clause/sentence. In chaining several clauses [each consisting of a subject and a verb] in a sentence, a conjunction (e.g., -ko "and then," -ese "because, and so") is suffixed to the verb of a non-final clause. Korean has an extensive set of conjunctions that connect to the next clause, expressing temporal, causal, and contrastive relations among others. In this paper, I lay out a developmental trajectory of clause chaining construction in Korean based on longitudinal and cross-sectional data samples, focusing on conjunctive forms and functions as well as morphological and syntactic properties of connected clauses in a sentence. The database comes from longitudinal naturalistic speech data of five children collected regularly over different time periods between 2 and 5 years of age, and from elicited descriptions of short video events from children - aged 3, 4, 6, 8, and 10 years - and adults. The results show that, at least from 2 years of age, the Korean children in the sample start connecting clauses using appropriate conjunctions. Within 6 months, they acquire several major conjunctions that express temporal, causal, conditional, and contrastive relations between events. By 4 years of age, the children's clause chains are quite adult-like in terms of the repertoire of conjunctive forms and functions, and of the morphological and syntactic features of the clauses that connect to the main clause. In particular they learn to express temporal relations that have some disjuncture between events. However, 4-year-olds still lack the ability to appropriately refer to differential subjects of the chained clauses and also to connect multiple clauses in a sentence. The elicitation data reveal that further development in clause chaining occurs over several years - with a milestone at 10 years - and through adulthood, particularly in relation to appropriate referential marking, conjunction frequency, and segmentation of a macro event into sub-events for clause-chaining construction. These developmental processes are presented from a cognitive perspective, in particular with regard to concept of temporal relation, reference specification involving two or more entities, and perceptual saliency of event type.

Dataset Information

Fast local fragment chaining using sum-of-pair gap costs.

Background

Results

Conclusions

Publications

Fast local fragment chaining using sum-of-pair gap costs.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets