Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

Highly heritable resistance to root-lesion nematode (Pratylenchus thornei) in Australian chickpea germplasm observed using an optimised glasshouse method and multi-environment trial analysis

Pratylenchus thornei is a root-lesion nematode (RLN) of economic significance in the grain growing regions of Australia. Chickpea (Cicer arietinum) is a significant legume crop grown throughout these regions, but previous testing found most cultivars were susceptible to P. thornei. Therefore, improved resistance to P. thornei is an important objective of the Australian chickpea breeding program. A glasshouse method was developed to assess resistance of chickpea lines to P. thornei, which requires relatively low labour and resource input, and hence is suited to routine adoption within a breeding program. Using this method, good differentiation of chickpea cultivars for P. thornei resistance was measured after 12 weeks. Nematode multiplication was higher for all genotypes than the unplanted control, but of the 47 cultivars and breeding lines tested, 17 exhibited partial resistance, allowing less than two fold multiplication. The relative differences in resistance identified using this method were highly heritable (0.69) and were validated against P. thornei data from seven field trials using a multi-environment trial analysis. Genetic correlations for cultivar resistance between the glasshouse and six of the field trials were high (>0.73). These results demonstrate that resistance to P. thornei in chickpea is highly heritable and can be effectively selected in a limited set of environments. The improved resistance found in a number of the newer chickpea cultivars tested shows that some advances have been made in the P. thornei resistance of Australian chickpea cultivars, and that further targeted breeding and selection should provide incremental improvements.

Are diverse factors proxies for architectural influences? A case for architecture in the aetiology of schizophrenia

Introduction The last half-century of epidemiological enquiry into schizophrenia can be characterized by the search for neurological imbalances and lesions for genetic factors. The growing consensus is that these directions have failed, and there is now a growing interest in psychosocial and developmental models. Another area of recent interest is in epigenetics – the multiplication of genetic influences by environmental factors. Methods This integrative review comparatively maps current psychosocial, developmental and epigenetic models for schizophrenia epidemiology to identify crossover and theoretical gaps. Results In the flood of data that is being produced around the schizophrenia epidemiology, one of the most consistent findings is that schizophrenia is an urban syndrome. Once demographic factors have been discounted, between one-quarter and one-third of all incidence is repeatedly traced back to urbanicity – potentially threatening more established models, such as the psychosocial, genetic and developmental hypotheses. Conclusions Close analysis demonstrates how current models for schizophrenia epidemiology appear to miss the mark. Furthermore, the built environment appears to be an inextricable factor in all current models and indeed may be a valid epidemiological factor on its own. The reason the built environment hasn’t already become a de rigueur area of epidemiological research is possibly trivial – it just doesn’t attract enough science, and lacks a hero to promote it alongside other hypotheses.

Reed-Muller Canonical Forms in Multivalued Logic

Canonical forms for m-valued functions referred to as m-Reed-Muller canonical (m-RMC) forms that are a generalization of RMC forms of two-valued functions are proposed. m-RMC forms are based on the operations ?m (addition mod m) and .m (multiplication mod m) and do not, as in the cases of the generalizations proposed in the literature, require an m-valued function for m not a power of a prime, to be expressed by a canonical form for M-valued functions, where M > m is a power of a prime. Methods of obtaining the m-RMC forms from the truth vector or the sum of products representation of an m-valued function are discussed. Using a generalization of the Boolean difference to m-valued logic, series expansions for m-valued functions are derived.

Below-ground processes in meadow soil under elevated ozone and carbon dioxide : - Greenhouse gas fluxes, N cycling and microbial communities

This thesis focuses on how elevated CO2 and/or O3 affect the below-ground processes in semi-natural vegetation, with an emphasis on greenhouse gases, N cycling and microbial communities. Meadow mesocosms mimicking lowland hay meadows in Jokioinen, SW Finland, were enclosed in open-top chambers and exposed to ambient and elevated levels of O3 (40-50 ppb) and/or CO2 (+100 ppm) for three consecutive growing season, while chamberless plots were used as chamber controls. Chemical and microbiological analyses as well as laboratory incubations of the mesocosm soils under different treatments were used to study the effects of O3 and/or CO2. Artificially constructed mesocosms were also compared with natural meadows with regards to GHG fluxes and soil characteristics. In addition to research conducted at the ecosystem level (i.e. the mesocosm study), soil microbial communities were also examined in a pot experiment with monocultures of individual species. By comparing mesocosms with similar natural plant assemblage, it was possible to demonstrate that artificial mesocosms simulated natural habitats, even though some differences were found in the CH4 oxidation rate, soil mineral N, and total C and N concentrations in the soil. After three growing seasons of fumigations, the fluxes of N2O, CH4, and CO2 were decreased in the NF+O3 treatment, and the soil NH4+-N and mineral N concentrations were lower in the NF+O3 treatment than in the NF control treatment. The mesocosm soil microbial communities were affected negatively by the NF+O3 treatment, as the total, bacterial, actinobacterial, and fungal PLFA biomasses as well as the fungal:bacterial biomass ratio decreased under elevated O3. In the pot survey, O3 decreased the total, bacterial, actinobacterial, and mycorrhizal PLFA biomasses in the bulk soil and affected the microbial community structure in the rhizosphere of L. pratensis, whereas the bulk soil and rhizosphere of the other monoculture, A. capillaris, remained unaffected by O3. Elevated CO2 caused only minor and insignificant changes in the GHG fluxes, N cycling, and the microbial community structure. In the present study, the below-ground processes were modified after three years of moderate O3 enhancement. A tentative conclusion is that a decrease in N availability may have feedback effects on plant growth and competition and affect the N cycling of the whole meadow ecosystem. Ecosystem level changes occur slowly, and multiplication of the responses might be expected in the long run.

Calculating the bound spectrum by path summation in action-angle variables

The density of states n(E) is calculated for a bound system whose classical motion is integrable, starting from an expression in terms of the trace of the time-dependent Green function. The novel feature is the use of action-angle variables. This has the advantages that the trace operation reduces to a trivial multiplication and the dependence of n(E) on all classical closed orbits with different topologies appears naturally. The method is contrasted with another, not applicable to integrable systems except in special cases, in which quantization arises from a single closed orbit which is assumed isolated and the trace taken by the method of stationary phase.

In vitro micropropagation of elite rosewood (Dalbergia latifolia Roxb

Induction of single and multiple shoots was obtained from nodal expiants of 60–80 year-old elite trees of rosewood on Murashige and Skoog's basal medium supplemented with 6-benzylaminopurine (1.0 mg 1-1) and delta -Naphthalene acetic acid (0.05 mg 1-1) or indole acetic acid (0.5 mg 1-1). Multiplication of shoots was obtained on MS (reduced major elements) or Woody Plant Medium supplemented with 6-benzylaminopurine (1.0 mg 1-1) and kinetin (0.5–1.0 mg 1-1). Excised shoots were rooted on half-strength MS with IBA (2.0 mg 1-1) to obtain complete plantlets. The regenerated plantlets have been acclimatized and successfully transferred to the soil.

Substance flow analysis in Finland : Four case studies on N and P flows

Nitrogen (N) and phosphorus (P) are essential elements for all living organisms. However, in excess, they contribute to several environmental problems such as aquatic and terrestrial eutrophication. Globally, human action has multiplied the volume of N and P cycling since the onset of industrialization. The multiplication is a result of intensified agriculture, increased energy consumption and population growth. Industrial ecology (IE) is a discipline, in which human interaction with the ecosystems is investigated using a systems analytical approach. The main idea behind IE is that industrial systems resemble ecosystems, and, like them, industrial systems can then be described using material, energy and information flows and stocks. Industrial systems are dependent on the resources provided by the biosphere, and these two cannot be separated from each other. When studying substance flows, the aims of the research from the viewpoint of IE can be, for instance, to elucidate the ways how the cycles of a certain substance could be more closed and how the flows of a certain substance could be decreased per unit of production (= dematerialization). In Finland, N and P are studied widely in different ecosystems and environmental emissions. A holistic picture comparing different societal systems is, however, lacking. In this thesis, flows of N and P were examined in Finland using substance flow analysis (SFA) in the following four subsystems: I) forest industry and use of wood fuels, II) food production and consumption, III) energy, and IV) municipal waste. A detailed analysis at the end of the 1990s was performed. Furthermore, historical development of the N and P flows was investigated in the energy system (III) and the municipal waste system (IV). The main research sources were official statistics, literature, monitoring data, and expert knowledge. The aim was to identify and quantify the main flows of N and P in Finland in the four subsystems studied. Furthermore, the aim was to elucidate whether the nutrient systems are cyclic or linear, and to identify how these systems could be more efficient in the use and cycling of N and P. A final aim was to discuss how this type of an analysis can be used to support decision-making on environmental problems and solutions. Of the four subsystems, the food production and consumption system and the energy system created the largest N flows in Finland. For the creation of P flows, the food production and consumption system (Paper II) was clearly the largest, followed by the forest industry and use of wood fuels and the energy system. The contribution of Finland to N and P flows on a global scale is low, but when compared on a per capita basis, we are one of the largest producers of these flows, with relatively high energy and meat consumption being the main reasons. Analysis revealed the openness of all four systems. The openness is due to the high degree of internationality of the Finnish markets, the large-scale use of synthetic fertilizers and energy resources and the low recycling rate of many waste fractions. Reduction in the use of fuels and synthetic fertilizers, reorganization of the structure of energy production, reduced human intake of nutrients and technological development are crucial in diminishing the N and P flows. To enhance nutrient recycling and replace inorganic fertilizers, recycling of such wastes as wood ash and sludge could be promoted. SFA is not usually sufficiently detailed to allow specific recommendations for decision-making to be made, but it does yield useful information about the relative magnitude of the flows and may reveal unexpected losses. Sustainable development is a widely accepted target for all human action. SFA is one method that can help to analyse how effective different efforts are in leading to a more sustainable society. SFA's strength is that it allows a holistic picture of different natural and societal systems to be drawn. Furthermore, when the environmental impact of a certain flow is known, the method can be used to prioritize environmental policy efforts.

The viral coat protein is regulated by HSP70 and HSP40 in Potato virus A infection

Plus-stranded (plus) RNA viruses multiply within a cellular environment as tightly integrated units and rely on the genetic information carried within their genomes for multiplication and, hence, persistence. The minimal genomes of plus RNA viruses are unable to encode the molecular machineries that are required for virus multiplication. This sets requisites for the virus, which must form compatible interactions with host components during multiplication to successfully utilize primary metabolites as building blocks or metabolic energy, and to divert the protein synthesis machinery for production of viral proteins. In fact, the emerging picture of a virus-infected cell displays tight integration with the virus, from simple host and virus protein interactions through to major changes in the physiological state of the host cell. This study set out to develop a method for the identification of host components, mainly host proteins, that interact with proteins of Potato virus A (PVA; Potyvirus) during infection. This goal was approached by developing affinity-tag based methods for the purification of viral proteins complexed with associated host proteins from infected plants. Using this method, host membrane-associated viral ribonucleoprotein (RNP) complexes were obtained, and several host and viral proteins could be identified as components of these complexes. One of the host proteins identified using this strategy was a member of the heat shock protein 70 (HSP70) family, and this protein was chosen for further analysis. To enable the analysis of viral gene expression, a second method was developed based on Agrobacterium-mediated virus genome delivery into plant cells, and detection of virally expressed Renilla luciferase (RLUC) as a quantitative measure of viral gene expression. Using this method, it was observed that down-regulation of HSP70 caused a PVA coat protein (CP)-mediated defect associated with replication. Further experimentation suggested that CP can inhibit viral gene expression and that a distinct translational activity coupled to replication, referred to as replication-associated translation (RAT), exists. Unlike translation of replication-deficient viral RNA, RAT was dependent on HSP70 and its co-chaperone CPIP. HSP70 and CPIP together regulated CP turnover by promoting its modification by ubiquitin. Based on these results, an HSP70 and CPIP-driven mechanism that functions to regulate CP during viral RNA replication and/or translation is proposed, possibly to prevent premature particle assembly caused by CP association with viral RNA.

Salmonella pathogenicity island 2 mediates protection of intracellular Salmonella from reactive nitrogen intermediates.

Salmonella typhimurium causes an invasive disease in mice that has similarities to human typhoid. A type III protein secretion system encoded by Salmonella pathogenicity island 2 (SPI2) is essential for virulence in mice, as well as survival and multiplication within macrophages. Reactive nitrogen intermediates (RNI) synthesized by inducible nitric oxide synthase (iNOS) are involved in the control of intracellular pathogens, including S. typhimurium. We studied the effect of Salmonella infection on iNOS activity in macrophages. Immunofluorescence microscopy demonstrated efficient colocalization of iNOS with bacteria deficient in SPI2 but not wild-type Salmonella, and suggests that the SPI2 system interferes with the localization of iNOS and Salmonella. Furthermore, localization of nitrotyrosine residues in the proximity was observed for SPI2 mutant strains but not wild-type Salmonella, indicating that peroxynitrite, a potent antimicrobial compound, is excluded from Salmonella-containing vacuoles by action of SPI2. Altered colocalization of iNOS with intracellular Salmonella required the function of the SPI2-encoded type III secretion system, but not of an individual "Salmonella translocated effector." Inhibition of iNOS increased intracellular proliferation of SPI2 mutant bacteria and, to a lesser extent, of wild-type Salmonella. The defect in systemic infection of a SPI2 mutant strain was partially restored in iNOS(-/-) mice. In addition to various strategies to detoxify RNI or repair damage due to RNI, avoidance of colocalization with RNI is important in adaptation of a pathogen to an intracellular life style.

Block Convolution Using Discrete Trigonometric Transforms and Discrete Fourier Transform

We derive expressions for convolution multiplication properties of discrete cosine transform II (DCT II) starting from equivalent discrete Fourier transform (DFT) representations. Using these expressions, a method for implementing linear filtering through block convolution in the DCT II domain is presented. For the case of nonsymmetric impulse response, additional discrete sine transform II (DST II) is required for implementing the filter in DCT II domain, where as for a symmetric impulse response, the additional transform is not required. Comparison with recently proposed circular convolution technique in DCT II domain shows that the proposed new method is computationally more efficient.

Consistent quaternion interpolation for objective finite element approximation of geometrically exact beam

We explore an isoparametric interpolation of total quaternion for geometrically consistent, strain-objective and path-independent finite element solutions of the geometrically exact beam. This interpolation is a variant of the broader class known as slerp. The equivalence between the proposed interpolation and that of relative rotation is shown without any recourse to local bijection between quaternions and rotations. We show that, for a two-noded beam element, the use of relative rotation is not mandatory for attaining consistency cum objectivity and an appropriate interpolation of total rotation variables is sufficient. The interpolation of total quaternion, which is computationally more efficient than the one based on local rotations, converts nodal rotation vectors to quaternions and interpolates them in a manner consistent with the character of the rotation manifold. This interpolation, unlike the additive interpolation of total rotation, corresponds to a geodesic on the rotation manifold. For beam elements with more than two nodes, however, a consistent extension of the proposed quaternion interpolation is difficult. Alternatively, a quaternion-based procedure involving interpolation of relative rotations is proposed for such higher order elements. We also briefly discuss a strategy for the removal of possible singularity in the interpolation of quaternions, proposed in [I. Romero, The interpolation of rotations and its application to finite element models of geometrically exact rods, Comput. Mech. 34 (2004) 121–133]. The strain-objectivity and path-independence of solutions are justified theoretically and then demonstrated through numerical experiments. This study, being focused only on the interpolation of rotations, uses a standard finite element discretization, as adopted by Simo and Vu-Quoc [J.C. Simo, L. Vu-Quoc, A three-dimensional finite rod model part II: computational aspects, Comput. Methods Appl. Mech. Engrg. 58 (1986) 79–116]. The rotation update is achieved via quaternion multiplication followed by the extraction of the rotation vector. Nodal rotations are stored in terms of rotation vectors and no secondary storages are required.

Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Straw Performance Studies and Quality Assurance for the ATLAS Transition Radiation Tracker

The Transition Radiation Tracker (TRT) of the ATLAS experiment at the LHC is part of the Inner Detector. It is designed as a robust and powerful gaseous detector that provides tracking through individual drift-tubes (straws) as well as particle identification via transition radiation (TR) detection. The straw tubes are operated with Xe-CO2-O2 70/27/3, a gas that combines the advantages of efficient TR absorption, a short electron drift time and minimum ageing effects. The modules of the barrel part of the TRT were built in the United States while the end-cap wheels are assembled at two Russian institutes. Acceptance tests of barrel modules and end-cap wheels are performed at CERN before assembly and integration with the Semiconductor Tracker (SCT) and the Pixel Detector. This thesis first describes simulations the TRT straw tube. The argon-based acceptance gas mixture as well as two xenon-based operating gases are examined for its properties. Drift velocities and Townsend coefficients are computed with the help of the program Magboltz and used to study electron drift and multiplication in the straw using the software Garfield. The inclusion of Penning transfers in the avalanche process leads to remarkable agreements with experimental data. A high level of cleanliness in the TRT s acceptance test gas system is indispensable. To monitor gas purity, a small straw tube detector has been constructed and extensively used to study the ageing behaviour of the straw tube in Ar-CO2. A variety of ageing tests are presented and discussed. Acceptance tests for the TRT survey dimensions, wire tension, gas-tightness, high-voltage stability and gas gain uniformity along each individual straw. The thesis gives details on acceptance criteria and measurement methods in the case of the end-cap wheels. Special focus is put on wire tension and straw straightness. The effect of geometrically deformed straws on gas gain and energy resolution is examined in an experimental setup and compared to simulation studies. An overview of the most important results from the end-cap wheels tested up to this point is presented.