An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

Solvatochromic Shift of the pi -> pi* Transition in All-Trans, Cis-13, Cis-11, Cis-9, and Cis-7 Retinal Isomers Induced by Water and Methanol

The solvatochromic shift of the lowest singlet it pi -> pi* electronic transition in the all-trans, cis-13, cis-11, cis-9, and cis-7 retinal isomers were computed under the influence of water, methanol, and benzene solvents. Excitation energies were calculated in gas phase and in solution. The calculations in solution were performed considering the sequential Monte Carlo (MC) /Quantum Mechanical approach. The MC simulations were performed considering the full retinal isomer molecules and 900 water molecules, 900 methanol, or 400 benzene ones. The OPLS/AA parametrization was chosen for retinal, methanol, and benzene molecules and the SPC model was used for water one. From the MC calculations 100 independent configurations were selected, with 100 solvent molecules in thermodynamical equilibrium at T = 298.15 K. Average point-charges were obtained from those independent configurations for water, methanol, and benzene solvent. TDDFT and CASSCF//CASPT2 methodologies were used to compute the vertical excitation energy of the retinal isomers in different environment. (C) 2010 Wiley Periodicals, Inc. Int J Quantum Chem 110: 2076-2087, 2010