Wyniki wyszukiwania - BazTech

1

Efficient alternatives to PSI-BLAST

Startek M., Lasota S., Sykulski M., Bułak A., Noé L., Kucherov G., Gambin A.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2012

|

Vol. 60, nr 3

495-505

EN

In this paper we present two algorithms that may serve as efficient alternatives to the well-known PSI BLAST tool: SeedBLAST and CTX-PSI Blast. Both may benefit from the knowledge about amino acid composition specific to a given protein family: SeedBLAST uses the advisedly designed seed, while CTX-PSI BLAST extends PSI BLAST with the context-specific substitution model. The seeding technique became central in the theory of sequence alignment. There are several efficient tools applying seeds to DNA homology search, but not to protein homology search. In this paper we fill this gap. We advocate the use of multiple subset seeds derived from a hierarchical tree of amino acid residues. Our method computes, by an evolutionary algorithm, seeds that are specifically designed for a given protein family. The seeds are represented by deterministic finite automata (DFAs) and built into the NCBI-BLAST software. This extended tool, named SeedBLAST, is compared to the original BLAST and PSI-BLAST on several protein families. Our results demonstrate a superiority of SeedBLAST in terms of efficiency, especially in the case of twilight zone hits. The contextual substitution model has been proven to increase sensitivity of protein alignment. In this paper we perform a next step in the contextual alignment program. We announce a contextual version of the PSI-BLAST algorithm, an iterative version of the NCBI-BLAST tool. The experimental evaluation has been performed demonstrating a significantly higher sensitivity compared to the ordinary PSI-BLAST algorithm.

2

Modeling Proteolysis from Mass Spectrometry Proteomic Data

Gambin A., Kluge B.

Fundamenta Informaticae

|

2010

|

Vol. 103, nr 1-4

89-104

EN

In this paper we propose a mathematical model of the proteolysis process. Protein digestion is modelled with the use of chemical master equation (CME), i.e. the system of stochastic differential equations corresponding to the network of enzymatic reactions. We present an efficient approach to model parameters’ estimation (i.e. enzyme activities) from time series of mass spectrometry data. These results extend previous results in three directions: by relaxing the stationarity of the proteolysis process assumption, by allowing cuts at arbitrary sites in the peptide sequence and by incorporating knowledge from biological databases.

3

New Metrics for Phylogenies

Bolikowski Ł., Gambin A.

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 2

199-216

EN

In this paper we propose two new metrics defined on the space of phylogenetic trees. The problem of determining how distant two trees are from each other is crucial because many various methods exist for reconstructing phylogenetic trees from molecular data. These techniques (in fact often heuristics) applied to the same data set result in significantly different trees. We investigate the basic properties of new metrics and present efficient algorithms approximating the distance between two trees for partition metric. Computational experiments, which has been performed for large family of trees justify the applicability of our algorithms. The interesting application of our framework is the identification of the ancestral paralog position in the paralog families. We propose to select the set of genes (exemplars) that minimize the partition metric distance between gene tree and species tree.

4

On different models for packet flow in Multistage Interconnection Networks

Dietzfelbiner M, Gambin A., Lasota S.

Fundamenta Informaticae

|

2001

|

Vol. 46, nr 4

287-314

EN

Multistage interconnection networks (MINs) have a number of applications in many areas, for example in parallel computing systems or high-speed communication networks. In the paper we define Markov chains describing several models of packet flow through the buffered MIN with a butterfly interconnection structure and 2 ×2 switching elements. We develop a notation together with a mathematical framework enabling to prove certain results relating the models. Moreover, we show that all considered Markov chains are ergodic and discuss relationships between stationary distributions. The important novelty is that our approach is compositional, which allows to keep the complexity of description of a very complicated network's behaviour on a reasonable and tractable level. Considerations are mostly independent of specific network topology and routing protocol, hence we expect our method to be applicable also in other contexts for stochastic models of massively parallel systems.