An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.

G M Landau; U Vishkin; R Nussinov

doi:10.1093/nar/14.1.31

Home/Archive/PubMed

PubMed · 3753770

An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.

G M Landau·U Vishkin·R Nussinov

View original source ↗Export metadata ↓

Abstract

There are a few algorithms designed to solve the problem of the optimal alignment of one sequence, the pattern, of length m, with another, longer sequence the text, of length n. These algorithms allow mismatches, deletions and insertions. Algorithms to date run in O(mn) time. Let us define an integer, k, which is the maximal number of differences allowed. We present a simple algorithm showing that sequences can be optimally aligned in O(k2n) time. For long sequences the gain factor over the currently used algorithms is very large.

Explore related subjects

Amino Acid Sequence Base Sequence Computers Mathematics Software Journal Article Research Support, U.S. Gov't, Non-P.H.S.

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

G M Landau, U Vishkin, R Nussinov. 1986-01-10. An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.. https://doi.org/10.1093/nar%2F14.1.31

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2024

A new point mutation in the HC-Pro of potato virus Y is involved in tobacco vein necrosis.

Tobacco vein necrosis (TVN) is a complex phenomenon regulated by different genetic determinants mapped in the HC-Pro protein (amino acids N330, K391 and E410) and in two regions of potato virus Y (PVY) genome, corresponding to the cytoplasmic inclusion (CI) protein and the nuclear inclusion protein a-protease (NIa-Pro), respectively. A new determinant of TVN was discovered in the MK isolate of PVY which, although carried the HC-Pro determinants associated to TVN, did not induce TVN. The HC-Pro open reading frame (ORF) of the necrotic infectious clone PVY N605 was replaced with that of the non-necrotic MK isolate, which differed only by one amino acid at position 392 (T392 instead of I392). The cDNA clone N605_MKHCPro inoculated in tobacco induced only weak mosaics at the systemic level, demostrating that the amino acid at position 392 is a new determinant for TVN. No significant difference in accumulation in tobacco was observed between N605 and N605_MKHCPro. Since phylogenetic analyses showed that the loss of necrosis in tobacco has occurred several times independently during PVY evolution, these repeated evolutions strongly suggest that tobacco necrosis is a costly trait in PVY.

Amino Acid Sequence↗

PubMed2019

Residues on Adeno-associated Virus Capsid Lumen Dictate Interactions and Compatibility with the Assembly-Activating Protein.

The adeno-associated virus (AAV) serves as a broadly used vector system for in vivo gene delivery. The process of AAV capsid assembly remains poorly understood. The viral cofactor assembly-activating protein (AAP) is required for maximum AAV production and has multiple roles in capsid assembly, namely, trafficking of the structural proteins (VP) to the nuclear site of assembly, promoting the stability of VP against multiple degradation pathways, and facilitating stable interactions between VP monomers. The N-terminal 60 amino acids of AAP (AAPN) are essential for these functions. Presumably, AAP must physically interact with VP to execute its multiple functions, but the molecular nature of the AAP-VP interaction is not well understood. Here, we query how structurally related AAVs functionally engage AAP from AAV serotype 2 (AAP2) toward virion assembly. These studies led to the identification of key residues on the lumenal capsid surface that are important for AAP-VP and for VP-VP interactions. Replacing a cluster of glutamic acid residues with a glutamine-rich motif on the conserved VP beta-barrel structure of variants incompatible with AAP2 creates a gain-of-function mutant compatible with AAP2. Conversely, mutating positively charged residues within the hydrophobic region of AAP2 and conserved core domains within AAPN creates a gain-of-function AAP2 mutant that rescues assembly of the incompatible variant. Our results suggest a model for capsid assembly where surface charge/neutrality dictates an interaction between AAPN and the lumenal VP surface to nucleate capsid assembly.IMPORTANCE Efforts to engineer the AAV capsid to gain desirable properties for gene therapy (e.g., tropism, reduced immunogenicity, and higher potency) require that capsid modifications do not affect particle assembly. The relationship between VP and the cofactor that facilitates its assembly, AAP, is central to both assembly preservation and vector production. Understanding the requirements for this compatibility can inform manufacturing strategies to maximize production and reduce costs. Additionally, library-based approaches that simultaneously examine a large number of capsid variants would benefit from a universally functional AAP, which could hedge against overlooking variants with potentially valuable phenotypes that were lost during vector library production due to incompatibility with the cognate AAP. Studying interactions between the structural and nonstructural components of AAV enhances our fundamental knowledge of capsid assembly mechanisms and the protein-protein interactions required for productive assembly of the icosahedral capsid.

Amino Acid Sequence↗

PubMed2016

Characterization of Class III Peroxidases from Switchgrass.

Class III peroxidases (CIIIPRX) catalyze the oxidation of monolignols, generate radicals, and ultimately lead to the formation of lignin. In general, CIIIPRX genes encode a large number of isozymes with ranges of in vitro substrate specificities. In order to elucidate the mode of substrate specificity of these enzymes, we characterized one of the CIIIPRXs (PviPRX9) from switchgrass (Panicum virgatum), a strategic plant for second-generation biofuels. The crystal structure, kinetic experiments, molecular docking, as well as expression patterns of PviPRX9 across multiple tissues and treatments, along with its levels of coexpression with the majority of genes in the monolignol biosynthesis pathway, revealed the function of PviPRX9 in lignification. Significantly, our study suggested that PviPRX9 has the ability to oxidize a broad range of phenylpropanoids with rather similar efficiencies, which reflects its role in the fortification of cell walls during normal growth and root development and in response to insect feeding. Based on the observed interactions of phenylpropanoids in the active site and analysis of kinetics, a catalytic mechanism involving two water molecules and residues histidine-42, arginine-38, and serine-71 was proposed. In addition, proline-138 and gluntamine-140 at the 137P-X-P-X140 motif, leucine-66, proline-67, and asparagine-176 may account for the broad substrate specificity of PviPRX9. Taken together, these observations shed new light on the function and catalysis of PviPRX9 and potentially benefit efforts to improve biomass conservation properties in bioenergy and forage crops.

Amino Acid Sequence↗