Barnacles are mostly sessile, hermaphroditic, internal-fertilizing and usually non-selfing crustaceans. They have the longest penis length, relative to body length, among all organisms. Because of their immobility, barnacles have to extend penes to reach mates and transfer the sperm. The longer the penis the more mates they can reach. However, maintaining long penes may be costly. How do barnacles allocate the reproductive investment and adjust the length of penes? Previous researches indicated that wave actions influenced the penis length of barnacles. Here we explore if biological factors are also involved in determining the penis length. Our hypotheses are that the penis length of Balanus amphitrite may be determined by (1) the presence of neighbors, (2) neighbor numbers, and (3) neighbor distance. Experimental results indicate that the neighbor distance could influence the penis length of B. amphitrite, and the penis length increase with increasing distance of neighbors. The neighbor numbers were not found to influence the penis length. In the treatment of lone individuals, the penis lengths first increased and then decreased, and they are significantly shorter than those in the treatment with neighbors. When neighbors exist, B. amphitrite detects the density by distance of neighbors. The greater the distance to neighbors, the lower the densities of neighbors. Because of the mates are enough to mate, the penes length decrease with increasing density to save cost. When neighbors do not exist, B. amphitrite may save cost by decreasing or not investing pens length . Our result shows that the plasticity of the penis length of B. amphitrite is an adaptation by natural selection.

Motivation: The quality of progressive sequence alignments strongly depends on the accuracy of the individual pairwise alignment steps since gaps that are introduced at one step cannot be removed at later aggregation steps. Adjacent insertions and deletions necessarily appear in arbitrary order in pairwise alignments and hence form an unavoidable source of errors. Idea: Here we present a modified variant of progressive sequence alignments that addresses both issues. Instead of pairwise alignments we use exact dynamic programming to align sequence or profile triples. This avoids a large fractions of the ambiguities arising in pairwise alignments. In the subsequent aggregation steps we follow the logic of the Neighbor-Net algorithm, which constructs a phylogenetic network by step-wisely replacing triples by pairs instead of combining pairs to singletons. To this end the three-way alignments are subdivided into two partial alignments, at which stage all-gap columns are naturally removed. This alleviates the “once a gap, always a gap” problem of progressive alignment procedures. Results: The three-way Neighbor-Net based alignment program aln3nn is shown to compare favorably on both protein sequences and nucleic acids sequences to other progressive alignment tools. In the latter case one easily can include scoring terms that consider secondary structure features. Overall, the quality of resulting alignments in general exceeds that of clustalw or other multiple alignments tools even though our software does not included heuristics for context dependent (mis)match scores.

"If it sounds good, it is good." - Duke Ellington "Like music, a work acquires its value only through the love it manifests." - Eileen Gray "...but in the mud and scum of things There alway, alway something sings." - R.W. Emerson / Master of Architecture

For a subset of vertices S in a graph G, if v ∈ S and w ∈ V - S, then the vertex w is an external private neighbor of v (with respect to S) if the only neighbor of w in S is v. A dominating set S is a private dominating set if each v ∈ S has an external private neighbor. Bollóbas and Cockayne (Graph theoretic parameters concerning domination, independence and irredundance. J. Graph Theory 3 (1979) 241-250) showed that every graph without isolated vertices has a minimum dominating set which is also a private dominating set. We define a graph G to be a private domination graph if every minimum dominating set of G is a private dominating set. We give a constructive characterization of private domination trees.

Most classification rules can be expressed in terms of a distance (or dissimilarity) from the point to be classified to each of the candidate classes. For example, linear discriminant analysis classifies points into the class for which the (sample) Mahalanobis distance is smallest. However, dependence among these point-to-group distance measures is generally ignored. The primary goal of this project is to investigate the properties of a general non-parametric classification rule which takes this dependence structure into account. A review of classification procedures and applications is presented. The distance profile nearest-neighbor classification rule is defined. Properties of the rule are then explored via application to both real and simulated data and comparisons to other classification rules are discussed.

Given a graph that defines a triangulation of a simply connected surface, it is possible to associate a radius with each vertex so that the vertices represent centers of circles, and the edges denote patterns of tangency. Such a configuration of circles is called a circle packing. We shall give evidence for the existence and uniqueness of circle packings generated by such graphs, as well as an explanation of the algorithms used to find and output a circle packing on the complex plane and hyperbolic disc. / Master of Science

No description available.

Nearest Neighbor (NN in short) queries are important in emerging applications, such as wireless networks, location-based services, and data stream applications, where the data obtained are often imprecise. The imprecision or imperfection of the data sources is modeled by uncertain data in recent research works. Handling uncertainty is important because this issue affects the quality of query answers. Although queries on uncertain data are useful, evaluating the queries on them can be costly, in terms of I/O or computational efficiency. In this thesis, we study how to efficiently evaluate NN queries on uncertain data. Given a query point q and a set of uncertain objects O, the possible nearest neighbor query returns a set of candidates which have non-zero probabilities to be the query answer. It is also interesting to ask \which region has the same set of possible nearest neighbors", and \which region has one specific object as its possible nearest neighbor". To reveal the relationship between the query space and nearest neighbor answers, we propose the UV-diagram, where the query space is split into disjoint partitions, such that each partition is associated with a set of objects. If a query point is located inside the partition, its possible nearest neighbors could be directly retrieved. However, the number of such partitions is exponential and the construction effort can be expensive. To tackle this problem, we propose an alternative concept, called UV-cell, and efficient algorithms for constructing it. The UV-cell has an irregular shape, which incurs difficulties in storage, maintenance, and query evaluation. We design an index structure, called UV-index, which is an approximated version of the UV-diagram. Extensive experiments show that the UV-index could efficiently answer different variants of NN queries, such as Probabilistic Nearest Neighbor Queries, Continuous Probabilistic Nearest Neighbor Queries. Another problem studied in this thesis is the trajectory nearest neighbor query. Here the query point is restricted to a pre-known trajectory. In applications (e.g. monitoring potential threats along a flight/vessel's trajectory), it is useful to derive nearest neighbors for all points on the query trajectory. Simple solutions, such as sampling or approximating the locations of uncertain objects as points, fails to achieve a good query quality. To handle this problem, we design efficient algorithms and optimization methods for this query. Experiments show that our solution can efficiently and accurately answer this query. Our solution is also scalable to large datasets and long trajectories. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

A central focus of computational biology is to organize and make use of vast stores of molecular sequence data. Two of the most studied and fundamental problems in the field are sequence alignment and phylogeny inference. The problem of multiple sequence alignment is to take a set of DNA, RNA, or protein sequences and identify related segments of these sequences. Perhaps the most common use of alignments of multiple sequences is as input for methods designed to infer a phylogeny, or tree describing the evolutionary history of the sequences. The two problems are circularly related: standard phylogeny inference methods take a multiple sequence alignment as input, while computation of a rudimentary phylogeny is a step in the standard multiple sequence alignment method.Efficient computation of high-quality alignments, and of high-quality phylogenies based on those alignments, are both open problems in the field of computational biology. The first part of the dissertation gives details of my efforts to identify a best-of-breed method for each stage of the standard form-and-polish heuristic for aligning multiple sequences; the result of these efforts is a tool, called Opal, that achieves state-of-the-art 84.7% accuracy on the BAliBASE alignment benchmark. The second part of the dissertation describes a new algorithm that dramatically increases the speed and scalability of a common method for phylogeny inference called neighbor-joining; this algorithm is implemented in a new tool, called NINJA, which is more than an order of magnitude faster than a very fast implementation of the canonical algorithm, for example building a tree on 218,000 sequences in under 6 days using a single processor computer.

Due to the combination of constrained power, low duty cycle, and high mobility, neighbor discovery is one of the most challenging problems in wireless sensor networks. Existing discovery designs can be divided into two types: pairwise-based and group-based. The former schemes suffer from high discovery delay, while the latter ones accelerate the discovery process but increase transmission package size or incur too much energy overhead, far from practical. Guided by the Talk More Listen Less (TMLL) principle (published in 2016), in which beacons are not necessarily placed in the wakeup slots, we propose two different versions of a group-based protocol we called Talk Half Listen Half (THLH). For the first time, a group-based protocol uses the Channel Occupancy Rate (COR), one of the fundamental novel components of the TMLL model, for performance improvements, in the same way, Duty Cycle (DC) was used in previous group-based protocols. Both versions of the protocol use low transmission overhead in comparison with previous group-based discoveries. After analyzing pros and cons of each approach, we arrived at the conclusion that both behave the best for networks where the average number of new neighbors per slot (β) is low, a metric that sets the bases for performance comparisons of any current/future work with variable COR usage. We also derived a formula that links this new metric with the worst case avg. COR usage of our proposed protocols. Finally, simulation results show that our protocol can improve the average discovery latency and worst case latency close to 50% given low β values.