Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

3,3',5,5'-Tetrabromophenolsulfonphthalein (bromphenol blue), C19H10Br4O5S

M r=670.02, monoclinic, C2/c, a= 31.003(4), b=11.037(2), c=21.183(3)A, fl= 143.7 (1) °, V= 4291.2/k 3, D,n = 2.06, D x = 2.07Mgm -3, Z=8, MoKa, 2=0.7107/k, /~=7.45 mm -1, F(000) = 2560, T= 293 K, R = 0.061 for 1697 observed reflections. The bromphenol blue molecule consists essentially of three planar groupings: the sulfonphthalein ring system and two dibromophenol rings attached to the tetrahedral C atom of the five-membered ring of the sulfonphthalein system. The dibromophenol rings are inclined with resPect to each other at 73 ° whereas they make angles of 85 and 68 ° with respect to the sulfonphthalein system. The molecules aggregate into helical columns with the non-polar regions of the molecules in the interior and the polar regions on the surface. The columns are held together by a network of hydrogen bonds.

4-Biphenylyl phenyl thioketone (I), C19H14S, and 1-naphthyl phenyl thioketone (II), C17H12S

(I): Mr=274"39, orthorhombic, Pbca, a = 7.443 (1), b= 32.691 (3), c= 11.828 (2)A, V= 2877.98A 3, Z=8, Din= 1.216 (flotation in KI), D x = 1.266 g cm -3, /~(Cu Ka, 2 = 1.5418 A) = 17.55 cm -1, F(000) = li52.0, T= 293 K, R = 6.8%, 1378 significant reflections. (II): M r = 248.35, orthorhombic, P212~21, a = 5.873 (3), b = 13.677 (3), c = 15-668 (5) A, V = 1260.14 A 3, Z = 4, D,n = 1.297 (flotation in KI), Dx= 1.308 g cm -a, /t(CuKa, 2=1.5418 A) = 19.55 cm -~, F(000) = 520.0, T= 293 K, R = 6.9%, 751 significant reflections. Crystals of (I) and (II) undergo photo-oxidation in the crystallinestate. In (I) the dihedral angle between the phenyl rings of the biphenyl moiety is 46 (1) °. The C=S bond length is 1.611(5) A in (I) and 1.630 (9)/~ in (II). The correlation between molecular packing and reactivity is discussed.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

A new type of high-order elements based on the mesh-free interpolations

We propose a new type of high-order elements that incorporates the mesh-free Galerkin formulations into the framework of finite element method. Traditional polynomial interpolation is replaced by mesh-free interpolations in the present high-order elements, and the strain smoothing technique is used for integration of the governing equations based on smoothing cells. The properties of high-order elements, which are influenced by the basis function of mesh-free interpolations and boundary nodes, are discussed through numerical examples. It can be found that the basis function has significant influence on the computational accuracy and upper-lower bounds of energy norm, when the strain smoothing technique retains the softening phenomenon. This new type of high-order elements shows good performance when quadratic basis functions are used in the mesh-free interpolations and present elements prove advantageous in adaptive mesh and nodes refinement schemes. Furthermore, it shows less sensitive to the quality of element because it uses the mesh-free interpolations and obeys the Weakened Weak (W2) formulation as introduced in [3, 5].

Molecular structure of nicotinamide adenine dinucleotide

NICOTINAMIDE adenine dinucleotide (NAD) has a fundamental role in metabolic processes as an electron transport molecule. Although its chemical structure was elucidated1 in 1934, its detailed conformation remains still to be established in spite of numerous physicochemical applications2. NAD analogues with a variety of substitutions on the bases are known to retain considerable activity of the natural coenzyme as long as the pyrophosphate diester group has been retained3,4. The geometry of this backbone moiety is therefore indispensable to our understanding of the conformation and function of the coenzyme. We have so far no experimental evidence on this in NAD or any other nucleotide coenzyme molecule. X-ray studies have been possible only on those analogues5,6 where the nicotinamide and adenine rings are linked by a trimethylene bridge. The results are conflicting and it is difficult to use them to provide a structural basis for the NAD molecule itself, particularly as the phosphate backbone is absent from these analogues.

Transient response of coupled non-linear non-conservative systems

This paper deals with an approximate method of analysis of non-linear, non-conservative systems of two degrees of freedom. The approximate equations for amplitude and phase are obtained by a generalized averaging technique based on the ultraspherical polynomial approximation. The method is illustrated by an example of a spring-mass-damper system.

Eru Ilúvatar : Jumala J.R.R. Tolkienin legendariumissa

The purpose of my research is to inquire into the essence and activity of God in the legendarium of the English philologist and writer J.R.R. Tolkien (1892-1973). The legendarium, composed of Tolkien’s writings related to Middle-earth, was begun when he created two Elvish languages, Quenya based on Finnish, Sindarin based on Welsh. Tolkien developed his mythology inspired by Germanic myths and The Kalevala. It is a fictional ancient history set in our world. The legendarium is monotheistic: God is called Eru ‘The One’ and Ilúvatar ‘Father of All’. Eru is the same as the Christian God, for Tolkien wanted to keep his tales consistent with his faith. He said his works were Christian by nature, with the religious element absorbed into the story and the symbolism. In The Silmarillion, set in the primeval ages of Middle-earth, the theological aspects are more conspicuous, while in The Lord of the Rings, which brings the stories to an end, they are mostly limited to symbolic references. The legendarium is unified by its realistic outlook on creaturely abilities and hope expressing itself as humbly defiant resistance. ”The possibility of complexity or of distinctions in the nature of Eru” is a part of the legendarium. Eru Ilúvatar is Trinitarian, as per Tolkien’s faith. Without contextual qualifiers, Eru seems to refer to God the Father, like God in the Bible. Being the creator who dwells outside the world is attributed to Him. The Holy Spirit is the only Person of the Trinity bestown with names: the Flame Imperishable and the Secret Fire. When Eru creates the material world with His word, He sends the Flame Imperishable to burn at the heart of the world. The Secret Fire signifies the Creative Power that belongs to God alone, and is a part of Him. The Son, the Word, is not directly mentioned, but according to one writing Eru must step inside the world in order to save it from corruption, yet remain outside it at the same time. The inner structure of the legendarium refers to the need for a future salvation. The creative word of Eru, “Eä! Let these things Be!”, probably has a connection with the Logos in Christianity. Thus we can find three “distinctions” in Eru: a Creator who dwells outside the world, a Sustainer who dwells inside it and a Redeemer who shall step inside it. Some studies of Tolkien have claimed that Eru is distant and remote. This seems to hold water only partially. Ilúvatar, the Father of All, has a special relation with the Eruhíni, His Children, the immortal Elves and the mortal Men. He communicates with them directly only through the Valar, who resemble archangels. Nevertheless, only the Children of Eru can fight against evil, because their tragic fortunes turn evil into good. Even though religious activities are scarce among them, the fundamental faith and ultimate hope of the “Free Peoples” is directed towards Eru. He is present in the drama of history as the “Author of the Story”, who at times also interferes with its course through catastrophes and eucatastrophes, ‘good catastrophes’. Eru brings about a catastrophe when evil would otherwise bring good to an end, and He brings about a eucatasrophe when creaturely strength is not sufficent for victory. Victory over corruption is especially connected with mortal Men, of whom the most (or least) insignificant people are the Hobbits. However, because of the “primeval disaster” (that is, fall) of Mankind, ultimate salvation can only remain open, a hope for the far future.

Crystal structure and conformation of the cyclic dipeptide cyclo-(L-histidyl-L-aspartyl) trihydrate

The crystal structure of cyclo-(L-histidyl-L-aspartyl) trihydrate has been determined by x-ray diffraction techniques, and refined to a final R index of 0.056 for 1601 reflections. The molecule is in a folded conformation, with the imidazole ring facing the diketopiperazine ring. However, since the diketopiperazine ring is essentially planar, the interaction between the two rings is not as intimate as in those cyclic dipeptides in which the diketopiperazine ring is in a boat conformation with the side chain occupying an axial, or flagpole, site. Planarity of the diketopiperazine ring may be dictated by steric interactions between the imidazole ring and the aspartyl side chain. The molecule is a zwitterion, a proton having been transferred from the carboxyl group of the aspartyl side chain to the imidazole ring.

Robust and High-resolution Voiced/Unvoiced Classification in Noisy Speech Using A Signal Smoothness Criterion

We propose a novel technique for robust voiced/unvoiced segment detection in noisy speech, based on local polynomial regression. The local polynomial model is well-suited for voiced segments in speech. The unvoiced segments are noise-like and do not exhibit any smooth structure. This property of smoothness is used for devising a new metric called the variance ratio metric, which, after thresholding, indicates the voiced/unvoiced boundaries with 75% accuracy for 0dB global signal-to-noise ratio (SNR). A novelty of our algorithm is that it processes the signal continuously, sample-by-sample rather than frame-by-frame. Simulation results on TIMIT speech database (downsampled to 8kHz) for various SNRs are presented to illustrate the performance of the new algorithm. Results indicate that the algorithm is robust even in high noise levels.

Improvement in the voltage grading (axial and radial) of the generator column of a Van de Graaf generator by the use of a resistor chain

It is well known that the use of a series of resistors, connected between the equipotential rings of a Van de Graaff generator, improves the axial voltage grading of the generator. The work reported in this paper shows how the resistor chain also improves the radial voltage gradient. The electrolytic field mapping technique was adopted in the present work.

The Crystal and Molecular Structure of l-(Diphenylmethyl)azetidin-3-ol

1-(Diphenylmethyl)azetidin-3-ol is triclinic, space group P1, with a=8.479(2), b=17.294(4),c = 10.606 (3) A, a = 118.59 (2),/~ = 100.30 (2), y = 89.63 (2) °, Z = 4. The structure was solved by multisolution methods and refined to an R of 0.044 for 2755 reflexions. The four-membered rings in the two independent molecules are puckered with dihedral angles of 156 and 153 ° . The two molecules differ in conformation with respect to rotation of the phenyl rings about the C-C bonds. The structure is stabilized by a network of O-H. • • N intermolecular hydrogen bonds.

Popular Mixed Matchings

We study the problem of matching applicants to jobs under one-sided preferences: that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be rnore popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M,T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based oil the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distributions over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P,Q) >= phi(Q,P) for all mixed matchings Q. We show that popular mixed matchings always exist. and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem.

Efficient probabilistic contingency analysis through a stability measure considering wind perturbation

The integration of stochastic wind power has accentuated a challenge for power system stability assessment. Since the power system is a time-variant system under wind generation fluctuations, pure time-domain simulations are difficult to provide real-time stability assessment. As a result, the worst-case scenario is simulated to give a very conservative assessment of system transient stability. In this study, a probabilistic contingency analysis through a stability measure method is proposed to provide a less conservative contingency analysis which covers 5-min wind fluctuations and a successive fault. This probabilistic approach would estimate the transfer limit of a critical line for a given fault with stochastic wind generation and active control devices in a multi-machine system. This approach achieves a lower computation cost and improved accuracy using a new stability measure and polynomial interpolation, and is feasible for online contingency analysis.

Tris(methyl 3-oxobutanoato-kappa O-2,O `)aluminium(III)

In the title compound, [Al(C5H7O3)(3)],three acac-type ligands(methyl 3-oxobutanoate anions) chelate to the aluminium(III)cation in a slightly distorted AlO6 octahedral coordination geometry.Electron delocalization occurs within the chelating rings.