12935102
Whole-Genome Analysis of Gene Conversion Events
Gene conversion events are often overlooked in analyses of genome evolution. In a conversion event, an interval of DNA sequence (not necessarily containing a gene) overwrites a highly similar sequence. The event creates relationships among genomic intervals that can confound attempts to identify orthologs and to transfer functional annotation between genomes. Here we examine 1,112,202 paralogous pairs of human genomic intervals, and detect conversion events in about 13.5% of them. Properties of the putative gene conversions are analyzed, such as the lengths of the paralogous pairs and the spacing between their sources and targets. Our approach is illustrated using conversion events in the beta-globin gene cluster.
12263549
Tree-guided Bayesian inference of population structures
MOTIVATION
Inferring population structures using genetic data sampled from a group of individuals is a challenging task. Many methods either consider a fixed population number or ignore the correlation between populations. As a result, they can lose sensitivity and specificity in detecting subtle stratifications. In addition, when a large number of genetic markers are used, many existing algorithms perform rather inefficiently.


RESULT
We propose a new Bayesian method to infer population structures using multiple unlinked single nucleotide polymorphisms (SNPs). Our approach explicitly considers the population correlation through a tree hierarchy, and treat the population number as a random variable. Using both simulated and real datasets of worldwide samples, we demonstrate that an incorporated tree can consistently improve the power in detecting subtle population stratifications. A tree-based model often involves a large number of unknown parameters, and the corresponding estimation procedure can be highly inefficient. We further implement a partition method to analytically integrate out all nuisance parameters in the tree. As a result, our method can analyze large SNP datasets with significantly improved convergence rate.


AVAILABILITY
http://www.stat.psu.edu/~yuzhang/tips.tar.
21795877
An Eulerian Path Approach to Global Multiple Alignment for DNA Sequences
With the rapid increase in the dataset of genome sequences, the multiple sequence alignment problem is increasingly important and frequently involves the alignment of a large number of sequences. Many heuristic algorithms have been proposed to improve the speed of computation and the quality of alignment. We introduce a novel approach that is fundamentally different from all currently available methods. Our motivation comes from the Eulerian method for fragment assembly in DNA sequencing that transforms all DNA fragments into a de Bruijn graph and then reduces sequence assembly to a Eulerian path problem. The paper focuses on global multiple alignment of DNA sequences, where entire sequences are aligned into one configuration. Our main result is an algorithm with almost linear computational speed with respect to the total size (number of letters) of sequences to be aligned. Five hundred simulated sequences (averaging 500 bases per sequence and as low as 70% pairwise identity) have been aligned within three minutes on a personal computer, and the quality of alignment is satisfactory. As a result, accurate and simultaneous alignment of thousands of long sequences within a reasonable amount of time becomes possible. Data from an Arabidopsis sequencing project is used to demonstrate the performance.
6114653
Alignment of Optical Maps
An adjustable device that provides a secure anchor in a crevice or other irregularity. The anchor may be used to assist rock climbers, rescue groups, military personnel, construction workers, etc. The device is comprised of a spring loaded sleeve mounted on a first end of a threaded shaft and limited in its movement on the shaft by a pin and slot arrangement. The sleeve provides a means for adjusting the length of the device. A first locking means releasably secures the sleeve in a retracted position, and a second locking means secures the sleeve at the desired extended position. A lever assembly is provided at the second end of the device in such a manner that a force applied to an attachment point of the assembly will be translated along the longitudinal axis of the device.
2554459
Refinement of optical map assemblies
MOTIVATION
Genomic mutations and variations provide insightful information about the functionality of sequence elements and their association with human diseases. Traditionally, variations are identified through analysis of short DNA sequences, usually shorter than 1000 bp per fragment. Optical maps provide both faster and more cost-efficient means for detecting such differences, because a single map can span over 1 million bp. Optical maps are assembled to cover the whole genome, and the accuracy of assembly is critical.


RESULTS
We present a computationally efficient model-based method for improving quality of such assemblies. Our method provides very high accuracy even with moderate coverage (<20 x). We utilize a hidden Markov model to represent the consensus map and use the expectation-Maximization algorithm to drive the refinement process. We also provide quality scores to assess the quality of the finished map.


AVAILABILITY
Code is available from www.cmb.usc.edu/people/valouev/
34552917
A new dynamic Bayesian network for integrating multiple data in estimating gene networks
We propose a novel method for estimating a gene regulatory network from both gene expression data and transcription factor binding location data. Based on dynamic Bayesian network (DBN) models, our method has two advantages. First, structural expectation maximization algorithm is embedded into a DBN framework, allowing it to learn the network with unknown structure and incomplete data, which cannot be tackled by expectation maximization algorithm. Second, since learning only from gene expression data is not enough to accurately estimate a gene network, we incorporate transcription factor binding location data through a structure prior. We demonstrate the effectiveness of the proposed method by the analysis of Saccharomyces Cerevisiae cell cycle data. The experimental results show that this new approach suits for dealing with missing values. Furthermore, combination of heterogeneous data from multiple sources ensures that our results are more accurate than those recovered from gene expression data alone.
18862565
Inferring Gene Regulatory Networks from Multiple Data Sources Via a Dynamic Bayesian Network with Structural EM
Using our dynamic Bayesian network with structural Expectation Maximization (SEM-DBN), we develop a new framework to model gene regulatory network from both gene expression data and transcriptional factor binding site data. Only based on mRNA expression data, it is not enough to accurately estimate a gene network. It is difficult for us to estimate a gene network accurately only with the mRNA expression data. In this paper, we use the transcription factor binding location data in order to introduce the prior knowledge to SEM-DBN model. Gene expression data are also exploited specifically for likelihood. Meanwhile, we incorporate the prior knowledge into every learning step by SEM rather than only learning from the very beginning, which can compensate the attenuation of the effect with location data. The effectiveness of our proposed method is demonstrated through the analysis of Saccharomyces cerevisiae cell cycle data. The combination of heterogeneous data from multiple sources ensures that our results are more accurate than those recovered from only gene expression data alone.
31009913
Synthesis of 3D faces using region-based morphing under intuitive control
This paper presents a new region-based method for automatically synthesizing varied, natural looking 3D human face models by morphing local facial features according to intuitive control parameters. We automatically compute a one-to-one vertex correspondence among the unregistered face scans in a large database by deforming a generic mesh to fit the specific person's face geometry in a global-to-local fashion. With the obtained correspondence, we transform the generated data sets of feature shapes into vector space representations. We parameterize the example models using the face anthropometric measurements that reflect the facial physical structure, and predefine the interpolation functions for the parameterized example models based on radial basis functions. At runtime, the interpolation functions are evaluated to efficiently generate the appropriate feature shape by taking the anthropometric parameters as input. We use a shape blending approach for generating a seamlessly deformed mesh around the feature region boundary. The correspondence among all example textures is established by parameterizing the 3D generic mesh over a 2D image domain. The new feature texture with desired attributes is synthesized by interpolating the example textures. Our 3D face synthesis method has several advantages: (1) it regulates the naturalness of synthesized faces, maintaining the quality existing in the real face examples; (2) the region-based morphing and comprehensive face shape and texture control parameters allow more diverse faces to be generated readily; and (3) the automatic runtime face synthesis is efficient in time complexity and performs fast. Copyright © 2006 John Wiley & Sons, Ltd.
5397904
Modeling and Throughput Analysis for Wireless Ad Hoc Networks
This paper presents a novel analytical model for wireless ad hoc networks. Based on the strong points in the literature, an accurate performance model for IEEE 802.11 MAC protocol is proposed. Moreover, by introducing the properties of spatial reuse, we extend the proposed model to support the throughput analysis of wireless ad hoc networks with directional antenna. An extensive set of simulations and numerical calculations validate our model by showing high accurate results.
8751830
Power-Modulated Challenge-Response Schemes for Verifying Location Claims
Location information should be verifiable in order to support new computing and information services. In this paper, we adapt the classical challenge-response method for authentication to the task of verifying an entity's location. Our scheme utilizes a collection of transmitters, and adapts their power allocations to verify a user's claimed location. This strategy, which we call power-modulated challenge response, is able to be used with existing wireless sensor networks, and we present three variations. First, we propose a direct method, where some transmitters are selected to send "challenges" that the claimant node should be able to witness based on its claimed location, and for which the claimant node must correctly respond in order to prove its location. Second, we reverse the strategy by presenting an indirect method, where some transmitters send challenges that the claimant node should not be able to witness. Finally, we present a signal strength based method, where the node responds with its received signal strength and thereby provides improved location verification. To evaluate our schemes, we examine different adversarial models for the claimant, and characterize the performance of our power-modulated challenge response schemes under these adversarial models.