Reduced space sequence alignment

Motivation: Sequence alignment is the problem of finding theoptimal character-by-character correspondence between two sequences.It can be readily solved in O(n²) time and O(n²) space on aserial machine, or in O(n) time with O(n) space per O(n) processingelements on a parallel machine. Hirschberg's divide-and-conquerapproach for finding the single best path reduces space useby a factor of n while inducing only a small constant slowdownto the serial version. Results: This paper presents a family of methods for computingsequence alignments with reduced memory that are well suitedto serial or parallel implementation. Unlike the divide-and-conquerapproach, they can be used in the forward-backward (Baum-Welch)training of linear hidden Markov models, and they avoid data-dependentrepartitioning, making them easier to parallelize. The algorithmsfeature, for an arbitrary integer L, a factor proportional toL slowdown in exchange for reducing space requirement from O(n²)to O(n). A single best path member of this algorithm familymatches the quadratic time and linear space of the divide-and-conqueralgorithm. Experimentally, the O(n1.5)-space member of the familyis 15–40% faster than the O(n)-space divide-and-conqueralgorithm. Availability: The methods will soon be incorporated in the SAMhidden Markov modeling package http: //www.cse.ucs-c.edu/research/compbio/sam.html. Contact: wzrph{at}cse.ucsc.edu     

Analysis of internal loops within the RNA secondary structure in almost quadratic time

MOTIVATION: Evaluating all possible internal loops is one of the key steps in predicting the optimal secondary structure of an RNA molecule. The best algorithm available runs in time O(L(3)), L is the length of the RNA. RESULTS: We propose a new algorithm for evaluating internal loops, its run-time is O(M(*)log(2)L), M < L(2) is a number of possible nucleotide pairings. We created a software tool Afold which predicts the optimal secondary structure of RNA molecules of lengths up to 28 000 nt, using a computer with 2 Gb RAM. We also propose algorithms constructing sets of conditionally optimal multi-branch loop free (MLF) structures, e.g. the set that for every possible pairing (x, y) contains an optimal MLF structure in which nucleotides x and y form a pair. All the algorithms have run-time O(M(*)log(2)L).     

The prediction of virus mutation using neural networks and rough set techniques

Viral evolution remains to be a main obstacle in the effectiveness of antiviral treatments. The ability to predict this evolution will help in the early detection of drug-resistant strains and will potentially facilitate the design of more efficient antiviral treatments. Various tools has been utilized in genome studies to achieve this goal. One of these tools is machine learning, which facilitates the study of structure-activity relationships, secondary and tertiary structure evolution prediction, and sequence error correction. This work proposes a novel machine learning technique for the prediction of the possible point mutations that appear on alignments of primary RNA sequence structure. It predicts the genotype of each nucleotide in the RNA sequence, and proves that a nucleotide in an RNA sequence changes based on the other nucleotides in the sequence. Neural networks technique is utilized in order to predict new strains, then a rough set theory based algorithm is introduced to extract these point mutation patterns. This algorithm is applied on a number of aligned RNA isolates time-series species of the Newcastle virus. Two different data sets from two sources are used in the validation of these techniques. The results show that the accuracy of this technique in predicting the nucleotides in the new generation is as high as 75 %. The mutation rules are visualized for the analysis of the correlation between different nucleotides in the same RNA sequence.     

Isolation of a Specific Potato Tuber-Inducing Substance from Potato Leaves

Potato tuberization is induced by an unidentified "tuberizationstimulus" which is produced in the leaves. Recently, we confirmedthe occurrence of two acidic substances in the leaves whichappear to be the stimulus (Koda and Okazawa 1988). We reporthere the isolation of one of the substances from potato leaves.The molecular weight of the substance is 388. The substanceis active in inducing tuberization in vitro at a concentrationof 0.01 mg- liter^-11 (ca. 3 ? 10^-8 M). (Received April 15, 1988; Accepted June 28, 1988)     

Negative Phototropism of Vaucheria terrestris Regulated by Calcium II. Inhibition by Ca2+-Channel Blockers and Mimesis by A23187

As reported in a previous article [Kataoka (1988a) Plant CellPhysiol. 29: 1323], growing apices of the xanthophycean coenocyticalga, Vaucheria terrestris, bends away from a unilateral bluelight (BL) source, if they are simultaneously irradiated withstrong background BL in a solution containing 1–4 mM Ca²⁺.Since the negative bending is a function of the product of theexternal Ca²⁺ concentration and the fluence rate of backgroundBL, a BL-induced Ca²⁺-influx at the apex was hypothesized tobe the cause of the phototropic inversion. The present reportprovides strong evidence for this hypothesis. Addition of theCa²⁺ channel blockers, La³⁺, verapamil, nifedipine and nitrendipineto media containing 4 mM Ca²⁺ completely inhibited the phototropicinversion. By contrast, 1 µM A23187 [GenBank] (plus 4 mM Ca²⁺) notonly enhanced the phototropic inversion under background BL,but also mimicked the background BL; i.e. it caused negativebending under safe red light. Inhibition of phototropic inversionby La³⁺ is also observed under conditions where the algae areirradiated with unilateral BL for 1 week. A BL-dependent Ca²⁺influx and a consequential elevation of the cytoplasmic Ca²⁺-levelin the apical growth region must be involved in the early stepsof phototropic response. A BL-controlled opening of L-type Ca²⁺channels is also suggested. ¹A part of this study was reported at the 3rd Phycological Congressat Melbourne 1988 (Kataoka 1988b) and XXII Yamada Conferenceon Plant Water Relations and Growth Under Stress at Osaka 1989(Kataoka 1989) ²Dedicated to Prof. em. Dr. Noburo Kamiya on the occasion ofhis 77th birthday (Received May 23, 1990; Accepted July 13, 1990)     

Nudeotide Pools and Purine Metabolism in Tissue Cultures of Wild-Type Datura innoxia and Adenine-Requiring Auxotroph

Cells of the auxotrophic mutant, Ad1, of Datura innoxia requiredadenine, adenosine, or inosine for their growth on solid agarmedium which contained Murashige-Skoog salts, 2,4-dichloro-phenoxyaceticacid, and sucrose. Thirteen purine and pyrimidine nucleotidesin extracts of wild-type and Ad1 cells were separated and quantifiedby HPLC. Levels of ADP-glucose and UMP were significantly higherin Ad1 than in wild-type cells, but those of other nucleotideswas found when Ad1 cells were transferred to fresh medium withoutadenine. The rate of the biosynthesis de novo of purines, asestimated from the rate of incorporation of ¹⁴C from [2-¹⁴C]-glycine and [¹⁴C]formate into adenine nucleotides, was reducedin Ad1 cells to 21 and 13% of the wild-type rate, respectively.The activities involved in the salvage of adenine and adenosinein Ad1 cells were similar to those in wild-type cells. Ad1 cellshad the capability to convert adenine to guanine nucleotidesand guanine to adenine nucleotides. ¹ Part 27 of the series, "Metabolic Regulation in Plant CellCulture". (Received March 7, 1988; Accepted August 3, 1988)     

Effects of Propyzamide on Tobacco Cell Microtubules In Vivo and In Vitro

Treatment with propyzamide at 2 ? 10^-6 M or at higher concentrationsarrested the cell cycleat metaphase in tobacco BY-2 cells. Metaphasecells having disorganized spindle microtubulesand scatteredchromosomes began to appear within several minutes of the additionof propyzamide. Within 30 min, disrupted spindle microtubulesand dispersed chromosomes were seenin all metaphase cells. Propyzamideat 2 ? 10^-6 M or at higher concentrations also disrupted corticalmicrotubules, but disruption of cortical microtubules requiredmore time than disruption of spindle microtubules. The effectof propyzamide on microtubules was found to be readily reversible.The cells arrested at metaphase by 2 ? 10^-6 M propyzamide resumedmitosis within 2 h from the termination of treatment with propyzamide.Spindle microtubules reappeared within 15 min from the terminationof treatment with propyzamide, and the cortical microtubuleswithin 1 h. Tubulin was isolated from tobacco BY-2 cells bycolumn chromatography on ethyl Nphenylcarbamate-Sepharose 4B.On incubation with EGTA, Mg²⁺ and DMSO, the purified tobaccotubulin polymerized into microtubules. Propyzamide at 1 ? 10^-4M completely inhibitedthe polymerization of tobacco tubulin,but did not inhibit polymerization of bovine braintubulin. Tobaccotubulin was adsorbed onto a column of propyzamide-analogue-linkedSepharose 4B and then purified by chromatography on this column. (Received February 15, 1988; Accepted June 29, 1988)     

Determination of Intracellular Chloride Ion Concentration in a Halotolerant Cyanobacterium Aphanothece halophytica

Salt inhibition of RuBP carboxylase activity from Aphanothecehalophytica was caused by Cl^-, but not by K⁺ nor Na⁺. The intracellularCl^- concentration increased about 4-fold from 35 mM to 150 mM,when NaCl concentration in the culture medium was increasedfrom 0.5 M to 2.0 M. ¹Permanent address: Department of Biochemistry, Faculty of Science,Chulalongkorn University, Bangkok, Thailand (Received February 12, 1988; Accepted June 1, 1988)     

Mechanisms of P(i) regulation of the skeletal muscle SR Ca(2+) release channel

Inorganic phosphate(P_i) accumulates in the fibers of actively working musclewhere it acts at various sites to modulate contraction. To characterizethe role of P_i as a regulator of the sarcoplasmic reticulum(SR) calcium (Ca²⁺) release channel, we examined the actionof P_i on purified SR Ca²⁺ release channels,isolated SR vesicles, and skinned skeletal muscle fibers. In singlechannel studies, addition of P_i to the cis chamberincreased single channel open probability (P_o;0.079 ± 0.020 in 0 P_i, 0.157 ± 0.034 in 20 mMP_i) by decreasing mean channel closed time; mean channelopen times were unaffected. In contrast, the ATP analog,,-methyleneadenosine 5'-triphosphate (AMP-PCP), enhancedP_o by increasing single channel open time anddecreasing channel closed time. P_i stimulation of[³H]ryanodine binding by SR vesicles wassimilar at all concentrations of AMP-PCP, suggesting P_i andadenine nucleotides act via independent sites. In skinned musclefibers, 40 mM P_i enhanced Ca²⁺-inducedCa²⁺ release, suggesting an in situ stimulation ofthe release channel by high concentrations of P_i. Ourresults support the hypothesis that P_i may be an importantendogenous modulator of the skeletal muscle SR Ca²⁺ releasechannel under fatiguing conditions in vivo, acting via a mechanismdistinct from adenine nucleotides.

     

Highly Repetitive Tandem Arrays of a Short 32 bp Unit in the Pharbitis nil Genome: the RsaI Family

A highly repetitive DNA sequence of Pharbitis nil, designatedthe RsaI family, was cloned, sequenced and analyzed with respectto its genomic organization. The RsaI family is arranged intandem arrays and composed of a 32 bp repeat unit, which isthe shortest unit thus far reported for plant repetitive sequences.The RsaI family represents 3% of the total genomic DNA and thecopy number of the 32 bp unit is estimated to be about 1 ? 10⁶per haploid genome. We suggest the existence of a higher orderrepeat unit, which may be composed of hundreds of the 32 bpunits and be repeated many times in the genome. (Received May 12, 1988; Accepted July 28, 1988)     

A special-purpose processor for gene sequence analysis

Advances in computational biology have occurred primarily inthe areas of software and algorithm development; new designsof hardware to support biological computing are extremely scarce.This is due, we believe, to the presence of a non-trivial knowledgegap between molecular biologists and computer designers. Theexistence of this gap is unfortunate, as it has long been knownthat for certain problems, special-purpose computers can achievesignificant cost/performance gains over general-purpose machines.We describe one such computer here: a custom accelerator forgene sequence analysis. The accelerator implements a versionof the Needleman – Wunsch algorithm for nucleotide sequencealignment. Sequence lengths are constrained only by availablememory; the product of sequence lengths in the current implementationcan be up to 2²². The machine is implemented as two NuBus boardsconnected to a Mac IIf/x, using a mixture of TTL and FPGA technologyclocked at 10 MHz. The boards are completely functional, andyield a 15-fold performance improvement over an unassisted host.     

An examination of on-line machine learning approaches for pseudo-random generated data

A pseudo-random generator is an algorithm to generate a sequence of objects determined by a truly random seed which is not truly random. It has been widely used in many applications, such as cryptography and simulations. In this article, we examine current popular machine learning algorithms with various on-line algorithms for pseudo-random generated data in order to find out which machine learning approach is more suitable for this kind of data for prediction based on on-line algorithms. To further improve the prediction performance, we propose a novel sample weighted algorithm that takes generalization errors in each iteration into account. We perform intensive evaluation on real Baccarat data generated by Casino machines and random number generated by a popular Java program, which are two typical examples of pseudo-random generated data. The experimental results show that support vector machine and k-nearest neighbors have better performance than others with and without sample weighted algorithm in the evaluation data set.     

A fast algorithm for determining the best combination of local alignments to a query sequence

Background  

Existing sequence alignment algorithms assume that similarities between DNA or amino acid sequences are linearly ordered. That is, stretches of similar nucleotides or amino acids are in the same order in both sequences. Recombination perturbs this order. An algorithm that can reconstruct sequence similarity despite rearrangement would be helpful for reconstructing the evolutionary history of recombined sequences.     

Dynamic programming algorithms for restriction map comparison

For most sequence comparison problems there is a correspondingmap comparison algorithm. While map data may appear to be incompatiblewith dynamic programming, we show in this paper that the rigorand efficiency of dynamic programming algorithms carry overto the map comparison algorithms. We present algorithms forrestriction map comparison that deal with two types of map errors:(i) closely spaced sites for different enzymes can be orderedincorrectly, and (ii) closely spaced sites for the same enzymecan be mapped as a single site. The new algorithms are a naturalextension of a previous map comparison model. Dynamic programmingalgorithms for computing optimal global and local alignmentsunder the new model are described. The new algorithms take aboutthe same order of time as previous map comparison algorithms.Programs implementing some of the new algorithms are used tofind similar regions within the Escherichia coli restrictionmap of Kohara et al.     

Alterations in Protein Synthesis in vivo in Chilling Sensitive Mung Bean Hypocotyls Caused by Chilling Stress

The effects of chilling on protein synthesis in vivo in etiolatedhypocotyls of Vigna radiata L. were investigated. After exposureof the tissues to 0?C for various periods of time, proteinswere labeled with [³⁵S]-methionine at 26?C. The total amountof ³⁵S incorporated into soluble and membrane proteins was reversiblyreduced by chilling for 24 h, during which time the tissuessuffered no injury. Further prolonged chilling produced an irreversibledecline both in the incorporation of radioactivity and in cellviability as assessed by the extent of leakage of electrolyte.The ³⁵S-labeled proteins in the soluble and the total membranefractions were analyzed quantitatively. Chilling of etiolatedhypocotyls for one or two days induced the syntheses of twosoluble proteins (82 and 74 kDa) and one membrane protein (80kDa). Moreover, three heat-shock proteins (HSPs) that were inducedby heat stress (41 ?C, 4h) had the same electrophoretic mobilitiesas those of the proteins induced directly or indirectly by thechilling treatment. ¹Contribution No. 3170 from the Institute of Low TemperatureScience. (Received April 22, 1988; Accepted September 30, 1988)     

A framework for phylogenetic sequence alignment

A phylogenetic alignment differs from other forms of multiple sequence alignment because it must align homologous features. Therefore, the goal of the alignment procedure should be to identify the events associated with the homologies, so that the aligned sequences accurately reflect those events. That is, an alignment is a set of hypotheses about historical events rather than about residues, and any alignment algorithm must be designed to identify and align such events. Some events (e.g., substitution) involve single residues, and our current algorithms can successfully align those events when sequence similarity is great enough. However, the other common events (such as duplication, translocation, deletion, insertion and inversion) can create complex sequence patterns that defeat such algorithms. There is therefore currently no computerized algorithm that can successfully align molecular sequences for phylogenetic analysis, except under restricted circumstances. Manual re-alignment of a preliminary alignment is thus the only feasible contemporary methodology, although it should be possible to automate such a procedure.     

Understanding the Underlying Mechanism of HA-Subtyping in the Level of Physic-Chemical Characteristics of Protein

The evolution of the influenza A virus to increase its host range is a major concern worldwide. Molecular mechanisms of increasing host range are largely unknown. Influenza surface proteins play determining roles in reorganization of host-sialic acid receptors and host range. In an attempt to uncover the physic-chemical attributes which govern HA subtyping, we performed a large scale functional analysis of over 7000 sequences of 16 different HA subtypes. Large number (896) of physic-chemical protein characteristics were calculated for each HA sequence. Then, 10 different attribute weighting algorithms were used to find the key characteristics distinguishing HA subtypes. Furthermore, to discover machine leaning models which can predict HA subtypes, various Decision Tree, Support Vector Machine, Naïve Bayes, and Neural Network models were trained on calculated protein characteristics dataset as well as 10 trimmed datasets generated by attribute weighting algorithms. The prediction accuracies of the machine learning methods were evaluated by 10-fold cross validation. The results highlighted the frequency of Gln (selected by 80% of attribute weighting algorithms), percentage/frequency of Tyr, percentage of Cys, and frequencies of Try and Glu (selected by 70% of attribute weighting algorithms) as the key features that are associated with HA subtyping. Random Forest tree induction algorithm and RBF kernel function of SVM (scaled by grid search) showed high accuracy of 98% in clustering and predicting HA subtypes based on protein attributes. Decision tree models were successful in monitoring the short mutation/reassortment paths by which influenza virus can gain the key protein structure of another HA subtype and increase its host range in a short period of time with less energy consumption. Extracting and mining a large number of amino acid attributes of HA subtypes of influenza A virus through supervised algorithms represent a new avenue for understanding and predicting possible future structure of influenza pandemics.     

CAST: an iterative algorithm for the complexity analysis of sequence tracts. Complexity analysis of sequence tracts

MOTIVATION: Sensitive detection and masking of low-complexity regions in protein sequences. Filtered sequences can be used in sequence comparison without the risk of matching compositionally biased regions. The main advantage of the method over similar approaches is the selective masking of single residue types without affecting other, possibly important, regions. RESULTS: A novel algorithm for low-complexity region detection and selective masking. The algorithm is based on multiple-pass Smith-Waterman comparison of the query sequence against twenty homopolymers with infinite gap penalties. The output of the algorithm is both the masked query sequence for further analysis, e.g. database searches, as well as the regions of low complexity. The detection of low-complexity regions is highly specific for single residue types. It is shown that this approach is sufficient for masking database query sequences without generating false positives. The algorithm is benchmarked against widely available algorithms using the 210 genes of Plasmodium falciparum chromosome 2, a dataset known to contain a large number of low-complexity regions. AVAILABILITY: CAST (version 1.0) executable binaries are available to academic users free of charge under license. Web site entry point, server and additional material: http://www.ebi.ac.uk/research/cgg/services/cast/     

Two distinct inactivation processes related to phosphorylation in cardiac L-type Ca(2+) channel currents

Weinvestigated the inactivation process of macroscopic cardiac L-typeCa²⁺ channel currents using the whole cell patch-clamptechnique with Na⁺ as the current carrier. The inactivationprocess of the inward currents carried by Na⁺ through thechannel consisted of two components >0 mV. The time constant of thefaster inactivating component (30.6 ± 2.2 ms at 0 mV) decreasedwith depolarization, but the time constant of the slower inactivatingcomponent (489 ± 21 ms at 0 mV) was not significantly influencedby the membrane potential. The inactivation process in the presence ofisoproterenol (100 nM) consisted of a single component (538 ± 60 ms at 0 mV). A protein kinase inhibitor, H-89, decreased the currentsand attenuated the effects of isoproterenol. In the presence of cAMP(500 µM), the inactivation process consisted of a single slowcomponent. We propose that the faster inactivating component representsa kinetic of the dephosphorylated or partially phosphorylated channel,and phosphorylation converts the kinetics into one with a differentvoltage dependency.

     

Automatic registration of microarray images. I. Rectangular grid

MOTIVATION: The analysis of high-throughput experiment data provided by microarrays becomes increasingly more and more important part of modern biological science. Microarrays allow to conduct genotyping or gene expression experiments on hundreds of thousands of test genes in parallel. Because of the large and constantly growing amount of experimental data the necessity of efficiency, robustness and complete automation of microarray image analysis algorithms is gaining significant attention in the field of microarray processing. RESULTS: The author presents here an efficient and completely automatic image registration algorithm (that is an algorithm for spots and blocks indexing) that allows to process a wide variety of microarray slides with different parameters of grid and block spacing as well as spot sizes. The algorithm scales linearly with the grid size, the time complexity is O(M), where M is number of rows x number of columns. It can successfully cope with local and global distortions of the grid, such as focal distortions and non-orthogonal transformations. The algorithm has been tested both on CCD and scanned images and showed very good performance-the processing time of a single slide with 44 blocks of 200 x 200 grid points (or 1 760 000 grid points total) was about 10 s. AVAILABILITY: The test implementation of the algorithm will be available upon request for academics. Supplementary information: http://fleece.ucsd.edu/~vit/Registration_Supplement.pdf