SSS Abstracts  Spring 2011

Presented by Kyung-Ah Sohn, CSD

In this talk, we present a new Bayesian approach for inferring genetic ancestry of individual chromosomes in an admixed population. The chromosomes of African Americans, for example, can be decomposed into segments with distinct ancestry of either African or European. The identification of such chromosomal segments plays an essential role in many applications such as disease gene mapping or population history inference. We employ an infinite hidden Markov model combined with population genetics parameters to describe both the reference and admixed populations in a unified setting. Unlike previous studies which relied on allele frequency profiles or were limited to two-way admixture, our model is built on explicit population generation process using haplotypes and provides more flexible framework that can be applied to admixture from an arbitrary number of populations. The experimental result shows that the proposed method outperforms state-of-the-art methods in simulated datasets under various admixing scenarios. We also present the result on real data of worldwide distributed 29 populations from Human Genome Diversity Project.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

Rational Model Reduction of Flexible Fluid Boundaries

Tuesday, March 1^st, 2011 from 12-1 pm in GHC 8102.

Presented by Matt Stanton, CSD

Model reduction accelerates high resolution physical simulations by projecting high-dimensional dynamical systems to low-dimensional spaces. Standard model reduction can only express polynomial functions, which sharply restricts the range of systems that it can describe. In this talk, we greatly relax this restriction by generalizing model reduction to rational functions.

We apply our rational model reduction technique to the example problem of fluid dynamics in deforming meshes. While this problem lies outside the scope of previous model reduction techniques, our method successfully reduces it, producing speedups on the order of 1000x. These speedups transform slow offline simulations into interactive ones, allowing us to, for example, instantly see the effect of shape deformations on the aerodynamic properties of a car model. Our method may also be applied to a wide variety of other rational systems found in fields from cosmology to biochemistry, providing promising avenues for future work.

Joint work with Martin Wicke, Federico Perazzi, and Adrien Treuille

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

A Tongue-based Input Device for Creating Conversational Interactions

Tuesday, April 5^th, 2011 from 12-1 pm in GHC 8102.

Presented by Ronit Slyper, CSD

We present a narrative of the steps we took, and consequent lessons learned, in the design of a new input device for triggering speech fragments to create a conversational interaction with a child. The device addresses the following problem presented to Disney Research Pittsburgh by theme park Imagineers: how can we provide the means for actors inside bulky Disney character costumes to interact with guests through clandestine triggering of pre-recorded audio snippets? Standard computer input devices will not work because the actor must use his hands and legs for acting. For inspiration on non-standard input methods, we turned to devices used by physically disabled people. In the talk, we present a broad overview of the various methods in use. We settle on the tongue as an available high degree of freedom input modality and create a successful prototype input device. We tested this tongue-input prototype against existing devices in a user study. We show results from this study, and consider future work in the context of the Disney application as well as more generally in assistive devices.

Joint work with Jessica Hodgins, Jodi Forlizzi, and Jill Lehman

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

Answering How-to Questions using the Web

Friday, April 22^nd, 2011 from 12-1 pm in GHC 4303.

Presented by Mehdi Samadi, CSD

The ability to find step-by-step instructions that describe a how-to query is of interest to many users. Although there are specific websites that include how-to instructions for many queries, there is a much wider set of queries that can be answered by using the complete Web. The problem of extracting how-to instructions from the Web is a challenging research area that has not been explored by the Information Extraction (IE) community. In this talk, we present a new approach that uses the Web to find a set of instructions for any how-to query. Our method consists of three phases, namely: crawler, instruction extractor, and bootstrapper. First, crawler searches the given how-to question in Google and downloads the top-K returned webpages. Second, based on global features such as word content (e.g., the word "step" frequently occurs in how-to instructions) that have been automatically learned, instruction extractor then extracts an initial set of instructions. Finally, bootstrapper learns the local features that are specific to a particular how-to question and iteratively extracts a new set of instructions using the local features. Empirical results on a set of how-to questions that are chosen randomly from wikihow.com demonstrates that our method significantly improves performance over a baseline approach.

Joint work with Manuela Veloso and Manuel Blum.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

MoGUL: Detecting Common Insertions and Deletions in a Population

Friday, April 29^th, 2011 from 12-1 pm in GHC 4303.

Presented by Seunghak Lee, CSD

While the discovery of structural variants in the human population is ongoing, most methods for this task assume that the genome is sequenced to high coverage (e.g. 40x), and use the combined power of the many sequenced reads and mate pairs to identify the variants. In contrast, the 1000 Genomes Project hopes to sequence hundreds of human genotypes, but at low coverage (4-6x), and most of the current methods are unable to discover insertion/deletion and structural variants from this data.

In order to identify indels from multiple low-coverage individuals we have developed the MoGUL (Mixture of Genotypes Variant Locator) framework, which identifies potential locations with indels by examining mate pairs generated from all sequenced individuals simultaneously, uses a Bayesian network with appropriate priors to explicitly model each individual as homozygous or heterozygous for each locus, and computes the expected Minor Allele Frequency (MAF) for all predicted variants. We have used MoGUL to identify variants in 1000 Genomes data, as well as in simulated genotypes, and show good accuracy at predicting indels, especially for MAF > 0.06 and indel size > 50 base pairs.

This is joint work with Eric Xing and Michael Brudno.

This will be presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

We Know Who You Followed Last Summer: Inferring Social Link Creation Times In Twitter

Tuesday, May 3^rd, 2011 from 12-1 pm in GHC 7501.

Presented by Brendan Meeder, CSD

Understanding a networks temporal evolution appears to require multiple observations of the graph over time. These often expensive repeated crawls are only able to answer questions about what happened from observation to observation, and not what happened before or between network snapshots. Contrary to this picture, we propose a method for Twitters social network that takes a single static snapshot of network edges and user account creation times to accurately infer when these edges were formed. This method can be exact in theory, and we demonstrate empirically for a large subset of Twitter relationships it is accurate to within hours in practice.

We study users who have a very large number of edges or who are recommended by Twitter. We examine the graph formed by these nearly 1,800 Twitter celebrities and their 862 million edges in detail, showing that a single static snapshot can give novel insights about Twitters evolution. We conclude from this analysis that real-world events and changes to Twitters interface for recommending users strongly influence network growth.

This is joint work with Brian Karrer, Amin Sayedi, R Ravi, Christian Borgs, and Jennifer Chayes.

Simulating Skin Deformation using the Musculoskeletal Structure

Friday, May 6^th, 2011 from 12-1 pm in GHC 4303.

Presented by Q Youn Hong, CSD

Skin deformation is critical to the quality of character animation. In modeling realistic and natural skin deformation, researchers have proposed several approaches such as geometry-based interpolation, data-driven deformation and physics-based simulation. In this talk, we present a method that simulates skin deformation using the underlying musculoskeletal structure. The method first computes the underlying skeletal motion and muscle parameters of the subject with motion capture. The outmost skin layer is then simulated with a mass-spring-damper model. Experimental results shows that our method generates various dynamic skin effects including muscle co-contraction effect and jiggling after impact.

This is joint work with Akihiko Murai, Katsu Yamane and Jessica Hodgins.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

Web contact: sss+www@cs