Surveying the Accessibility of Mobile Touchscreen Games for Persons with Motor Impairments: A Preliminary Analysis - Kim, Y; Sutreja, N; Jon Froehlich; Findlater, L (terpconnect.umd.edu)
ABSTRACT Touchscreen devices have rapidly become one of the most pervasive video game platforms in the world and, in turn, an integral part of popular culture; however, little work exists on comprehensively examining their accessibility. In this poster paper, we ...

Rapid, quantitative therapeutic screening for Alzheimer's enzymes enabled by optimal signal transduction with transistors - Le, Son T.; Morris, Michelle A.; Cardone, Antonio; Guros, Nicholas B.; Klauda, Jeffery B.; Sperling, Brent A.; Richter, Curt A.; Pant, Harish C.; Balijepalli, Arvind (The Analyst, 2020)

Quantum Capacitance-Limited MoS2 Biosensors Enable Remote Label-Free Enzyme Measurements - Le, Son T; Guros, Nicholas B; Bruce, Robert C; Cardone, Antonio; Amin, Niranjana D; Zhang, Siyuan; Klauda, Jeffery; Pant, Harish C; Richter, Curt A; Balijepalli, Arvind (Nanoscale, 2019)

Comparison of Infant Gut and Skin Microbiota, Resistome and Virulome Between Neonatal Intensive Care Unit (NICU) Environments - Hourigan, Suchitra K.; Subramanian, Poorani; Hasan, Nur A.; Ta, Allison; Klein, Elisabeth; Chettout, Nassim; Huddleston, Kathi; Deopujari, Varsha; Levy, Shira; Baveja, R; Clemency, Nicole C.; Baker, Robin L.; et al. (Frontiers in Microbiology, 2018)

Deep-learning-assisted Volume Visualization - Cheng, Hsueh-Chien; Cardone, Antonio; Jain, Somay; Krokos, Eric; Narayan, Kedar; Subramaniam, Sriram; Varshney, Amitabh (IEEE Transactions on Visualization and Computer Graphics, 2018)

Distinct consequences of amoxicillin and ertapenem exposure in the porcine gut microbiome - Connelly, Sheila; Subramanian, Poorani; Hasan, Nur A.; Rita R Colwell; Kaleko, Michael (Anaerobe, 2018)

High-Throughput DNA Sequencing To Profile Microbial Water Quality Of Potable Reuse - Menu B. Leddy; Megan H. Plumlee; Rose S. Kantor; Kara L. Nelson; Scott E. Miller; Lauren C. Kennedy; Blake W. Stamps; John R. Spear; Nur A. Hasan; Rita R Colwell (2018)

Interpolation-Based Gray-Level Co-Occurrence Matrix Computation for Texture Directionality Estimation - Marcin Kociolek; Mary Brady; Peter Bajcsy; Cardone, Antonio (IEEE 22nd Signal Processing Algorithms, Architectures, Arrangements, and Applications Conference, 2018)
A novel interpolation-based model for the computation of the Gray Level Co-occurrence Matrix (GLCM) is presented. The model enables GLCM computation for any real valued angles and offsets, as opposed to the traditional, lattice-based model. A texture directionality estimation algorithm is defined using the GLCM-derived correlation feature. The robustness of the algorithm with respect to image blur and additive Gaussian noise is evaluated. It is concluded that directionality estimation is robust to image blur and low noise levels. For high noise levels, the mean error increases but remains bounded. The performance of the directionality estimation algorithm is illustrated on fluorescence microscopy images of fibroblast cells. The algorithm was implemented in C++ and the source code is available in an openly accessible repository.

Occurrence of Vibrio cholerae in water reservoirs of Burkina Faso - Kaboré, Saidou; Cecchi, Philippe; Mosser, Thomas; Toubiana, Mylène; Traoré, Oumar; Ouattara, Aboubakar S.; Traoré, Alfred S.; Barro, Nicolas; Rita R Colwell; Monfort, Patrick (Research in Microbiology, 2018)
Africa is currently an important region in which cholera epidemics occur. Little is known about the presence of Vibrio cholerae in freshwater bodies in Africa. There are ca. 1700 lakes and reservoirs in Burkina Faso, most of which have been built within recent decades to secure water resources. The purpose of this study was to investigate the presence of V. cholerae in the water of reservoirs, using the most-probable-number polymerase chain reaction. Results showed that V. cholerae could be detected in water samples collected from 14 of 39 sampled reservoirs. The concentrations varied from 0 MPN/l to more than 1100 MPN/l. Fifty strains of V. cholerae isolated on CHROMagar™ vibrio were identified as V. cholerae non-O1/non-O139, none of which carried the ctxA gene. A significant positive correlation was found between the presence of V. cholerae in the reservoirs and both alkaline pH and phytoplankton biomass. V. cholerae was present in significantly higher numbers in reservoirs of urban areas than in rural areas. Since V. cholerae non-O1/non-O139 has been shown to be a causative agent of endemic diarrheal outbreaks, their presence in Burkina Faso reservoirs suggests they may play a role in gastroenteritis in that country.

Spores and soil from six sides: interdisciplinarity and the environmental biology of anthrax (Bacillus anthracis) - Carlson, Colin J.; Getz, Wayne M.; Kausrud, Kyrre L.; Cizauskas, Carrie A.; Blackburn, Jason K.; Bustos Carrillo, Fausto A.; Rita R Colwell; Easterday, W. Ryan; Ganz, Holly H.; Kamath, Pauline L.; Økstad, Ole A.; Turner, Wendy C.; et al. (Biological Reviews, 2018)
Environmentally transmitted diseases are comparatively poorly understood and managed, and their ecology is particularly understudied. Here we identify challenges of studying environmental transmission and persistence with a six‐sided interdisciplinary review of the biology of anthrax (Bacillus anthracis). Anthrax is a zoonotic disease capable of maintaining infectious spore banks in soil for decades (or even potentially centuries), and the mechanisms of its environmental persistence have been the topic of significant research and controversy. Where anthrax is endemic, it plays an important ecological role, shaping the dynamics of entire herbivore communities. The complex eco‐epidemiology of anthrax, and the mysterious biology of Bacillus anthracis during its environmental stage, have necessitated an interdisciplinary approach to pathogen research. Here, we illustrate different disciplinary perspectives through key advances made by researchers working in Etosha National Park, a long‐term ecological research site in Namibia that has exemplified the complexities of the enzootic process of anthrax over decades of surveillance. In Etosha, the role of scavengers and alternative routes (waterborne transmission and flies) has proved unimportant relative to the long‐term persistence of anthrax spores in soil and their infection of herbivore hosts. Carcass deposition facilitates green‐ups of vegetation to attract herbivores, potentially facilitated by the role of anthrax spores in the rhizosphere. The underlying seasonal pattern of vegetation, and herbivores' immune and behavioural responses to anthrax risk, interact to produce regular ‘anthrax seasons’ that appear to be a stable feature of the Etosha ecosystem. Through the lens of microbiologists, geneticists, immunologists, ecologists, epidemiologists, and clinicians, we discuss how anthrax dynamics are shaped at the smallest scale by population genetics and interactions within the bacterial communities up to the broadest scales of ecosystem structure. We illustrate the benefits and challenges of this interdisciplinary approach to disease ecology, and suggest ways anthrax might offer insights into the biology of other important pathogens. Bacillus anthracis, and the more recently emerged Bacillus cereus biovar anthracis, share key features with other environmentally transmitted pathogens, including several zoonoses and panzootics of special interest for global health and conservation efforts. Understanding the dynamics of anthrax, and developing interdisciplinary research programs that explore environmental persistence, is a critical step forward for understanding these emerging threats.

Virulence-Related Genes Identified from the Genome Sequence of the Non-O1/Non-O139 Vibrio cholerae Strain VcN1, Isolated from Dhaka, Bangladesh - Hossain, Maqsud; Alam, Munirul; Khaleque, Abdul; Islam, Sohidul; Sadique, Abdus; Khan, Nayeim; Halim, Zahra; Sarker, Mrinmoy; El-Sayed, Najib M.; Huq, Anwar; Ahsan, Gias Uddin; Rita R Colwell (Genome Announcements, 2018)
We report here the first draft genome sequence of the non-O1/non-O139 Vibrio cholerae strain VcN1, isolated from Dhaka, Bangladesh. The data submitted to GenBank for this strain will contribute to advancing our understanding of this environmentally disseminated bacterium, including its virulence and its evolution as an important pathogen.

Assessment of Risk of Cholera in Haiti following Hurricane Matthew - Huq, Anwar; Anwar, Rifat; Rita R Colwell; McDonald, Michael D.; Khan, Rakib; Jutla, Antarpreet; Akanda, Shafqat (The American Journal of Tropical Medicine and Hygiene, 2017)
Damage to the inferior and fragile water and sanitation infrastructure of Haiti after Hurricane Matthew has created an urgent public health emergency in terms of likelihood of cholera occurring in the human population. Using satellite-derived data on precipitation, gridded air temperature, and hurricane path and with information on water and sanitation (WASH) infrastructure, we tracked changing environmental conditions conducive for growth of pathogenic vibrios. Based on these data, we predicted and validated the likelihood of cholera cases occurring past hurricane. The risk of cholera in the southwestern part of Haiti remained relatively high since November 2016 to the present. Findings of this study provide a contemporary process for monitoring ground conditions that can guide public health intervention to control cholera in human population by providing access to vaccines, safe WASH facilities. Assuming current social and behavioral patterns remain constant, it is recommended that WASH infrastructure should be improved and considered a priority especially before 2017 rainy season.

Comparative genomic analysis and characterization of incompatibility group FIB plasmid encoded virulence factors of Salmonella enterica isolated from food sources - Khajanchi, Bijay K.; Hasan, Nur A.; Choi, Seon Young; Han, Jing; Zhao, Shaohua; Rita R Colwell; Cerniglia, Carl E.; Foley, Steven L. (BMC Genomics, 2017)
BACKGROUND: The degree to which the chromosomal mediated iron acquisition system contributes to virulence of many bacterial pathogens is well defined. However, the functional roles of plasmid encoded iron acquisition systems, specifically Sit and aerobactin, have yet to be determined for Salmonella spp. In a recent study, Salmonella enterica strains isolated from different food sources were sequenced on the Illumina MiSeq platform and found to harbor the incompatibility group (Inc) FIB plasmid. In this study, we examined sequence diversity and the contribution of factors encoded on the IncFIB plasmid to the virulence of S. enterica. RESULTS: Whole genome sequences of seven S. enterica isolates were compared to genomes of serovars of S. enterica isolated from food, animal, and human sources. SeqSero analysis predicted that six strains were serovar Typhimurium and one was Heidelberg. Among the S. Typhimurium strains, single nucleotide polymorphism (SNP)-based phylogenetic analyses revealed that five of the isolates clustered as a single monophyletic S. Typhimurium subclade, while one of the other strains branched with S. Typhimurium from a bovine source. DNA sequence based phylogenetic diversity analyses showed that the IncFIB plasmid-encoded Sit and aerobactin iron acquisition systems are conserved among bacterial species including S. enterica. The IncFIB plasmid was transferred to an IncFIB plasmid deficient strain of S. enterica by conjugation. The transconjugant SE819::IncFIB persisted in human intestinal epithelial (Caco-2) cells at a higher rate than the recipient SE819. Genes of the Sit and aerobactin operons in the IncFIB plasmid were differentially expressed in iron-rich and iron-depleted growth media. CONCLUSIONS: Minimal sequence diversity was detected in the Sit and aerobactin operons in the IncFIB plasmids present among different bacterial species, including foodborne Salmonella strains. IncFIB plasmid encoded factors play a role during infection under low-iron conditions in host cells.

CRISPR-Cas and Contact-Dependent Secretion Systems Present on Excisable Pathogenicity Islands with Conserved Recombination Modules - Carpenter, Megan R.; Kalburge, Sai S.; Borowski, Joseph D.; Peters, Molly C.; Rita R Colwell; Boyd, E. Fidelma (Journal of Bacteriology, 2017)
Pathogenicity islands (PAIs) are mobile integrated genetic elements that contain a diverse range of virulence factors. PAIs integrate into the host chromosome at a tRNA locus that contains their specific bacterial attachment site, attB, via integrase-mediated site-specific recombination generating attL and attR sites. We identified conserved recombination modules (integrases and att sites) previously described in choleragenic Vibrio cholerae PAIs but with novel cargo genes. Clustered regularly interspaced short palindromic repeat (CRISPR)-associated proteins (Cas proteins) and a type VI secretion system (T6SS) gene cluster were identified at the Vibrio pathogenicity island 1 (VPI-1) insertion site in 19 V. cholerae strains and contained the same recombination module. Two divergent type I-F CRISPR-Cas systems were identified, which differed in Cas protein homology and content. The CRISPR repeat sequence was identical among all V. cholerae strains, but the CRISPR spacer sequences and the number of spacers varied. In silico analysis suggests that the CRISPR-Cas systems were active against phages and plasmids. A type III secretion system (T3SS) was present in 12 V. cholerae strains on a 68-kb island inserted at the same tRNA-serine insertion site as VPI-2 and contained the same recombination module. Bioinformatics analysis showed that two divergent T3SSs exist among the strains examined. Both the CRISPR and T3SS islands excised site specifically from the bacterial chromosome as complete units, and the cognate integrases were essential for this excision. These data demonstrated that identical recombination modules that catalyze integration and excision from the chromosome can acquire diverse cargo genes, signifying a novel method of acquisition for both CRISPR-Cas systems and T3SSs.

Deep-learning-assisted visualization for live-cell images - Hsueh-Chien Cheng; Cardone, Antonio; Krokos, Eric; Stoica, Bogdan; Faden, Alan; Varshney, Amitabh (IEEE International Conference on Image Processing, 2017)
Analyzing live-cell images is particularly challenging because cells move at the same time they undergo systematic changes. Visually inspecting live-cell images therefore involves simultaneously tracking individual cells and detecting relevant spatio-temporal changes. The high cognitive burden of such a complex task makes this kind of analysis inefficient and error-prone. In this paper we describe a deep-learning-assisted visualization based on automatically derived high-level features to identify target cell changes in live-cell images. Applying a novel user-mediated color assignment scheme that maps abstract features into corresponding colors, we create color-based visual annotations that facilitate visual reasoning and analysis of complex time varying live-cell imagery datasets. The visual representations can be used to study temporal changes in cells, such as the morphological changes in cell at various stages of life cycle.
Keywords: deep learning; live-cell images; Visualization

Genomic Methods and Microbiological Technologies for Profiling Novel and Extreme Environments for the Extreme Microbiome Project (XMP) - Tighe, Scott; Afshinnekoo, Ebrahim; Rock, Tara M.; McGrath, Ken; Alexander, Noah; McIntyre, Alexa; Ahsanuddin, Sofia; Bezdan, Daniela; Green, Stefan J.; Joye, Samantha; Stewart Johnson, Sarah; Baldwin, Don A.; et al. (Journal of Biomolecular Techniques : JBT, 2017)
The Extreme Microbiome Project (XMP) is a project launched by the Association of Biomolecular Resource Facilities Metagenomics Research Group (ABRF MGRG) that focuses on whole genome shotgun sequencing of extreme and unique environments using a wide variety of biomolecular techniques. The goals are multifaceted, including development and refinement of new techniques for the following: 1) the detection and characterization of novel microbes, 2) the evaluation of nucleic acid techniques for extremophilic samples, and 3) the identification and implementation of the appropriate bioinformatics pipelines. Here, we highlight the different ongoing projects that we have been working on, as well as details on the various methods we use to characterize the microbiome and metagenome of these complex samples. In particular, we present data of a novel multienzyme extraction protocol that we developed, called Polyzyme or MetaPolyZyme. Presently, the XMP is characterizing sample sites around the world with the intent of discovering new species, genes, and gene clusters. Once a project site is complete, the resulting data will be publically available. Sites include Lake Hillier in Western Australia, the “Door to Hell” crater in Turkmenistan, deep ocean brine lakes of the Gulf of Mexico, deep ocean sediments from Greenland, permafrost tunnels in Alaska, ancient microbial biofilms from Antarctica, Blue Lagoon Iceland, Ethiopian toxic hot springs, and the acidic hypersaline ponds in Western Australia.

Hydroclimatic sustainability assessment of changing climate on cholera in the Ganges-Brahmaputra basin - Nasr-Azadani, Fariborz; Khan, Rakibul; Rahimikollu, Javad; Unnikrishnan, Avinash; Akanda, Ali; Alam, Munirul; Huq, Anwar; Jutla, Antarpreet; Rita R Colwell (Advances in Water Resources, 2017)
The association of cholera and climate has been extensively documented. However, determining the effects of changing climate on the occurrence of disease remains a challenge. Bimodal peaks of cholera in Bengal Delta are hypothesized to be linked to asymmetric flow of the Ganges and Brahmaputra rivers. Spring cholera is related to intrusion of bacteria-laden coastal seawater during low flow seasons, while autumn cholera results from cross-contamination of water resources when high flows in the rivers cause massive inundation. Coarse resolution of General Circulation Model (GCM) output (usually at 100 – 300 km)cannot be used to evaluate variability at the local scale(10–20 km),hence the goal of this study was to develop a framework that could be used to understand impacts of climate change on occurrence of cholera. Instead of a traditional approach of downscaling precipitation, streamflow of the two rivers was directly linked to GCM outputs, achieving reasonable accuracy (R2 = 0.89 for the Ganges and R2 = 0.91 for the Brahmaputra)using machine learning algorithms (Support Vector Regression-Particle Swarm Optimization). Copula methods were used to determine probabilistic risks of cholera under several discharge conditions. Key results, using model outputs from ECHAM5, GFDL, andHadCM3for A1B and A2 scenarios, suggest that the combined low flow of the two rivers may increase in the future, with high flows increasing for first half of this century, decreasing thereafter. Spring and autumn cholera, assuming societal conditions remain constant e.g., at the current rate, may decrease. However significant shifts were noted in the magnitude of river discharge suggesting that cholera dynamics of the delta may well demonstrate an uncertain predictable pattern of occurrence over the next century.

Natural Disasters and Cholera Outbreaks: Current Understanding and Future Outlook - Jutla, Antarpreet; Khan, Rakibul; Rita R Colwell (Current Environmental Health Reports, 2017)
Purpose of Review Diarrheal diseases remain a serious global public health threat, especially for those populations lacking access to safe water and sanitation infrastructure. Although association of several diarrheal diseases, e.g., cholera, shigellosis, etc., with climatic processes has been documented, the global human population remains at heightened risk of outbreak of diseases after natural disasters, such as earthquakes, floods, or droughts. In this review, cholera was selected as a signature diarrheal disease and the role of natural disasters in triggering and transmitting cholera was analyzed. Recent Findings Key observations include identification of an inherent feedback loop that includes societal structure, prevailing climatic processes, and spatio-temporal seasonal variability of natural disasters. Data obtained from satellite-based remote sensing are concluded to have application, although limited, in predicting risks of a cholera outbreak(s). Summary We argue that with the advent of new high spectral and spatial resolution data, earth observation systems should be seamlessly integrated in a decision support mechanism to be mobilize resources when a region suffers a natural disaster. A framework is proposed that can be used to assess the impact of natural disasters with response to outbreak of cholera, providing assessment of short- and long-term influence of climatic processes on disease outbreaks.

SYN-004 (ribaxamase), an oral beta-lactamase, mitigates antibiotic-mediated dysbiosis in a porcine gut microbiome model - Connelly, S.; Bristol, J.A.; Hubert, S.; Subramanian, P.; Hasan, N.A.; Rita R Colwell; Kaleko, M. (Journal of Applied Microbiology, 2017)
Aim To evaluate an antibiotic inactivation strategy to protect the gut microbiome from antibiotic‐mediated damage. Methods and Results SYN‐004 (ribaxamase) is an orally delivered beta‐lactamase intended to degrade penicillins and cephalosporins within the gastrointestinal tract to protect the microbiome. Pigs (20 kg, n = 10) were treated with ceftriaxone (CRO) (IV, 50 mg kg−1, SID) for 7 days and a cohort (n = 5) received ribaxamase (PO, 75 mg, QID) for 9 days beginning the day before antibiotic administration. Ceftriaxone serum levels were not statistically different in the antibiotic‐alone and antibiotic + ribaxamase groups, indicating ribaxamase did not alter systemic antibiotic levels. Whole‐genome metagenomic analyses of pig faecal DNA revealed that CRO caused significant changes to the gut microbiome and an increased frequency of antibiotic resistance genes. With ribaxamase, the gut microbiomes were not significantly different from pretreatment and antibiotic resistance gene frequency was not increased. Conclusion Ribaxamase mitigated CRO‐mediated gut microbiome dysbiosis and attenuated propagation of the antibiotic resistance genes in pigs. Significance and Impact of the Study Damage of the microbiome can lead to overgrowth of pathogenic organisms and antibiotic exposure can promote selection for antibiotic‐resistant micro‐organisms. Ribaxamase has the potential to become the first therapy designed to protect the gut microbiome from antibiotic‐mediated dysbiosis and reduce emergence of antibiotic resistance.

Cross-talk among flesh-eating Aeromonas hydrophila strains in mixed infection leading to necrotizing fasciitis - Ponnusamy, Duraisamy; Kozlova, Elena V.; Sha, Jian; Erova, Tatiana E.; Azar, Sasha R.; Fitts, Eric C.; Kirtley, Michelle L.; Tiner, Bethany L.; Andersson, Jourdan A.; Grim, Christopher J.; Isom, Richard P.; Hasan, Nur A.; et al. (Proceedings of the National Academy of Sciences, 2016)
Necrotizing fasciitis (NF) caused by flesh-eating bacteria is associated with high case fatality. In an earlier study, we reported infection of an immunocompetent individual with multiple strains of Aeromonas hydrophila (NF1–NF4), the latter three constituted a clonal group whereas NF1 was phylogenetically distinct. To understand the complex interactions of these strains in NF pathophysiology, a mouse model was used, whereby either single or mixed A. hydrophila strains were injected intramuscularly. NF2, which harbors exotoxin A (exoA) gene, was highly virulent when injected alone, but its virulence was attenuated in the presence of NF1 (exoA-minus). NF1 alone, although not lethal to animals, became highly virulent when combined with NF2, its virulence augmented by cis-exoA expression when injected alone in mice. Based on metagenomics and microbiological analyses, it was found that, in mixed infection, NF1 selectively disseminated to mouse peripheral organs, whereas the other strains (NF2, NF3, and NF4) were confined to the injection site and eventually cleared. In vitro studies showed NF2 to be more effectively phagocytized and killed by macrophages than NF1. NF1 inhibited growth of NF2 on solid media, but ExoA of NF2 augmented virulence of NF1 and the presence of NF1 facilitated clearance of NF2 from animals either by enhanced priming of host immune system or direct killing via a contact-dependent mechanism.

Modeling Sustainability: Population, Inequality, Consumption, and Bidirectional Coupling of the Earth and Human Systems - Motesharrei, Safa; Rivas, Jorge; Kalnay, Eugenia; Asrar, Ghassem R.; Busalacchi, Antonio J.; Cahalan, Robert F.; Cane, Mark A.; Rita R Colwell; Feng, Kuishuang; Franklin, Rachel S.; Hubacek, Klaus; Miralles-Wilhelm, Fernando; et al. (National Science Review, 2016)
Over the last two centuries, the impact of the Human System has grown dramatically, becoming strongly dominant within the Earth System in many different ways. Consumption, inequality, and population have increased extremely fast, especially since about 1950, threatening to overwhelm the many critical functions and ecosystems of the Earth System. Changes in the Earth System, in turn, have important feedback effects on the Human System, with costly and potentially serious consequences. However, current models do not incorporate these critical feedbacks. We argue that in order to understand the dynamics of either system, Earth System Models must be coupled with Human System Models through bidirectional couplings representing the positive, negative, and delayed feedbacks that exist in the real systems. In particular, key Human System variables, such as demographics, inequality, economic growth, and migration, are not coupled with the Earth System but are instead driven by exogenous estimates, such as United Nations population projections. This makes current models likely to miss important feedbacks in the real Earth–Human system, especially those that may result in unexpected or counterintuitive outcomes, and thus requiring different policy interventions from current models. The importance and imminence of sustainability challenges, the dominant role of the Human System in the Earth System, and the essential roles the Earth System plays for the Human System, all call for collaboration of natural scientists, social scientists, and engineers in multidisciplinary research and modeling to develop coupled Earth–Human system models for devising effective science-based policies and measures to benefit current and future generations.

Environmental Surveillance for Toxigenic Vibrio cholerae in Surface Waters of Haiti - Hill, Vincent R.; Humphrys, Michael S.; Kahler, Amy M.; Boncy, Jacques; Tarr, Cheryl L.; Huq, Anwar; Chen, Arlene; Katz, Lee S.; Mull, Bonnie J.; Derado, Gordana; Haley, Bradd J.; Freeman, Nicole; et al. (The American Journal of Tropical Medicine and Hygiene, 2015)
Epidemic cholera was reported in Haiti in 2010, with no information available on the occurrence or geographic distribution of toxigenic Vibrio cholerae in Haitian waters. In a series of field visits conducted in Haiti between 2011 and 2013, water and plankton samples were collected at 19 sites. Vibrio cholerae was detected using culture, polymerase chain reaction, and direct viable count methods (DFA-DVC). Cholera toxin genes were detected by polymerase chain reaction in broth enrichments of samples collected in all visits except March 2012. Toxigenic V. cholerae was isolated from river water in 2011 and 2013. Whole genome sequencing revealed that these isolates were a match to the outbreak strain. The DFA-DVC tests were positive for V. cholerae O1 in plankton samples collected from multiple sites. Results of this survey show that toxigenic V. cholerae could be recovered from surface waters in Haiti more than 2 years after the onset of the epidemic.

Estimating Actin Fiber Orientation using Interpolation-Based Grey-Level Co-Occurrence Matrix Computation - Cardone, Antonio; Brady, Mary; Kociolek, Marcin; Bajcsy, Peter (BioImage Informatics Conference, 2015)

Hybrid Vibrio cholerae El Tor Lacking SXT Identified as the Cause of a Cholera Outbreak in the Philippines - Klinzing, David C.; Choi, Seon Young; Hasan, Nur A.; Matias, Ronald R.; Tayag, Enrique; Geronimo, Josefina; Skowronski, Evan; Rashed, Shah M.; Kawashima, Kent; Rosenzweig, C. Nicole; Gibbons, Henry S.; Torres, Brian C.; et al. (mBio, 2015)
Cholera continues to be a global threat, with high rates of morbidity and mortality. In 2011, a cholera outbreak occurred in Palawan, Philippines, affecting more than 500 people, and 20 individuals died. Vibrio cholerae O1 was confirmed as the etiological agent. Source attribution is critical in cholera outbreaks for proper management of the disease, as well as to control spread. In this study, three V. cholerae O1 isolates from a Philippines cholera outbreak were sequenced and their genomes analyzed to determine phylogenetic relatedness to V. cholerae O1 isolates from recent outbreaks of cholera elsewhere. The Philippines V. cholerae O1 isolates were determined to be V. cholerae O1 hybrid El Tor belonging to the seventh-pandemic clade. They clustered tightly, forming a monophyletic clade closely related to V. cholerae O1 hybrid El Tor from Asia and Africa. The isolates possess a unique multilocus variable-number tandem repeat analysis (MLVA) genotype (12-7-9-18-25 and 12-7-10-14-21) and lack SXT. In addition, they possess a novel 15-kb genomic island (GI-119) containing a predicted type I restriction-modification system. The CTXΦ-RS1 array of the Philippines isolates was similar to that of V. cholerae O1 MG116926, a hybrid El Tor strain isolated in Bangladesh in 1991. Overall, the data indicate that the Philippines V. cholerae O1 isolates are unique, differing from recent V. cholerae O1 isolates from Asia, Africa, and Haiti. Furthermore, the results of this study support the hypothesis that the Philippines isolates of V. cholerae O1 are indigenous and exist locally in the aquatic ecosystem of the Philippines.

Occurrence and Diversity of Clinically Important Vibrio Species in the Aquatic Environment of Georgia - Kokashvili, Tamar; Whitehouse, Chris A.; Tskhvediani, Ana; Grim, Christopher J.; Elbakidze, Tinatin; Mitaishvili, Nino; Janelidze, Nino; Jaiani, Ekaterine; Haley, Bradd J.; Lashkhi, Nino; Huq, Anwar; Rita R Colwell; et al. (Frontiers in Public Health, 2015)

Segmentation and sub-cellular feature-based analysis of microscopy images - Cardone, Antonio; Chalfoun, Joe; Peskin, Adele; Bajcsy, Peter; Kociolek, Marcin; Bhadriraju, Kiran; Brady, Mary (BioImage Informatics Conference, 2015)

Survey statistics of automated segmentations applied to optical imaging of mammalian cells - Bajcsy, Peter; Cardone, Antonio; Chalfoun, Joe; Halter, Michael; Juba, Derek; Kociolek, Marcin; Majurski, Michael; Peskin, Adele; Simon, Carl; Simon, Mylene; others (BMC bioinformatics, 2015)

A unified initiative to harness Earth's microbiomes - Alivisatos, A. P.; Blaser, M. J.; Brodie, E. L.; Chun, M.; Dangl, J. L.; Donohue, T. J.; Dorrestein, P. C.; Gilbert, J. A.; Green, J. L.; Jansson, J. K.; Knight, R.; Maxon, M. E.; et al. (Science, 2015)

Vibrio metoecus sp. nov., a close relative of Vibrio cholerae isolated from coastal brackish ponds and clinical specimens - Kirchberger, P. C.; Turnsek, M.; Hunt, D. E.; Haley, B. J.; Rita R Colwell; Polz, M. F.; Tarr, C. L.; Boucher, Y. (INTERNATIONAL JOURNAL OF SYSTEMATIC AND EVOLUTIONARY MICROBIOLOGY, 2014)

On Minimal Assumptions for Sender-Deniable Public Key Encryption - Dana Dachman-Soled (Public-Key Cryptography – PKC 2014, 2014)
The primitive of deniable encryption was introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is an encryption scheme with the added feature that after transmitting a message m, both sender and receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message m′ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain adaptively-secure multiparty computation (MPC) protocols and is secure under selective-opening attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the sender or receiver produce fake random coins, have been considered. Recently, over 15 years after the primitive was first introduced, Sahai and Waters (IACR Cryptology ePrint Archive, 2013), gave the first construction of sender-deniable encryption schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. Their construction is based on the construction of an indistinguishability obfuscator for general programs recently introduced in a breakthrough result of Garg et al. (FOCS, 2013). Although feasibility has now been demonstrated, the question of determining the minimal assumptions necessary for sender-deniable encryption with super-polynomial security remains open. The primitive of simulatable public key encryption (PKE), introduced by Damgård and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O’Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with super-polynomial security from simulatable PKE. In this work, we investigate the possibility of constructing sender-deniable public key encryption from simulatable PKE in a black-box manner. We show that there is no black-box construction of sender-deniable public key encryption with super-polynomial security from simulatable PKE. This indicates that improving on the original construction of Canetti et al. requires the use of non-black-box techniques, stronger assumptions, or interaction, thus giving some evidence that strong assumptions such as those used by Sahai and Waters are necessary.
Keywords: Algorithm Analysis and Problem Complexity; black-box separation; Coding and Information Theory; Data Encryption; sender-deniable encryption; simulatable PKE; Systems and Data Security

Molecular diversity and predictability of Vibrio parahaemolyticus along the Georgian coastal zone of the Black Sea - Haley, Bradd J.; Kokashvili, Tamar; Tskshvediani, Ana; Janelidze, Nino; Mitaishvili, Nino; Grim, Christopher J.; Constantin_de_Magny, Guillaume; Chen, Arlene J.; Taviani, Elisa; Eliashvili, Tamar; Tediashvili, Marina; Whitehouse, Chris A.; et al. (Frontiers in Microbiology, 2014)
Vibrio parahaemolyticus is a leading cause of seafood-related gastroenteritis and is also an autochthonous member of marine and estuarine environments worldwide. One-hundred seventy strains of V. parahaemolyticus were isolated from water and plankton samples collected along the Georgian coast of the Black Sea during 28 months of sample collection. All isolated strains were tested for presence of tlh, trh, and tdh. A subset of strains were serotyped and tested for additional factors and markers of pandemicity. Twenty-six serotypes, five of which are clinically relevant, were identified. Although all 170 isolates were negative for tdh, trh, and the Kanagawa Phenomenon, 7 possessed the GS-PCR sequence and 27 the 850 bp sequence of V. parahaemolyticus pandemic strains. The V. parahaemolyticus population in the Black Sea was estimated to be genomically heterogeneous by rep-PCR and the serodiversity observed did not correlate with rep-PCR genomic diversity. Statistical modeling was used to predict presence of V. parahaemolyticus as a function of water temperature, with strongest concordance observed for Green Cape site samples (Percent of total variance = 70, P < 0.001). Results demonstrate a diverse population of V. parahaemolyticus in the Black Sea, some of which carry pandemic markers, with increased water temperature correlated to an increase in abundance of V. parahaemolyticus.

Phylodynamic Analysis of Clinical and Environmental Vibrio cholerae Isolates from Haiti Reveals Diversification Driven by Positive Selection - Azarian, Taj; Ali, Afsar; Johnson, Judith A.; Mohr, David; Prosperi, Mattia; Veras, Nazle M.; Jubair, Mohammed; Strickland, Samantha L.; Rashid, Mohammad H.; Alam, Meer T.; Weppelmann, Thomas A.; Katz, Lee S.; et al. (mBio, 2014)
Phylodynamic analysis of genome-wide single-nucleotide polymorphism (SNP) data is a powerful tool to investigate underlying evolutionary processes of bacterial epidemics. The method was applied to investigate a collection of 65 clinical and environmental isolates of Vibrio cholerae from Haiti collected between 2010 and 2012. Characterization of isolates recovered from environmental samples identified a total of four toxigenic V. cholerae O1 isolates, four non-O1/O139 isolates, and a novel nontoxigenic V. cholerae O1 isolate with the classical tcpA gene. Phylogenies of strains were inferred from genome-wide SNPs using coalescent-based demographic models within a Bayesian framework. A close phylogenetic relationship between clinical and environmental toxigenic V. cholerae O1 strains was observed. As cholera spread throughout Haiti between October 2010 and August 2012, the population size initially increased and then fluctuated over time. Selection analysis along internal branches of the phylogeny showed a steady accumulation of synonymous substitutions and a progressive increase of nonsynonymous substitutions over time, suggesting diversification likely was driven by positive selection. Short-term accumulation of nonsynonymous substitutions driven by selection may have significant implications for virulence, transmission dynamics, and even vaccine efficacy.

Stable isotope labeling of phosphoproteins for large-scale phosphorylation rate determination - Molden, Rosalynn C.; Goya, Jonathan; Zia Khan; Garcia, Benjamin A. (Molecular & Cellular Proteomics, 2014)
Signals that control response to stimuli and cellular function are transmitted through dynamic phosphorylation of thousands of proteins by protein kinases. Many techniques have been developed to study phosphorylation dynamics, including several mass spectrometry (MS)-based methods. Over the last few decades, substantial developments have been made in MS techniques for the large-scale identification of proteins and their post-translational modifications. Nevertheless, all of the current MS-based techniques for quantifying protein phosphorylation dynamics rely on the measurement of changes in peptide abundance levels and many methods suffer from low confidence in phosphopeptide identification due to poor fragmentation. Here we have optimized an approach for the Stable Isotope Labeling of Amino acids by Phosphate (SILAP) using [gamma-18O4]ATP in nucleo to determine global site-specific phosphorylation rates. The advantages of this metabolic labeling technique are: increased confidence in phosphorylated peptide identification, direct labeling of phosphorylation sites, measurement phosphorylation rates, and the identification of actively phosphorylated sites in a cell-like environment. In this study we calculated approximate rate constants for over 500 phosphorylation sites based on labeling progress curves. We measured a wide range of phosphorylation rate constants from 0.34 min-1 to 0.001 min-1. Finally, we applied SILAP to determine sites that have different phosphorylation kinetics during G1/S and M phase. We found that most sites have very similar phosphorylation rates under both conditions; however a small subset of sites on proteins involved in the mitotic spindle were more actively phosphorylated during M phase, while proteins involved in DNA replication and transcription were more actively phosphorylated during G1/S phase.
Keywords: DYNAMICS; Phosphoproteins*; Phosphoproteome; Phosphorylation; Post-translational modifications*; Signal Transduction*; turnover

Validation of high throughput sequencing and microbial forensics applications - Budowle, Bruce; Connell, Nancy D; Bielecka-Oder, Anna; Rita R Colwell; Corbett, Cindi R; Fletcher, Jacqueline; Forsman, Mats; Kadavy, Dana R; Markotic, Alemka; Morse, Stephen A; Murch, Randall S; Sajantila, Antti; et al. (Investigative Genetics, 2014)
High throughput sequencing (HTS) generates large amounts of high quality sequence data for microbial genomics. The value of HTS for microbial forensics is the speed at which evidence can be collected and the power to characterize microbial-related evidence to solve biocrimes and bioterrorist events. As HTS technologies continue to improve, they provide increasingly powerful sets of tools to support the entire field of microbial forensics. Accurate, credible results allow analysis and interpretation, significantly influencing the course and/or focus of an investigation, and can impact the response of the government to an attack having individual, political, economic or military consequences. Interpretation of the results of microbial forensic analyses relies on understanding the performance and limitations of HTS methods, including analytical processes, assays and data interpretation. The utility of HTS must be defined carefully within established operating conditions and tolerances. Validation is essential in the development and implementation of microbial forensics methods used for formulating investigative leads attribution. HTS strategies vary, requiring guiding principles for HTS system validation. Three initial aspects of HTS, irrespective of chemistry, instrumentation or software are: 1) sample preparation, 2) sequencing, and 3) data analysis. Criteria that should be considered for HTS validation for microbial forensics are presented here. Validation should be defined in terms of specific application and the criteria described here comprise a foundation for investigators to establish, validate and implement HTS as a tool in microbial forensics, enhancing public safety and national security.

A Dataset for Quality Assessment of Camera Captured Document Images - Kumar, J; Ye, P; David Doermann (2013)
Abstract—With the proliferation of cameras on mobile devices there is an increased desire to image document pages as an alternative to scanning. However, the quality of captured document images is often lower than its scanned equivalent due to hardware limitations ...

Distinct Rap1 Activity States Control the Extent of Epithelial Invagination via α-Catenin - Wang, Yu-Chiun; Zia Khan; Wieschaus, Eric F. (Developmental Cell, 2013)
Localized cell shape change initiates epithelial folding, while neighboring cell invagination determines the final depth of an epithelial fold. The mechanism that controls the extent of invagination remains unknown. During Drosophila gastrulation, a higher number of cells undergo invagination to form the deep posterior dorsal fold, whereas far fewer cells become incorporated into the initially very similar anterior dorsal fold. We find that a decrease in α-catenin activity causes the anterior fold to invaginate as extensively as the posterior fold. In contrast, constitutive activation of the small GTPase Rap1 restricts invagination of both dorsal folds in an α-catenin-dependent manner. Rap1 activity appears spatially modulated by Rapgap1, whose expression levels are high in the cells that flank the posterior fold but low in the anterior fold. We propose a model whereby distinct activity states of Rap1 modulate α-catenin-dependent coupling between junctions and actin to control the extent of epithelial invagination.

Drug response and genetic properties of Vibrio cholerae associated with endemic cholera in north-eastern Thailand, 2003-2011 - Chomvarin, C.; Johura, F.-T.; Mannan, S. B.; Jumroenjit, W.; Kanoktippornchai, B.; Tangkanakul, W.; Tantisuwichwong, N.; Huttayananont, S.; Watanabe, H.; Hasan, N. A.; Huq, A.; Cravioto, A.; et al. (Journal of Medical Microbiology, 2013)
Cholera, caused by Vibrio cholerae, results in significant morbidity and mortality worldwide, including Thailand. Representative V. cholerae strains associated with endemic cholera (n = 32), including strains (n = 3) from surface water sources, in Khon Kaen, Thailand (2003–2011), were subjected to microbiological, molecular and phylogenetic analyses. According to phenotypic and related genetic data, all tested V. cholerae strains belonged to serogroup O1, biotype El Tor (ET), Inaba (IN) or Ogawa (OG). All of the strains were sensitive to gentamicin and ciprofloxacin, while multidrug-resistant (MDR) strains showing resistance to erythromycin, tetracycline, trimethoprim/sulfamethoxazole and ampicillin were predominant in 2007. V. cholerae strains isolated before and after 2007 were non-MDR. All except six diarrhoeal strains possessed ctxA and ctxB genes and were toxigenic altered ET, confirmed by MAMA-PCR and DNA sequencing. Year-wise data revealed that V. cholerae INET strains isolated between 2003 and 2004, plus one strain isolated in 2007, lacked the RS1 sequence (rstC) and toxin-linked cryptic plasmid (TLC)-specific genetic marker, but possessed CTXCL prophage genes ctxB CL and rstR CL. A sharp genetic transition was noted, namely the majority of V. cholerae strains in 2007 and all in 2010 and 2011 were not repressor genotype rstR CL but instead were rstR ET, and all ctx + strains possessed RS1 and TLC-specific genetic markers. DNA sequencing data revealed that strains isolated since 2007 had a mutation in the tcpA gene at amino acid position 64 (N→S). Four clonal types, mostly of environmental origin, including subtypes, reflected genetic diversity, while distinct signatures were observed for clonally related, altered ET from Thailand, Vietnam and Bangladesh, confirmed by distinct subclustering patterns observed in the PFGE (NotI)-based dendrogram, suggesting that endemic cholera is caused by V. cholerae indigenous to Khon Kaen.

Mind the Theoretical Gap: Interpreting, Using, and Developing Behavioral Theory in HCI Research - Hekler, E. B.; Klasnja,P.; Jon Froehlich; Buman, M. P. (CHI 2013 To Appear, 2013)

Parallel and Dynamic Searchable Symmetric Encryption - Kamara, Seny; Charalampos Papamanthou (Financial Cryptography and Data Security, 2013)
Searchable symmetric encryption (SSE) enables a client to outsource a collection of encrypted documents in the cloud and retain the ability to perform keyword searches without revealing information about the contents of the documents and queries. Although efficient SSE constructions are known, previous solutions are highly sequential. This is mainly due to the fact that, currently, the only method for achieving sub-linear time search is the inverted index approach (Curtmola, Garay, Kamara and Ostrovsky, CCS ’06) which requires the search algorithm to access a sequence of memory locations, each of which is unpredictable and stored at the previous location in the sequence. Motivated by advances in multi-core architectures, we present a new method for constructing sub-linear SSE schemes. Our approach is highly parallelizable and dynamic. With roughly a logarithmic number of cores in place, searches for a keyword w in our scheme execute in o(r) parallel time, where r is the number of documents containing keyword w (with more cores, this bound can go down to O(logn), i.e., independent of the result size r). Such time complexity outperforms the optimal Θ(r) sequential search time—a similar bound holds for the updates. Our scheme also achieves the following important properties: (a) it enjoys a strong notion of security, namely security against adaptive chosen-keyword attacks; (b) compared to existing sub-linear dynamic SSE schemes (e.g., Kamara, Papamanthou, Roeder, CCS ’12), updates in our scheme do not leak any information, apart from information that can be inferred from previous search tokens; (c) it can be implemented efficiently in external memory (with logarithmic I/O overhead). Our technique is simple and uses a red-black tree data structure; its security is proven in the random oracle model.
Keywords: cloud storage; Computer Appl. in Administrative Data Processing; Data Encryption; e-Commerce/e-business; parallel search; Searchable encryption; Systems and Data Security

Parallel geometric classification of stem cells by their three-dimensional morphology - Juba,Derek; Cardone, Antonio; Ip, Cheuk Yiu; Simon Jr, Carl G; K Tison, Christopher; Kumar, Girish; Brady,Mary; Varshney, Amitabh (Computational Science & Discovery, 2013)

Primate Transcript and Protein Expression Levels Evolve Under Compensatory Selection Pressures - Zia Khan; Ford, Michael J.; Cusanovich, Darren A.; Mitrano, Amy; Pritchard, Jonathan K.; Gilad, Yoav (Science, 2013)
Changes in gene regulation have likely played an important role in the evolution of primates. Differences in messenger RNA (mRNA) expression levels across primates have often been documented; however, it is not yet known to what extent measurements of divergence in mRNA levels reflect divergence in protein expression levels, which are probably more important in determining phenotypic differences. We used high-resolution, quantitative mass spectrometry to collect protein expression measurements from human, chimpanzee, and rhesus macaque lymphoblastoid cell lines and compared them to transcript expression data from the same samples. We found dozens of genes with significant expression differences between species at the mRNA level yet little or no difference in protein expression. Overall, our data suggest that protein expression levels evolve under stronger evolutionary constraint than mRNA levels.Don't Ape Protein Variation Changes in DNA and messenger RNA (mRNA) expression levels have been used to estimate evolutionary changes between species. However protein expression levels may better reflect selection on divergent and constrained phenotypes. Khan et al. (p. 1100, published online 17 October; see the Perspective by Vogel) measured the differences among and within species between mRNA expression and protein levels in humans, chimpanzees, and rhesus macaques, identifying protein transcripts that seem to be under lineage-specific constraint between humans and chimpanzees.

Real-time No-Reference Image Quality Assessment based on Filter Learning - Ye,Peng; Kumar,Jayant; Kang,Le; David Doermann (International Conference on Computer Vision and Pattern Recognition (CVPR), 2013)

Segmenting time-lapse phase contrast images of adjacent NIH 3T3 cells. - Chalfoun, J; Kociolek, M; Dima, A; Halter, M; Cardone, Antonio; Peskin, A; Bajcsy, P; Brady, M. (Journal of microscopy, 2013)
We present a new method for segmenting phase contrast images of NIH 3T3 fibroblast cells that is accurate even when cells are physically in contact with each other. The problem of segmentation, when cells are in contact, poses a challenge to the accurate automation of cell counting, tracking and lineage modelling in cell biology. The segmentation method presented in this paper consists of (1) background reconstruction to obtain noise-free foreground pixels and (2) incorporation of biological insight about dividing and nondividing cells into the segmentation process to achieve reliable separation of foreground pixels defined as pixels associated with individual cells. The segmentation results for a time-lapse image stack were compared against 238 manually segmented images (8219 cells) provided by experts, which we consider as reference data. We chose two metrics to measure the accuracy of segmentation: the 'Adjusted Rand Index' which compares similarities at a pixel level between masks resulting from manual and automated segmentation, and the 'Number of Cells per Field' (NCF) which compares the number of cells identified in the field by manual versus automated analysis. Our results show that the automated segmentation compared to manual segmentation has an average adjusted rand index of 0.96 (1 being a perfect match), with a standard deviation of 0.03, and an average difference of the two numbers of cells per field equal to 5.39% with a standard deviation of 4.6%.
Keywords: Animals; Cell Adhesion; Cell Count; Cell Division; Cell Shape; Computational Biology; Fibroblasts; Image Processing, Computer-Assisted; Mice; Microscopy, Phase-Contrast; NIH 3T3 Cells; Reproducibility of results; Sensitivity and Specificity; Time-Lapse Imaging

Structural similarity for document image classification and retrieval - Kumar, Jayant; Ye, Peng; David Doermann (Pattern Recognition Letters, 2013)
Abstract This paper presents a novel approach to defining document image structural similarity for the applications of classification and retrieval. We first build a codebook of SURF descriptors extracted from a set of representative training images. We then encode ...

Unsupervised Classification of Structurally Similar Document Images - Kumar,Jayant; David Doermann (International Conference on Document Analysis and Recognition, 2013)

Why “Fiat-Shamir for Proofs” Lacks a Proof - Bitansky, Nir; Dana Dachman-Soled; Garg, Sanjam; Jain, Abhishek; Kalai, Yael Tauman; López-Alt, Adriana; Wichs, Daniel (Theory of Cryptography, 2013)
The Fiat-Shamir heuristic [CRYPTO ’86] is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover’s first message to select the verifier’s challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai [FOCS ’03] shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps we can securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if we must fail for some computationally sound arguments. Indeed, this has been conjectured to be the case by Barak, Lindell and Vadhan [FOCS ’03], but we do not have any provably secure instantiation under any “standard assumption”. In this work, we give a broad black-box separation result showing that the security of the Fiat-Shamir heuristic for statistically sound proofs cannot be proved under virtually any standard assumption via a black-box reduction. More precisely: –If we want to have a “universal” instantiation of the Fiat-Shamir heuristic that works for all 3-message public-coin proofs, then we cannot prove its security via a black-box reduction from any assumption that has the format of a “cryptographic game”. –For many concrete proof systems, if we want to have a “specific” instantiation of the Fiat-Shamir heuristic for that proof system, then we cannot prove its security via a black box reduction from any “falsifiable assumption” that has the format of a cryptographic game with an efficient challenger.
Keywords: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Encryption; Systems and Data Security

An additional step in the transmission of Yersinia pestis? - Easterday, W Ryan; Kausrud, Kyrre L; Star, Bastiaan; Heier, Lise; Haley, Bradd J; Ageyev, Vladimir; Rita R Colwell; Stenseth, Nils Chr (The ISME Journal, 2012)
Plague, caused by the bacterium Yersinia pestis, is a mammalian vector-borne disease, transmitted by fleas that serve as the vector between rodent hosts. For many pathogens, including Y. pestis, there are strong evolutionary pressures that lead to a reduction in ‘useless genes’, with only those retained that reflect function in the specific environment inhabited by the pathogen. Genetic traits critical for survival and transmission between two environments, the rodent and the flea, are conserved in epizootic/epidemic plague strains. However, there are genes that remain conserved for which no function in the flea–rodent cycle has yet been observed, indicating an additional environment may exist in the transmission cycle of plague. Here, we present evidence for highly conserved genes that suggests a role in the persistence of Y. pestis after death of its host. Furthermore, maintenance of these genes points to Y. pestis traversing a post-mortem path between, and possibly within, epizootic periods and offering insight into mechanisms that may allow Y. pestis an alternative route of transmission in the natural environment.

BclAF1 restriction factor is neutralized by proteasomal degradation and microRNA repression during human cytomegalovirus infection - Lee, Song Hee; Kalejta, Robert F.; Kerry, Julie; Semmes, Oliver John; O’Connor, Christine M.; Zia Khan; Garcia, Benjamin A.; Shenk, Thomas; Murphy, Eain (Proceedings of the National Academy of Sciences, 2012)
Cell proteins can restrict the replication of viruses. Here, we identify the cellular BclAF1 protein as a human cytomegalovirus restriction factor and describe two independent mechanisms the virus uses to decrease its steady-state levels. Immediately following infection, the viral pp71 and UL35 proteins, which are delivered to cells within virions, direct the proteasomal degradation of BclAF1. Although BclAF1 reaccumulates through the middle stages of infection, it is subsequently down-regulated at late times by miR-UL112-1, a virus-encoded microRNA. In the absence of BclAF1 neutralization, viral gene expression and replication are inhibited. These data identify two temporally and mechanistically distinct functions used by human cytomegalovirus to down-regulate a cellular antiviral protein.
Keywords: innate immunity; intrinsic immunity; miRNA; Proteasome; UL82

#bias: Measuring the Tweeting Behavior of Propagandists - Lumezanu,Cristian; Feamster, Nick; Klein,Hans (Sixth International AAAI Conference on Weblogs and Social Media, 2012)
#bias: Measuring the Tweeting Behavior of Propagandists

Collecting Semantic Similarity Ratings to Connect Concepts in Assistive Communication Tools - Nikolova,Sonya; Jordan Boyd-Graber; Fellbaum,Christiane (Modeling, Learning, and Processing of Text Technological Data StructuresModeling, Learning, and Processing of Text Technological Data Structures, 2012)
To compensate for the common inability of people with lexical production impairments to access and express intended concepts, we make use of models of human semantic memory that build on the notion of semantic similarity and relatedness. Such models, constructed on evidence gained from psycholinguistic experiments, form the basis of a large lexical database, WordNet . We augment WordNet with many additional links among words and concepts that are semantically related. Making this densely connected semantic network available to people with anomic aphasia through assistive technologies should enable them to navigate among related words and concepts and retrieve the words that they intend to express.

Computational Extractors and Pseudorandomness - Dana Dachman-Soled; Gennaro, Rosario; Krawczyk, Hugo; Malkin, Tal (Theory of Cryptography, 2012)
Computational extractors are efficient procedures that map a source of sufficiently high min-entropy to an output that is computationally indistinguishable from uniform. By relaxing the statistical closeness property of traditional randomness extractors one hopes to improve the efficiency and entropy parameters of these extractors, while keeping their utility for cryptographic applications. In this work we investigate computational extractors and consider questions of existence and inherent complexity from the theoretical and practical angles, with particular focus on the relationship to pseudorandomness. An obvious way to build a computational extractor is via the “extract-then-prg” method: apply a statistical extractor and use its output to seed a PRG. This approach carries with it the entropy cost inherent to implementing statistical extractors, namely, the source entropy needs to be substantially higher than the PRG’s seed length. It also requires a PRG and thus relies on one-way functions. We study the necessity of one-way functions in the construction of computational extractors and determine matching lower and upper bounds on the “black-box efficiency” of generic constructions of computational extractors that use a one-way permutation as an oracle. Under this efficiency measure we prove a direct correspondence between the complexity of computational extractors and that of pseudorandom generators, showing the optimality of the extract-then-prg approach for generic constructions of computational extractors and confirming the intuition that to build a computational extractor via a PRG one needs to make up for the entropy gap intrinsic to statistical extractors. On the other hand, we show that with stronger cryptographic primitives one can have more entropy- and computationally-efficient constructions. In particular, we show a construction of a very practical computational extractor from any weak PRF without resorting to statistical extractors.
Keywords: Algorithm Analysis and Problem Complexity; Coding and Information Theory; Computer Communication Networks; Data Encryption; Math Applications in Computer Science; Systems and Data Security

Deep Sequencing of the Oral Microbiome Reveals Signatures of Periodontal Disease - Liu,B.; Faller, L.L.; Klitgord, N.; Mazumdar, V.; Ghodsi,M.; Sommer, D.D.; Gibbons, T.R.; Treangen, T.J.; Chang, Y.C.; Li,S. (PloS one, 2012)
The oral microbiome, the complex ecosystem of microbes inhabiting the human mouth, harbors several thousands of bacterial types. The proliferation of pathogenic bacteria within the mouth gives rise to periodontitis, an inflammatory disease known to also constitute a risk factor for cardiovascular disease. While much is known about individual species associated with pathogenesis, the system-level mechanisms underlying the transition from health to disease are still poorly understood. Through the sequencing of the 16S rRNA gene and of whole community DNA we provide a glimpse at the global genetic, metabolic, and ecological changes associated with periodontitis in 15 subgingival plaque samples, four from each of two periodontitis patients, and the remaining samples from three healthy individuals. We also demonstrate the power of whole-metagenome sequencing approaches in characterizing the genomes of key players in the oral microbiome, including an unculturable TM7 organism. We reveal the disease microbiome to be enriched in virulence factors, and adapted to a parasitic lifestyle that takes advantage of the disrupted host homeostasis. Furthermore, diseased samples share a common structure that was not found in completely healthy samples, suggesting that the disease state may occupy a narrow region within the space of possible configurations of the oral microbiome. Our pilot study demonstrates the power of high-throughput sequencing as a tool for understanding the role of the oral microbiome in periodontal disease. Despite a modest level of sequencing (~2 lanes Illumina 76 bp PE) and high human DNA contamination (up to ~90%) we were able to partially reconstruct several oral microbes and to preliminarily characterize some systems-level differences between the healthy and diseased oral microbiomes.

Detection, Isolation, and Identification of Vibrio cholerae from the Environment - Huq, Anwar; Haley, Bradd J.; Taviani, Elisa; Chen, Arlene; Hasan, Nur A.; Rita R Colwell (Current Protocols in Microbiology, 2012)
Recent molecular advances in microbiology have greatly improved the detection of bacterial pathogens in the environment. These improvements and a downward trend in the cost of molecular detection methods have contributed to increased frequency of detection of pathogenic microorganisms where traditional culture‐based detection methods have failed. Culture methods also have been greatly improved, and the confluence of the two suites of methods provides a powerful tool for detection, isolation, and characterization of pathogens. While molecular detection provides data on the presence and type of pathogens, culturing methods allow a researcher to preserve the organism of interest for “‐omics” studies, such as genomic, metabolomic, secretomic, and transcriptomic analysis, which are rapidly becoming more affordable. This has yielded a clearer understanding of the ecology and epidemiology of microorganisms that cause disease. In this unit, we present commonly accepted methods for isolation, detection, and characterization of V. cholerae, providing more extensive knowledge of the ecology and epidemiology of this organism. This unit has been fully revised and updated from the earlier version with the latest knowledge and additional information not previously included. Curr. Protoc. Microbiol. 26:6A.5.1‐6A.5.51. © 2012 by John Wiley & Sons, Inc.

Differential positioning of adherens junctions is associated with initiation of epithelial folding - Wang, Yu-Chiun; Zia Khan; Kaschube, Matthias; Wieschaus, Eric F. (Nature, 2012)
During tissue morphogenesis, simple epithelial sheets undergo folding to form complex structures. The prevailing model underlying epithelial folding involves cell shape changes driven by myosin-dependent apical constriction. Here we describe an alternative mechanism that requires differential positioning of adherens junctions controlled by modulation of epithelial apical–basal polarity. Using live embryo imaging, we show that before the initiation of dorsal transverse folds during Drosophila gastrulation, adherens junctions shift basally in the initiating cells, but maintain their original subapical positioning in the neighbouring cells. Junctional positioning in the dorsal epithelium depends on the polarity proteins Bazooka and Par-1. In particular, the basal shift that occurs in the initiating cells is associated with a progressive decrease in Par-1 levels. We show that uniform reduction of the activity of Bazooka or Par-1 results in uniform apical or lateral positioning of junctions and in each case dorsal fold initiation is abolished. In addition, an increase in the Bazooka/Par-1 ratio causes formation of ectopic dorsal folds. The basal shift of junctions not only alters the apical shape of the initiating cells, but also forces the lateral membrane of the adjacent cells to bend towards the initiating cells, thereby facilitating tissue deformation. Our data thus establish a direct link between modification of epithelial polarity and initiation of epithelial folding.
Keywords: cell biology; developmental biology

Drosophila Src regulates anisotropic apical surface growth to control epithelial tube size - Nelson, Kevin S.; Zia Khan; Molnár, Imre; Mihály, József; Kaschube, Matthias; Beitel, Greg J. (Nature Cell Biology, 2012)
Networks of epithelial and endothelial tubes are essential for the function of organs such as the lung, kidney and vascular system. The sizes and shapes of these tubes are highly regulated to match their individual functions. Defects in tube size can cause debilitating diseases such as polycystic kidney disease and ischaemia. It is therefore critical to understand how tube dimensions are regulated. Here we identify the tyrosine kinase Src as an instructive regulator of epithelial-tube length in the Drosophila tracheal system. Loss-of-function Src42 mutations shorten tracheal tubes, whereas Src42 overexpression elongates them. Surprisingly, Src42 acts distinctly from known tube-size pathways and regulates both the amount of apical surface growth and, with the conserved formin dDaam, the direction of growth. Quantitative three-dimensional image analysis reveals that Src42- and dDaam-mutant tracheal cells expand more in the circumferential than the axial dimension, resulting in tubes that are shorter in length—but larger in diameter—than wild-type tubes. Thus, Src42 and dDaam control tube dimensions by regulating the direction of anisotropic growth, a mechanism that has not previously been described.

Dynamic Searchable Symmetric Encryption - Kamara, Seny; Charalampos Papamanthou; Roeder, Tom (CCS '12 Proceedings of the 2012 ACM Conference on Computer and Communications Security, 2012)
Searchable symmetric encryption (SSE) allows a client to encrypt its data in such a way that this data can still be searched. The most immediate application of SSE is to cloud storage, where it enables a client to securely outsource its data to an untrusted cloud provider without sacrificing the ability to search over it. SSE has been the focus of active research and a multitude of schemes that achieve various levels of security and efficiency have been proposed. Any practical SSE scheme, however, should (at a minimum) satisfy the following properties: sublinear search time, security against adaptive chosen-keyword attacks, compact indexes and the ability to add and delete files efficiently. Unfortunately, none of the previously-known SSE constructions achieve all these properties at the same time. This severely limits the practical value of SSE and decreases its chance of deployment in real-world cloud storage systems. To address this, we propose the first SSE scheme to satisfy all the properties outlined above. Our construction extends the inverted index approach (Curtmola et al., CCS 2006) in several non-trivial ways and introduces new techniques for the design of SSE. In addition, we implement our scheme and conduct a performance evaluation, showing that our approach is highly efficient and ready for deployment.
Keywords: Cloud computing; cloud storage; searchable symmetric encryption

GAGE: A Critical Evaluation of Genome Assemblies and Assembly Algorithms - Salzberg,Steven L.; Phillippy,Adam M; Zimin,Aleksey; Puiu,Daniela; Magoc,Tanja; Koren,Sergey; Treangen,Todd J; Schatz,Michael C; Delcher,Arthur L.; Roberts,Michael; Marçais,Guillaume; Pop, Mihai; et al. (Genome Research, 2012)
New sequencing technology has dramatically altered the landscape of whole-genome sequencing, allowing scientists to initiate numerous projects to decode the genomes of previously unsequenced organisms. The lowest-cost technology can generate deep coverage of most species, including mammals, in just a few days. The sequence data generated by one of these projects consist of millions or billions of short DNA sequences (reads) that range from 50 to 150 nt in length. These sequences must then be assembled de novo before most genome analyses can begin. Unfortunately, genome assembly remains a very difficult problem, made more difficult by shorter reads and unreliable long-range linking information. In this study, we evaluated several of the leading de novo assembly algorithms on four different short-read data sets, all generated by Illumina sequencers. Our results describe the relative performance of the different assemblers as well as other significant differences in assembly difficulty that appear to be inherent in the genomes themselves. Three overarching conclusions are apparent: first, that data quality, rather than the assembler itself, has a dramatic effect on the quality of an assembled genome; second, that the degree of contiguity of an assembly varies enormously among different assemblers and different genomes; and third, that the correctness of an assembly also varies widely and is not well correlated with statistics on contiguity. To enable others to replicate our results, all of our data and methods are freely available, as are all assemblers used in this study.

Gene Prediction with Glimmer for Metagenomic Sequences Augmented by Classification and Clustering - Kelley,David R; Liu,Bo; Delcher,Arthur L.; Pop, Mihai; Salzberg,Steven L. (Nucleic Acids ResearchNucl. Acids Res., 2012)
Environmental shotgun sequencing (or metagenomics) is widely used to survey the communities of microbial organisms that live in many diverse ecosystems, such as the human body. Finding the protein-coding genes within the sequences is an important step for assessing the functional capacity of a metagenome. In this work, we developed a metagenomics gene prediction system Glimmer-MG that achieves significantly greater accuracy than previous systems via novel approaches to a number of important prediction subtasks. First, we introduce the use of phylogenetic classifications of the sequences to model parameterization. We also cluster the sequences, grouping together those that likely originated from the same organism. Analogous to iterative schemes that are useful for whole genomes, we retrain our models within each cluster on the initial gene predictions before making final predictions. Finally, we model both insertion/deletion and substitution sequencing errors using a different approach than previous software, allowing Glimmer-MG to change coding frame or pass through stop codons by predicting an error. In a comparison among multiple gene finding methods, Glimmer-MG makes the most sensitive and precise predictions on simulated and real metagenomes for all read lengths and error rates tested.

Global secretome analysis identifies novel mediators of bone metastasis - Blanco, Mario Andres; LeRoy, Gary; Zia Khan; Alečković, Maša; Zee, Barry M.; Garcia, Benjamin A.; Kang, Yibin (Cell Research, 2012)
Bone is the one of the most common sites of distant metastasis of solid tumors. Secreted proteins are known to influence pathological interactions between metastatic cancer cells and the bone stroma. To comprehensively profile secreted proteins associated with bone metastasis, we used quantitative and non-quantitative mass spectrometry to globally analyze the secretomes of nine cell lines of varying bone metastatic ability from multiple species and cancer types. By comparing the secretomes of parental cells and their bone metastatic derivatives, we identified the secreted proteins that were uniquely associated with bone metastasis in these cell lines. We then incorporated bioinformatic analyses of large clinical metastasis datasets to obtain a list of candidate novel bone metastasis proteins of several functional classes that were strongly associated with both clinical and experimental bone metastasis. Functional validation of selected proteins indicated that in vivo bone metastasis can be promoted by high expression of (1) the salivary cystatins CST1, CST2, and CST4; (2) the plasminogen activators PLAT and PLAU; or (3) the collagen functionality proteins PLOD2 and COL6A1. Overall, our study has uncovered several new secreted mediators of bone metastasis and therefore demonstrated that secretome analysis is a powerful method for identification of novel biomarkers and candidate therapeutic targets.
Keywords: bone; cancer; metastasis; proteomics; secretome

InterPro in 2011: new developments in the family and domain prediction database. - Hunter, Sarah; Jones, Philip; Mitchell, Alex; Apweiler, Rolf; Attwood, Teresa K; Bateman, Alex; Bernard, Thomas; Binns, David; Bork, Peer; Burge, Sarah; de Castro, Edouard; Coggill, Penny; et al. (Nucleic Acids Res, 2012)
InterPro (http://www.ebi.ac.uk/interpro/) is a database that integrates diverse information about protein families, domains and functional sites, and makes it freely available to the public via Web-based interfaces and services. Central to the database are diagnostic models, known as signatures, against which protein sequences can be searched to determine their potential function. InterPro has utility in the large-scale analysis of whole genomes and meta-genomes, as well as in characterizing individual protein sequences. Herein we give an overview of new developments in the database and its associated software since 2009, including updates to database content, curation processes and Web and programmatic interfaces.
Keywords: Databases, Protein; Protein Structure, Tertiary; Proteins; Sequence Analysis, Protein; software; Terminology as Topic; User-Computer Interface

Learning Document Structure for Retrieval and Classification - Kumar,Jayant; Ye,Peng; David Doermann (International Conference on Pattern Recognition (ICPR 2012), 2012)
In this paper, we present a method for the retrieval of document images with chosen layout characteristics. The proposed method is based on statistics of patch codewords over different regions of image. We begin with a set of wanted and a random set of unwanted images representative of a large heterogeneous collection. We then use raw-image patches extracted from the unlabeled images to learn a codebook. To model the spatial relationships between patches, the image is recursively partitioned horizontally and vertically, and a histogram of patch-codewords is computed in each partition. The resulting set of features give a high precision and recall for the retrieval of hand-drawn and machine-print table-documents, and unconstrained mixed form-type documents, when trained using a random forest classifier. We compare our method to the spatial-pyramid method, and show that the proposed approach for learning layout characteristics is competitive for document images.

Learning Text-line Segmentation using Codebooks and Graph Partitioning - Kang,Le; Kumar,Jayant; Ye,Peng; David Doermann (International Conference on Frontiers in Handwriting Recognition (ICFHR), 2012)
In this paper, we present a codebook based method for handwritten text-line segmentation which uses image patches in the training data to learn a graph-based similarity for clustering. We first construct a codebook of image-patches using K-medoids, and obtain exemplars which encode local evidence. We then obtain the corresponding codewords for all patches extracted from a given image and construct a similarity graph using the learned evidence and partitioned to obtain textlines. Our learning based approach performs well on a field dataset containing degraded and un-constrained handwritten Arabic document images. Results on ICDAR 2009 segmentation contest dataset show that the method is competitive with previous approaches.

Lithium: Event-Driven Network Control - Kim,H.; Voellmy,A.; Burnett,S.; Feamster, Nick; Clark,R. (Georgia Institute of Technology, 2012)
This paper introduces event-driven network control, a network control framework that makes networks easier to manage by automating many tasks that must currently be performed by manually modifying low-level, distributed, and complex device configuration. We identify four policy domains that inherently capture many events: time, user, history, and traffic flow. We then present Lithium, an event-driven network control framework that can implement policies expressed using these domains. Lithium can support policies that automatically react to a wide range of events, from fluctuations in traffic volumes to changes in the time of day. Lithium allows network operators to specify networkwide policies in terms of a high-level, event-driven policy model, as opposed to configuring individual network devices with low-level commands. To show that Lithium is practical, general, and applicable in different types of network scenarios, we have deployed Lithium in both a campus network and a home network and used it to implement more flexible and dynamic network policies. We also perform evaluations to show that Lithium introduces negligible overhead beyond a conventional OpenFlow-based control framework.

Local Segmentation of Touching Characters using Contour based Shape Decomposition - Kang,Le; David Doermann; Cao,Huiagu; Prasad,Rohit; Natarajan,Prem (Document Analysis Systems, 2012)
We propose a contour based shape decomposition approach that provides local segmentation of touching characters. The shape contour is linearized into edgelets and edgelets are merged into boundary fragments. Connection cost between boundary fragments is obtained by considering local smoothness, connection length and a stroke-level property Similar Stroke Rate. Samples of connections among boundary fragments are randomly generated and the one with the minimum global cost is selected to produce optimal segmentation of the shape. To obtain a binary segmentation using this approach, we make an iterative search for the parameters that yields two components on a shape. Experimental results on a number of synthetic shape images and the LTP dataset showed that this contour based shape decomposition technique is promising and it is effective on providing local segmentation of touching characters.

Mapping Parameterized Cyclo-static Dataflow Graphs onto Configurable Hardware - Kee, Hojin; Chung-Ching Shen; Bhattacharyya, Shuvra S.; Wong, Ian; Yong Rao; Kornerup, Jacob (Journal of Signal Processing Systems, 2012)
In recent years, parameterized dataflow has evolved as a useful framework for modeling synchronous and cyclo-static graphs in which arbitrary parameters can be changed dynamically. Parameterized dataflow has proven to have significant expressive power for managing dynamics of DSP applications in important ways. However, efficient hardware synthesis techniques for parameterized dataflow representations are lacking. This paper addresses this void; specifically, the paper investigates efficient field programmable gate array (FPGA)-based implementation of parameterized cyclo-static dataflow (PCSDF) graphs. We develop a scheduling technique for throughput-constrained minimization of dataflow buffering requirements when mapping PCSDF representations of DSP applications onto FPGAs. The proposed scheduling technique is integrated with an existing formal schedule model, called the generalized schedule tree, to reduce schedule cost. To demonstrate our new, hardware-oriented PCSDF scheduling technique, we have designed a real-time base station emulator prototype based on a subset of long-term evolution (LTE), which is a key cellular standard.
Keywords: 4G communication systems; Circuits and Systems; Computer Imaging, Vision, Pattern Recognition and Graphics; Dataflow modeling; Electrical Engineering; FPGA implementation; Image Processing and Computer Vision; Parameterized dataflow; pattern recognition; scheduling; Signal, Image and Speech Processing

Media, Aggregators and the Link Economy: Strategic Hyperlink Formation in Content Networks - Dellarocas, Chris; Katona,Zsolt; Rand, William (Management Science, 2012)
A key property of the World Wide Web is the possibility for firms to place virtually costless links to third-party content as a substitute or complement to their own content. This ability to hyperlink has enabled new types of players, such as search engines and content aggregators, to successfully enter content ecosystems, attracting traffic and revenues by hosting links to the content of others. This, in turn, has sparked a heated controversy between content producers and aggregators regarding the legitimacy and social costs/benefits of uninhibited free linking. This work is the first to model the implications of interrelated and strategic hyper-linking and content investments. Our results provide a nuanced view of the much-touted “link economy,” highlighting both the beneficial consequences and the drawbacks of free hyperlinks for content producers and consumers. We show that content sites can reduce competition and improve profits by forming links to each other; in such networks one site makes high investments in content and other sites link to it. Interestingly, competitive dynamics often preclude the formation of link networks, even in settings where they would improve everyone’s profits. Furthermore, such networks improve economic efficiency only when all members have similar abilities to produce content; otherwise the less capable nodes can free-ride on the content of the more capable nodes, reducing profits for the capable nodes as well as the average content quality available to consumers. Within these networks, aggregators have both positive and negative effects. By making it easier for consumers to access good quality content they increase the appeal of the entire content ecosystem relative to the alternatives. To the extent that this increases the total traffic flowing into the content ecosystem, aggregators can help increase the profits of the highest quality content sites. At the same time, however, the market entry of aggregators takes away some of the revenue that would otherwise go to content sites. Finally, by placing links to only a subset of available content, aggregators further increase competitive pressure on content sites. Interestingly, this can increase the likelihood that such sites will then attempt to alleviate the competitive pressure by forming link networks.

Mobile Data Offloading through Opportunistic Communications and Social Participation - Han,Bo; Hui,Pan; Kumar,V. S.A; Marathe,M. V; Shao,Jianhua; Srinivasan, Aravind (Mobile Computing, IEEE Transactions on, 2012)
3G networks are currently overloaded, due to the increasing popularity of various applications for smartphones. Offloading mobile data traffic through opportunistic communications is a promising solution to partially solve this problem, because there is almost no monetary cost for it. We propose to exploit opportunistic communications to facilitate information dissemination in the emerging Mobile Social Networks (MoSoNets) and thus reduce the amount of mobile data traffic. As a case study, we investigate the target-set selection problem for information delivery. In particular, we study how to select the target set with only k users, such that we can minimize the mobile data traffic over cellular networks. We propose three algorithms, called Greedy, Heuristic, and Random, for this problem and evaluate their performance through an extensive trace-driven simulation study. Our simulation results verify the efficiency of these algorithms for both synthetic and real-world mobility traces. For example, the Heuristic algorithm can offload mobile data traffic by up to 73.66 percent for a real-world mobility trace. Moreover, to investigate the feasibility of opportunistic communications for mobile phones, we implement a proof-of-concept prototype, called Opp-off, on Nokia N900 smartphones, which utilizes their Bluetooth interface for device/service discovery and content transfer.
Keywords: 3G mobile communication; 3G networks; Bluetooth interface; cellular networks; cellular radio; content transfer; device/service discovery; graph theory; greedy algorithm; heuristic algorithm; information delivery; information dissemination; mobile data offloading; mobile data traffic; mobile phones; mobile social networks; MoSoNets; Nokia N900 smartphones; Opp-off; opportunistic communications; random algorithm; real-world mobility traces; smart phones; social networking (online); social participation; target-set selection problem; telecommunication network routing; Telecommunication traffic; trace-driven simulation study

Optimizing epidemic protection for socially essential workers - Barrett,Chris; Beckman,Richard; Bisset,Keith; Chen,Jiangzhuo; DuBois,Thomas; Eubank,Stephen; Kumar,V. S. Anil; Lewis,Bryan; Marathe,Madhav V.; Srinivasan, Aravind; Stretz,Paula E. (Proceedings of the 2nd ACM SIGHIT International Health Informatics Symposium, 2012)
Public-health policy makers have many tools to mitigate an epidemic's effects. Most related research focuses on the direct effects on those infected (in terms of health, life, or productivity). Interventions including treatment, prophylaxis, quarantine, and social distancing are well studied in this context. These interventions do not address indirect effects due to the loss of critical services and infrastructures when too many of those responsible for their day-to-day operations fall ill. We examine, both analytically and through simulation, the protection of such essential subpopulations by sequestering them, effectively isolating them into groups during an epidemic. We develop a framework for studying the benefits of sequestering and heuristics for when to sequester. We also prove a key property of sequestering placement which helps partition the subpopulations optimally. Thus we provide a first step toward determining how to allocate resources between the direct protection of a population, and protection of those responsible for critical services.
Keywords: epidemiology; OPTIMIZATION; public health informatics

Quantitative measurement of allele‐specific protein expression in a diploid yeast hybrid by LC‐MS - Zia Khan; Bloom, Joshua S.; Amini, Sasan; Singh, Mona; Perlman, David H.; Caudy, Amy A.; Kruglyak, Leonid (Molecular Systems Biology, 2012)
Understanding the genetic basis of gene regulatory variation is a key goal of evolutionary and medical genetics. Regulatory variation can act in an allele‐specific manner (cis‐acting) or it can affect both alleles of a gene (trans‐acting). Differential allele‐specific expression (ASE), in which the expression of one allele differs from another in a diploid, implies the presence of cis‐acting regulatory variation. While microarrays and high‐throughput sequencing have enabled genome‐wide measurements of transcriptional ASE, methods for measurement of protein ASE (pASE) have lagged far behind. We describe a flexible, accurate, and scalable strategy for measurement of pASE by liquid chromatography‐coupled mass spectrometry (LC‐MS). We apply this approach to a hybrid between the yeast species Saccharomyces cerevisiae and Saccharomyces bayanus. Our results provide the first analysis of the relative contribution of cis‐acting and trans‐acting regulatory differences to protein expression divergence between yeast species.Synopsis A novel strategy for the quantitative measurement of allele‐specific protein expression is used to infer the contributions of cis‐ and trans‐acting factors influencing the divergence of protein levels between yeast species. Rigorous experimental controls and analyses confirm the accuracy of the new strategy for the quantitative measurement of allele‐specific protein expression by high‐throughput mass spectrometry.Analysis of allele‐specific protein expression in an interspecies yeast hybrid and protein expression differences between species reveals that both cis‐effects and trans‐effects contribute to protein expression divergence between two yeast species, Saccharomyces cerevisiae and Saccharomyces bayanus.
Keywords: allele specific; divergence; mass spectrometry; protein expression; proteomics

Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution - Huang,Y.; Katz, Jonathan; Evans,D. (IEEE Symposium on Security and Privacy, 2012)
Known protocols for secure two-party computa-tion that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party’s input. Correctness of the honest party’s output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some heuristic enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing stronger security guarantees.

Review of efficient secure two-party protocols: techniques and constructions by Carmit Hazay and Yehuda Lindell - Katz, Jonathan (SIGACT News, 2012)

Re-wiring Activity of Malicious Networks - Konte,Maria; Feamster, Nick (Passive and Active MeasurementPassive and Active Measurement, 2012)
This paper studies the AS-level re-wiring dynamics (changes in the connectivity) of malicious networks. Anecdotal evidence suggests that some malicious ASes that are primarily involved in nefarious activities on the Internet, were sequentially de-peered by providers before their final cut-off (as occurred in the well-publicized cases of Atrivo/Intercage). We present the first systematic study of the re-wiring dynamics of malicious ASes. We tracked the ASes that were listed by Hostexploit over the last two years and compared their AS-level re-wiring dynamics with non-reported ASes. Using a publicly available dataset of Customer-Provider (CP) relations in the Internet’s AS graph, we studied how interconnection between autonomous systems evolves, both for ASes that provide connectivity for attackers and ASes that were not reported as malicious. We find that malicious networks are more aggressive both in forming links with providers and changing their upstream connectivity than other ASes. Our results indicate that the re-wiring dynamics of the networks that host attacks are stable over time, despite the evolving nature of the attacks themselves, which suggests that existing defense mechanisms could benefit from incorporating these features.
Keywords: Computer science

Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces - Choi,S.; Hwang,K.W.; Katz, Jonathan; Malkin,T.; Rubenstein,D. (Topics in Cryptology–CT-RSA 2012, 2012)
Protocols for generic secure multi-party computation (MPC) generally come in two forms: they either represent the function being computed as a boolean circuit, or as an arithmetic circuit over a large field. Either type of protocol can be used for any function, but the choice of which protocol to use can have a significant impact on efficiency. The magnitude of the effect, however, has never been quantified.With this in mind, we implement the MPC protocol of Goldreich, Micali, and Wigderson [13], which uses a boolean representation and is secure against a semi-honest adversary corrupting any number of parties. We then consider applications of secure MPC in on-line marketplaces, where customers select resources advertised by providers and it is desired to ensure privacy to the extent possible. Problems here are more naturally formulated in terms of boolean circuits, and we study the performance of our MPC implementation relative to existing ones that use an arithmetic-circuit representation. Our protocol easily handles tens of customers/providers and thousands of resources, and outperforms existing implementations including FairplayMP [3], VIFF [11], and SEPIA [7].

Securing Circuits against Constant-Rate Tampering - Dana Dachman-Soled; Kalai, Yael Tauman (Advances in Cryptology – CRYPTO 2012, 2012)
We present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et. al. (Eurocrypt 2006), we consider adversaries who may choose an arbitrary set of wires to corrupt, and may set each such wire to 0 or to 1, or may toggle with the wire. We prove that such adversaries, who continuously tamper with the circuit, can learn at most logarithmically many bits of secret information (in addition to black-box access to the circuit). Our results are information theoretic.
Keywords: circuit compiler; Computer Communication Networks; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; PCP of proximity; side-channel attacks; Systems and Data Security; tampering

Sharpness Estimation for Document and Scene Images - Kumar,Jayant; Chen, Francine; David Doermann (International Conference on Pattern Recognition (ICPR 2012), 2012)
Images of document pages have different characteristics than images of natural scenes, and so the sharpness measures developed for natural scene images do not necessarily extend to document images primarily composed of text. We present an efficient and simple method for effectively estimating the sharpness/ blurriness of document images that also performs well on natural scenes. Our method can be used to predict the sharpness in scenarios where images are blurred due to camera-motion (or hand-shake), defocus, or inherent properties of the imaging system. The proposed method outperforms the perceptually-based, no-reference sharpness work of [1] and [4], which was shown to perform better than 14 other no-reference sharpness measures on the LIVE dataset.

Structure, function and diversity of the healthy human microbiome - Huttenhower, C.; Gevers, D.; Knight,R.; Abubucker, S.; Badger, J.H.; Chinwalla, A.T.; Creasy, H.H.; Earl, A.M.; Fitzgerald, M.G.; Fulton, R.S.; others (Nature, 2012)
Studies of the human microbiome have revealed that even healthy individuals differ remarkably in the microbes that occupy habitats such as the gut, skin and vagina. Much of this diversity remains unexplained, although diet, environment, host genetics and early microbial exposure have all been implicated. Accordingly, to characterize the ecology of human-associated microbial communities, the Human Microbiome Project has analysed the largest cohort and set of distinct, clinically relevant body habitats so far. We found the diversity and abundance of each habitat’s signature microbes to vary widely even among healthy subjects, with strong niche specialization both within and among individuals. The project encountered an estimated 81–99% of the genera, enzyme families and community configurations occupied by the healthy Western microbiome. Metagenomic carriage of metabolic pathways was stable among individuals despite variation in community structure, and ethnic/racial background proved to be one of the strongest associations of both pathways and microbes with clinical metadata. These results thus delineate the range of structural and functional configurations normal in the microbial communities of a healthy population, enabling future characterization of the epidemiology, ecology and translational applications of the human microbiome.

Two-server password-only authenticated key exchange - Katz, Jonathan; MacKenzie,Philip; Taban,Gelareh; Gligor,Virgil (Journal of Computer and System Sciences, 2012)
Typical protocols for password-based authentication assume a single server that stores all the information (e.g., the password) necessary to authenticate a user. An inherent limitation of this approach, assuming low-entropy passwords are used, is that the userʼs password is exposed if this server is ever compromised. To address this issue, it has been suggested to share a userʼs password information among multiple servers, and to have these servers cooperate (possibly in a threshold manner) when the user wants to authenticate. We show here a two-server version of the password-only key-exchange protocol of Katz, Ostrovsky, and Yung (the KOY protocol). Our work gives the first secure two-server protocol for the password-only setting (in which the user need remember only a password, and not the serversʼ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model. Our work thus fills a gap left by the work of MacKenzie et al. (2006) [31] and Di Raimondo and Gennaro (2006) [16]. As an additional benefit of our work, we show modifications that improve the efficiency of the original KOY protocol.
Keywords: Key-exchange protocols; passwords

Unsupervised Feature Learning Framework for No-reference Image Quality Assessment - Ye,Peng; Kumar,Jayant; Kang,Le; David Doermann (CVPR, 2012)
In this paper, we present an efficient general-purpose objective no-reference (NR) image quality assessment (IQA) framework based on unsupervised feature learning. The goal is to build a computational model to automatically predict human perceived image quality without a reference image and without knowing the distortion present in the image. Previous approaches for this problem typically rely on hand-crafted features which are carefully designed based on prior knowledge. In contrast, we use raw-image-patches extracted from a set of unlabeled images to learn a dictionary in an unsupervised manner. We use soft-assignment coding with max pooling to obtain effective image representations for quality estimation. The proposed algorithm is very computationally appealing, using raw image patches as local descriptors and using soft-assignment for encoding. Furthermore, unlike previous methods, our unsupervised feature learning strategy enables our method to adapt to different domains. CORNIA (Codebook Representation for No-Reference Image Assessment) was tested on LIVE database and shown to perform statistically better than full-reference quality measure structural similarity index (SSIM) and was shown to be comparable to state-of-the-art general purpose NR-IQA algorithms.

Which Languages Have 4-Round Zero-Knowledge Proofs? - Katz, Jonathan (Journal of cryptology, 2012)
We show that if a language L has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then . Assuming the polynomial hierarchy does not collapse, this means in particular that NP-complete languages do not have 4-round zero-knowledge proofs with black-box simulation.

Ability-based design: Concept, principles and examples - Wobbrock,J.O.; Kane,S.K.; Gajos,K.Z.; Harada,S.; Jon Froehlich (ACM Transactions on Accessible Computing (TACCESS), 2011)

Accurate proteome-wide protein quantification from high-resolution 15N mass spectra - Zia Khan; Amini, Sasan; Bloom, Joshua S.; Ruse, Cristian; Caudy, Amy A.; Kruglyak, Leonid; Singh, Mona; Perlman, David H.; Tavazoie, Saeed (Genome Biology, 2011)
In quantitative mass spectrometry-based proteomics, the metabolic incorporation of a single source of 15N-labeled nitrogen has many advantages over using stable isotope-labeled amino acids. However, the lack of a robust computational framework for analyzing the resulting spectra has impeded wide use of this approach. We have addressed this challenge by introducing a new computational methodology for analyzing 15N spectra in which quantification is integrated with identification. Application of this method to an Escherichia coli growth transition reveals significant improvement in quantification accuracy over previous methods.PMID: 22182234

On Achieving the" Best of Both Worlds" in Secure Multiparty Computation - Ishai,Y.; Katz, Jonathan; Kushilevitz,E.; Lindell,Y.; Petrank,E. (SIAM Journal on Computing, 2011)
Two settings are traditionally considered for secure multiparty computation, de-pending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

Adaptively secure broadcast, revisited - Garay,J. A; Katz, Jonathan; Kumaresan,R.; Zhou,H.S. (Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011)
We consider the classical problem of synchronous broadcast with dishonest majority, whena public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes- simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num- ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine.

Analysis of SystemC actor networks for efficient synthesis - Falk, Joachim; Zebelein, Christian; Keinert, Joachim; Haubelt, Christian; Teich, Juergen; Bhattacharyya, Shuvra S. (ACM Trans. Embed. Comput. Syst., 2011)
Applications in the signal processing domain are often modeled by dataflow graphs. Due to heterogeneous complexity requirements, these graphs contain both dynamic and static dataflow actors. In previous work, we presented a generalized clustering approach for these heterogeneous dataflow graphs in the presence of unbounded buffers. This clustering approach allows the application of static scheduling methodologies for static parts of an application during embedded software generation for multiprocessor systems. It systematically exploits the predictability and efficiency of the static dataflow model to obtain latency and throughput improvements. In this article, we present a generalization of this clustering technique to dataflow graphs with bounded buffers, therefore enabling synthesis for embedded systems without dynamic memory allocation. Furthermore, a case study is given to demonstrate the performance benefits of the approach.
Keywords: actor-oriented design; clustering; Dataflow analysis; scheduling

Applying graphics processor acceleration in a software defined radio prototyping environment - Plishker,W.; Zaki, G.F.; Bhattacharyya, Shuvra S.; Clancy, C.; Kuykendall, J. (2011 22nd IEEE International Symposium on Rapid System Prototyping (RSP), 2011)
With higher bandwidth requirements and more complex protocols, software defined radio (SDR) has ever growing computational demands. SDR applications have different levels of parallelism that can be exploited on multicore platforms, but design and programming difficulties have inhibited the adoption of specialized multicore platforms like graphics processors (GPUs). In this work we propose a new design flow that augments a popular existing SDR development environment (GNU Radio), with a dataflow foundation and a stand-alone GPU accelerated library. The approach gives an SDR developer the ability to prototype a GPU accelerated application and explore its design space fast and effectively. We demonstrate this design flow on a standard SDR benchmark and show that deciding how to utilize a GPU can be non-trivial for even relatively simple applications.
Keywords: Acceleration; coprocessors; dataflow foundation; GNU radio; Graphics processing unit; graphics processor acceleration; Kernel; Libraries; multicore platforms; Multicore processing; PARALLEL PROCESSING; Pipelines; Protocols; software defined radio prototyping environment; software radio; stand-alone GPU accelerated library

Architecting for innovation - Koponen,Teemu; Shenker,Scott; Balakrishnan,Hari; Feamster, Nick; Ganichev,Igor; Ghodsi,Ali; Godfrey,P. Brighten; McKeown,Nick; Parulkar,Guru; Raghavan,Barath; Rexford,Jennifer; Arianfar,Somaya; et al. (SIGCOMM Comput. Commun. Rev., 2011)
We argue that the biggest problem with the current Internet architecture is not a particular functional deficiency, but its inability to accommodate innovation. To address this problem we propose a minimal architectural "framework" in which comprehensive architectures can reside. The proposed Framework for Internet Innovation (FII) --- which is derived from the simple observation that network interfaces should be extensible and abstract --- allows for a diversity of architectures to coexist, communicate, and evolve. We demonstrate FII's ability to accommodate diversity and evolution with a detailed examination of how information flows through the architecture and with a skeleton implementation of the relevant interfaces.
Keywords: diversity; Evolution; innovation; internet architecture

Assessing the benefits of using mate-pairs to resolve repeats in de novo short-read prokaryotic assemblies - Wetzel,Joshua; Kingsford, Carl; Pop, Mihai (BMC Bioinformatics, 2011)
Next-generation sequencing technologies allow genomes to be sequenced more quickly and less expensively than ever before. However, as sequencing technology has improved, the difficulty of de novo genome assembly has increased, due in large part to the shorter reads generated by the new technologies. The use of mated sequences (referred to as mate-pairs) is a standard means of disambiguating assemblies to obtain a more complete picture of the genome without resorting to manual finishing. Here, we examine the effectiveness of mate-pair information in resolving repeated sequences in the DNA (a paramount issue to overcome). While it has been empirically accepted that mate-pairs improve assemblies, and a variety of assemblers use mate-pairs in the context of repeat resolution, the effectiveness of mate-pairs in this context has not been systematically evaluated in previous literature.

Bacillus Anthracis Comparative Genome Analysis in Support of the Amerithrax Investigation - Rasko,David A; Worsham,Patricia L; Abshire,Terry G; Stanley,Scott T; Bannan,Jason D; Wilson,Mark R; Langham,Richard J; Decker,R. Scott; Jiang,Lingxia; Read,Timothy D.; Phillippy,Adam M; Salzberg,Steven L.; et al. (Proceedings of the National Academy of SciencesPNAS, 2011)
Before the anthrax letter attacks of 2001, the developing field of microbial forensics relied on microbial genotyping schemes based on a small portion of a genome sequence. Amerithrax, the investigation into the anthrax letter attacks, applied high-resolution whole-genome sequencing and comparative genomics to identify key genetic features of the letters’ Bacillus anthracis Ames strain. During systematic microbiological analysis of the spore material from the letters, we identified a number of morphological variants based on phenotypic characteristics and the ability to sporulate. The genomes of these morphological variants were sequenced and compared with that of the B. anthracis Ames ancestor, the progenitor of all B. anthracis Ames strains. Through comparative genomics, we identified four distinct loci with verifiable genetic mutations. Three of the four mutations could be directly linked to sporulation pathways in B. anthracis and more specifically to the regulation of the phosphorylation state of Spo0F, a key regulatory protein in the initiation of the sporulation cascade, thus linking phenotype to genotype. None of these variant genotypes were identified in single-colony environmental B. anthracis Ames isolates associated with the investigation. These genotypes were identified only in B. anthracis morphotypes isolated from the letters, indicating that the variants were not prevalent in the environment, not even the environments associated with the investigation. This study demonstrates the forensic value of systematic microbiological analysis combined with whole-genome sequencing and comparative genomics.

Bambus 2: scaffolding metagenomes - Koren, S.; Treangen, T.J.; Pop, Mihai (Bioinformatics, 2011)

Believe Me—We Can Do This! Annotating Persuasive Acts in Blog Text - Anand,P.; King,J.; Jordan Boyd-Graber; Wagner,E.; Martell,C.; Oard, Douglas; Resnik, Philip (Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011)

Blurring-invariant Riemannian metrics for comparing signals and images - Zhengwu Zhang; Klassen, E.; Srivastava, A.; Turaga,P.; Chellapa, Rama (2011 IEEE International Conference on Computer Vision (ICCV), 2011)
We propose a novel Riemannian framework for comparing signals and images in a manner that is invariant to their levels of blur. This framework uses a log-Fourier representation of signals/images in which the set of all possible Gaussian blurs of a signal, i.e. its orbits under semigroup action of Gaussian blur functions, is a straight line. Using a set of Riemannian metrics under which the group actions are by isometries, the orbits are compared via distances between orbits. We demonstrate this framework using a number of experimental results involving 1D signals and 2D images.
Keywords: blurring-invariant Riemannian metrics; Estimation; Fourier transforms; Gaussian blur function; Gaussian processes; image representation; log-Fourier representation; measurement; Orbits; Polynomials; signal representation; Space vehicles; vectors

Can Deliberately Incomplete Gene Sample Augmentation Improve a Phylogeny Estimate for the Advanced Moths and Butterflies (Hexapoda: Lepidoptera)? - Cho,Soowon; Zwick,Andreas; Regier,Jerome C; Mitter,Charles; Cummings, Michael P.; Yao,Jianxiu; Du,Zaile; Zhao,Hong; Kawahara,Akito Y; Weller,Susan; Davis,Donald R; Baixeras,Joaquin; et al. (Systematic BiologySyst Biol, 2011)
This paper addresses the question of whether one can economically improve the robustness of a molecular phylogeny estimate by increasing gene sampling in only a subset of taxa, without having the analysis invalidated by artifacts arising from large blocks of missing data. Our case study stems from an ongoing effort to resolve poorly understood deeper relationships in the large clade Ditrysia ( > 150,000 species) of the insect order Lepidoptera (butterflies and moths). Seeking to remedy the overall weak support for deeper divergences in an initial study based on five nuclear genes (6.6 kb) in 123 exemplars, we nearly tripled the total gene sample (to 26 genes, 18.4 kb) but only in a third (41) of the taxa. The resulting partially augmented data matrix (45% intentionally missing data) consistently increased bootstrap support for groupings previously identified in the five-gene (nearly) complete matrix, while introducing no contradictory groupings of the kind that missing data have been predicted to produce. Our results add to growing evidence that data sets differing substantially in gene and taxon sampling can often be safely and profitably combined. The strongest overall support for nodes above the family level came from including all nucleotide changes, while partitioning sites into sets undergoing mostly nonsynonymous versus mostly synonymous change. In contrast, support for the deepest node for which any persuasive molecular evidence has yet emerged (78–85% bootstrap) was weak or nonexistent unless synonymous change was entirely excluded, a result plausibly attributed to compositional heterogeneity. This node (Gelechioidea + Apoditrysia), tentatively proposed by previous authors on the basis of four morphological synapomorphies, is the first major subset of ditrysian superfamilies to receive strong statistical support in any phylogenetic study. A “more-genes-only” data set (41 taxa×26 genes) also gave strong signal for a second deep grouping (Macrolepidoptera) that was obscured, but not strongly contradicted, in more taxon-rich analyses.
Keywords: Ditrysia; gene sampling; Hexapoda; Lepidoptera; missing data; molecular phylogenetics; nuclear genes; taxon sampling

A case for query by image and text content: searching computer help using screenshots and keywords - Tom Yeh; White,Brandyn; San Pedro,Jose; Katz,Boriz; Davis, Larry S. (Proceedings of the 20th international conference on World wide web, 2011)
The multimedia information retrieval community has dedicated extensive research effort to the problem of content-based image retrieval (CBIR). However, these systems find their main limitation in the difficulty of creating pictorial queries. As a result, few systems offer the option of querying by visual examples, and rely on automatic concept detection and tagging techniques to provide support for searching visual content using textual queries.This paper proposes and studies a practical multimodal web search scenario, where CBIR fits intuitively to improve the retrieval of rich information queries. Many online articles contain useful know-how knowledge about computer applications. These articles tend to be richly illustrated by screenshots. We present a system to search for such software know-how articles that leverages the visual correspondences between screenshots. Users can naturally create pictorial queries simply by taking a screenshot of the application to retrieve a list of articles containing a matching screenshot. We build a prototype comprising 150k articles that are classified into walkthrough, book, gallery, and general categories, and provide a comprehensive evaluation of this system, focusing on technical (accuracy of CBIR techniques) and usability (perceived system usefulness) aspects. We also consider the study of added value features of such a visual-supported search, including the ability to perform cross-lingual queries. We find that the system is able to retrieve matching screenshots for a wide variety of programs, across language boundaries, and provide subjectively more useful results than keyword-based web and image search engines.
Keywords: content-based image retrieval; multimodal search; online help

A case for query by image and text content: searching computer help using screenshots and keywords - Tom Yeh; White,Brandyn; San Pedro,Jose; Katz,Boriz; Davis, Larry S. (Proceedings of the 20th international conference on World wide web, 2011)
The multimedia information retrieval community has dedicated extensive research effort to the problem of content-based image retrieval (CBIR). However, these systems find their main limitation in the difficulty of creating pictorial queries. As a result, few systems offer the option of querying by visual examples, and rely on automatic concept detection and tagging techniques to provide support for searching visual content using textual queries. This paper proposes and studies a practical multimodal web search scenario, where CBIR fits intuitively to improve the retrieval of rich information queries. Many online articles contain useful know-how knowledge about computer applications. These articles tend to be richly illustrated by screenshots. We present a system to search for such software know-how articles that leverages the visual correspondences between screenshots. Users can naturally create pictorial queries simply by taking a screenshot of the application to retrieve a list of articles containing a matching screenshot. We build a prototype comprising 150k articles that are classified into walkthrough, book, gallery, and general categories, and provide a comprehensive evaluation of this system, focusing on technical (accuracy of CBIR techniques) and usability (perceived system usefulness) aspects. We also consider the study of added value features of such a visual-supported search, including the ability to perform cross-lingual queries. We find that the system is able to retrieve matching screenshots for a wide variety of programs, across language boundaries, and provide subjectively more useful results than keyword-based web and image search engines.
Keywords: content-based image retrieval; multimodal search; online help

CHI 2011 sustainability community invited panel: challenges ahead - Khan,Azam; Bartram,Lyn; Blevis,Eli; DiSalvo,Carl; Jon Froehlich; Kurtenbach,Gordon (2011 annual conference extended abstracts on Human factors in computing systems, 2011)
As part of a new CHI Sustainability Community, focused on environmental sustainability, this panel will discuss specific ways in which HCI research will be critical in finding solutions to this global challenge. While research to date has primarily focused on the end consumer, the panel will be challenged with enlarging the discussion to include the designer as a target user and to consider interfaces and interactions that support sustainable design and sustainable manufacturing, as well as sustainable consumption. Specifically, to make real progress, we seek to enumerate ways that HCI needs to grow, as well as to find ways that can help more HCI researchers to become involved.
Keywords: design; Environment; sustainability; community; user behavior

Clonal transmission, dual peak, and off-season cholera in Bangladesh - Alam,M.; Islam,A.; Bhuiyan,N. A.; Rahim,N.; Hossain,A.; Khan,G. Y.; Ahmed,D.; Watanabe,H.; Izumiya,H.; Faruque,A. S. G.; Rita R Colwell (Infection Ecology & Epidemiology, 2011)
Vibrio cholerae is an estuarine bacterium associated with a single peak of cholera (March–May) in coastal villages of Bangladesh. For an unknown reason, however, cholera occurs in a unique dual peak (March–May and September–November) pattern in the city of Dhaka that is bordered by a heavily polluted freshwater river system and flood embankment. In August 2007, extreme flooding was accompanied by an unusually severe diarrhea outbreak in Dhaka that resulted in a record high illness. This study was aimed to understand the unusual outbreak and if it was related to the circulation of a new V. cholerae clone. Nineteen V. cholerae isolated during the peak of the 2007 outbreak were subjected to extensive phenotypic and molecular analyses, including multi-locus genetic screening by polymerase chain reaction (PCR), sequence-typing of the ctxB gene, and pulsed-field gel electrophoresis (PFGE). Factors associated with the unusual incidence of cholera were determined and analysis of the disease severity was done. Overall, microbiological and molecular data confirmed that the hypervirulent V. cholerae was O1 biotype El Tor (ET) that possessed cholera toxin (CT) of the classical biotype. The PFGE (NotI) and dendrogram clustering confirmed that the strains were clonal and related to the pre-2007 variant ET from Dhaka and Matlab and resembled one of two distinct clones of the variant ET confirmed to be present in the estuarine ecosystem of Bangladesh. Results of the analyses of both diarrheal case data for three consecutive years (2006–2008) and regional hydroclimatology over three decades (1980–2009) clearly indicate that the pattern of cholera occurring in Dhaka, and not seen at other endemic sites, was associated with flood waters transmitting the infectious clone circulating via the fecal-oral route during and between the dual seasonal cholera peaks in Dhaka. Circular river systems and flood embankment likely facilitate transmission of infectious V. cholerae throughout the year that leads to both sudden and off-season outbreaks in the densely populated urban ecosystem of Dhaka. Clonal recycling of hybrid El Tor with increasing virulence in a changing climate and in a region with a growing urban population represents a serious public health concern for Bangladesh.

Collective graph identification - Namata,Galileo Mark; Kok,Stanley; Getoor, Lise (Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011)
Data describing networks (communication networks, transaction networks, disease transmission networks, collaboration networks, etc.) is becoming increasingly ubiquitous. While this observational data is useful, it often only hints at the actual underlying social or technological structures which give rise to the interactions. For example, an email communication network provides useful insight but is not the same as the "real" social network among individuals. In this paper, we introduce the problem of graph identification, i.e., the discovery of the true graph structure underlying an observed network. We cast the problem as a probabilistic inference task, in which we must infer the nodes, edges, and node labels of a hidden graph, based on evidence provided by the observed network. This in turn corresponds to the problems of performing entity resolution, link prediction, and node labeling to infer the hidden graph. While each of these problems have been studied separately, they have never been considered together as a coherent task. We present a simple yet novel approach to address all three problems simultaneously. Our approach, called C3, consists of Coupled Collective Classifiers that are iteratively applied to propagate information among solutions to the problems. We empirically demonstrate that C3 is superior, in terms of both predictive accuracy and runtime, to state-of-the-art probabilistic approaches on three real-world problems.
Keywords: collective classification; entity resolution; link prediction; semi-supervised learning

Communicating with Caps: Managing Usage Caps in Home Networks - Kim, Hyojoon; Sundaresan, Srikanth; Marshini Chetty; Feamster, Nick; Edwards, W. Keith (SIGCOMM Comput. Commun. Rev., 2011)
As Internet service providers increasingly implement and impose "usage caps", consumers need better ways to help them understand and control how devices in the home use up the available network resources or available capacity. Towards this goal, we will demonstrate a system that allows users to monitor and manage their usage caps. The system uses the BISMark firmware running on network gateways to collect usage statistics and report them to a logically centralized controller, which displays usage information. The controller allows users to specify policies about how different people, devices, and applications should consume the usage cap; it implements and enforces these policies via a secure OpenFlow control channel to each gateway device. The demonstration will show various use cases, such as limiting the usage of a particular application, visualizing usage statistics, and allowing users within a single household to "trade" caps with one another.
Keywords: home network; openflow; usage cap

Communicating with caps: managing usage caps in home networks - Kim,Hyojoon; Sundaresan,Srikanth; Marshini Chetty; Feamster, Nick; Edwards,W. Keith (ACM SIGCOMM Computer Communication Review, 2011)
As Internet service providers increasingly implement and impose "usage caps", consumers need better ways to help them understand and control how devices in the home use up the available network resources or available capacity. Towards this goal, we will demonstrate a system that allows users to monitor and manage their usage caps. The system uses the BISMark firmware running on network gateways to collect usage statistics and report them to a logically centralized controller, which displays usage information. The controller allows users to specify policies about how different people, devices, and applications should consume the usage cap; it implements and enforces these policies via a secure OpenFlow control channel to each gateway device. The demonstration will show various use cases, such as limiting the usage of a particular application, visualizing usage statistics, and allowing users within a single household to "trade" caps with one another.
Keywords: home network; openflow; usage cap

Complete Fairness in Secure Two-Party Computation - Gordon,S. Dov; Hazay,Carmit; Katz, Jonathan; Lindell,Yehuda (Journal of the ACM, 2011)
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.
Keywords: cryptography; fairness; secure computation

A computational statistics approach for estimating the spatial range of morphogen gradients - Kanodia, Jitendra S.; Kim, Yoosik; Tomer, Raju; Zia Khan; Chung, Kwanghun; Storey, John D.; Lu, Hang; Keller, Philipp J.; Shvartsman, Stanislav Y. (Development, 2011)
A crucial issue in studies of morphogen gradients relates to their range: the distance over which they can act as direct regulators of cell signaling, gene expression and cell differentiation. To address this, we present a straightforward statistical framework that can be used in multiple developmental systems. We illustrate the developed approach by providing a point estimate and confidence interval for the spatial range of the graded distribution of nuclear Dorsal, a transcription factor that controls the dorsoventral pattern of the Drosophila embryo.
Keywords: Computational Biology; Confidence interval; Dorsal gradient; Drosophila embryo; Morphogen gradient; Statistics

Constant-Round Private Function Evaluation with Linear Complexity - Katz, Jonathan; Malka,L. (Advances in Cryptology–ASIACRYPT 2011, 2011)
We consider the problem of private function evaluation (PFE) in the two-party setting. Here, informally, one party holds an input x while the other holds a (circuit describing a) function f; the goal is for one (or both) of the parties to learn f(x) while revealing nothing more to either party. In contrast to the usual setting of secure computation, where the function being computed is known to both parties, PFE is useful in settings where the function (i.e., algorithm) itself must remain secret, e.g., because it is proprietary or classified.It is known that PFE can be reduced to standard secure computation by having the parties evaluate a universal circuit, and this is the approach taken in most prior work. Using a universal circuit, however, introduces additional overhead and results in a more complex implementation. We show here a completely new technique for PFE that avoids universal circuits, and results in constant-round protocols with communication/computational complexity linear in the size of the circuit computing f. This gives the first constant-round protocol for PFE with linear complexity (without using fully homomorphic encryption), even restricted to semi-honest adversaries.

A cost-aggregating integer linear program for motif finding - Kingsford, Carl; Zaslavsky,Elena; Singh,Mona (Journal of Discrete Algorithms, 2011)
In the motif finding problem one seeks a set of mutually similar substrings within a collection of biological sequences. This is an important and widely-studied problem, as such shared motifs in DNA often correspond to regulatory elements. We study a combinatorial framework where the goal is to find substrings of a given length such that the sum of their pairwise distances is minimized. We describe a novel integer linear program for the problem, which uses the fact that distances between substrings come from a limited set of possibilities allowing for aggregate consideration of sequence position pairs with the same distances. We show how to tighten its linear programming relaxation by adding an exponential set of constraints and give an efficient separation algorithm that can find violated constraints, thereby showing that the tightened linear program can still be solved in polynomial time. We apply our approach to find optimal solutions for the motif finding problem and show that it is effective in practice in uncovering known transcription factor binding sites.
Keywords: Computational Biology; Integer linear programming; Sequence motif finding

Decentralized, accurate, and low-cost network bandwidth prediction - Sukhyun Song; Keleher,P.; Bhattacharjee, Bobby; Sussman, Alan (2011 Proceedings IEEE INFOCOM, 2011)
The distributed nature of modern computing makes end-to-end prediction of network bandwidth increasingly important. Our work is inspired by prior work that treats the Internet and bandwidth as an approximate tree metric space. This paper presents a decentralized, accurate, and low cost system that predicts pairwise bandwidth between hosts. We describe an algorithm to construct a distributed tree that embeds bandwidth measurements. The correctness of the algorithm is provable when driven by precise measurements. We then describe three novel heuristics that achieve high accuracy for predicting bandwidth even with imprecise input data. Simulation experiments with a real-world dataset confirm that our approach shows high accuracy with low cost.
Keywords: accuracy; approximate tree metric space; Bandwidth; bandwidth allocation; bandwidth measurement; decentralized low cost system; distributed tree; end-to-end prediction; Extraterrestrial measurements; Internet; low-cost network bandwidth prediction; Measurement uncertainty; pairwise bandwidth; Peer to peer computing; Prediction algorithms; trees (mathematics)

Decision and Game Theory for Security: Second International Conference, GameSec 2011, College Park, MD, Maryland, USA, November 14-15, 2011, Proceedings - Baras,John S; Katz, Jonathan; Altman,Eitan (Springer, 2011)
This book constitutes the refereed proceedings of the Second International Conference on Decision and Game Theory for Security, GameSec 2011, held in College Park, Maryland, USA, in November 2011. The 16 revised full papers and 2 plenary keynotes presented were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on attacks, adversaries, and game theory, wireless adhoc and sensor networks, network games, security insurance, security and trust in social networks and security investments.
Keywords: Business & Economics / Information Management; Computers / Hardware / Network Hardware; Computers / Information Technology; Computers / Programming / Algorithms; Computers / Security / General; Mathematics / Applied; Mathematics / Game Theory; Mathematics / General

Direct targeting of Sec23a by miR-200s influences cancer cell secretome and promotes metastatic colonization - Korpal, Manav; Ell, Brian J.; Buffa, Francesca M.; Ibrahim, Toni; Blanco, Mario A.; Celià-Terrassa, Toni; Mercatali, Laura; Zia Khan; Goodarzi, Hani; Hua, Yuling; Wei, Yong; Hu, Guohong; et al. (Nature Medicine, 2011)
Although the role of miR-200s in regulating E-cadherin expression and epithelial-to-mesenchymal transition is well established, their influence on metastatic colonization remains controversial. Here we have used clinical and experimental models of breast cancer metastasis to discover a pro-metastatic role of miR-200s that goes beyond their regulation of E-cadherin and epithelial phenotype. Overexpression of miR-200s is associated with increased risk of metastasis in breast cancer and promotes metastatic colonization in mouse models, phenotypes that cannot be recapitulated by E-cadherin expression alone. Genomic and proteomic analyses revealed global shifts in gene expression upon miR-200 overexpression toward that of highly metastatic cells. miR-200s promote metastatic colonization partly through direct targeting of Sec23a, which mediates secretion of metastasis-suppressive proteins, including Igfbp4 and Tinagl1, as validated by functional and clinical correlation studies. Overall, these findings suggest a pleiotropic role of miR-200s in promoting metastatic colonization by influencing E-cadherin–dependent epithelial traits and Sec23a-mediated tumor cell secretome.View full text

Document Image Classification and Labeling using Multiple Instance Learning - Kumar,Jayant; Pillai,Jaishanker; David Doermann (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
The labeling of large sets of images for training or testing analysis systems can be a very costly and time-consuming process. Multiple instance learning (MIL) is a generalization of traditional supervised learning which relaxes the need for exact labels on training instances. Instead, the labels are required only for a set of instances known as bags. In this paper, we apply MIL to the retrieval and localization of signatures and the retrieval of images containing machine-printed text, and show that a gain of 15-20% in performance can be achieved over the supervised learning with weak-labeling. We also compare our approach to supervised learning with fully annotated training data and report a competitive accuracy for MIL. Using our experiments on real-world datasets, we show that MIL is a good alternative when the training data has only document-level annotation.

The DSPCAD Lightweight Dataflow Environment: Introduction to LIDE Version 0.1 - Chung-Ching Shen; Wang, Lai-Huei; Cho, Inkeun; Kim, Scott; Won, Stephen; Plishker,William; Bhattacharyya, Shuvra S. (Technical Reports from UMIACS, 2011)
LIDE (the DSPCAD Lightweight Dataflow Environment) is a flexible,lightweight design environment that allows designers to experiment with dataflow-based approaches for design and implementation of digital signal processing (DSP) systems. LIDE contains libraries of dataflow graph elements (primitive actors, hierarchical actors, and edges) and utilities that assist designers in modeling, simulating, and implementing DSP systems using formal dataflow techniques. The libraries of dataflow graph elements (mainly actors) contained in LIDE provide useful building blocks that can be used to construct signal processing applications, and that can be used as examples that designers can adapt to create their own, customized LIDE actors. Furthermore, by using LIDE along with the DSPCAD Integrative Command Line Environment (DICE), designers can efficiently create and execute unit tests for user-designed actors. This report provides an introduction to LIDE. The report includes details on the process for setting up the LIDE environment, and covers methods for using pre-designed libraries of graph elements, as well as creating user-designed libraries and associated utilities using the C language. The report also gives an introduction to the C language plug-in for dicelang. This plug-in, called dicelang-C, provides features for efficient C-based project development and maintenance that are useful to apply when working with LIDE.
Keywords: Technical Report

Efficient privacy-preserving biometric identification - Huang,Y.; Malka,L.; Evans,D.; Katz, Jonathan (Network and Distributed System Security Symposium, 2011)
We present an efficient matching protocol that can be usedin many privacy-preserving biometric identification systems in the semi-honest setting. Our most general technical con- tribution is a new backtracking protocol that uses the by- product of evaluating a garbled circuit to enable efficient oblivious information retrieval. We also present a more ef- ficient protocol for computing the Euclidean distances of vectors, and optimized circuits for finding the closest match between a point held by one party and a set of points held by another. We evaluate our protocols by implementing a practical privacy-preserving fingerprint matching system.

Efficient Secure Computation with Garbled Circuits - Huang,Y.; Shen,C.; Evans,D.; Katz, Jonathan; Shelat,A. (Information Systems Security, 2011)
Secure two-party computation enables applications in which participants compute the output of a function that depends on their private inputs, without revealing those inputs or relying on any trusted third party. In this paper, we show the potential of building privacy-preserving applications using garbled circuits, a generic technique that until recently was believed to be too inefficient to scale to realistic problems. We present a Java-based framework that uses pipelining and circuit-level optimizations to build efficient and scalable privacy-preserving applications. Although the standard garbled circuit protocol assumes a very week, honest-but-curious adversary, techniques are available for converting such protocols to resist stronger adversaries, including fully malicious adversaries. We summarize approaches to producing malicious-resistant secure computations that reduce the costs of transforming a protocol to be secure against stronger adversaries. In addition, we summarize results on ensuring fairness, the property that either both parties receive the result or neither party does. Several open problems remain, but as theory and pragmatism advance, secure computation is approaching the point where it offers practical solutions for a wide variety of important problems.

Energy efficient monitoring in sensor networks - Deshpande, Amol; Khuller, Samir; Malekian,A.; Toossi,M. (Algorithmica, 2011)
We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice.We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in α different sets (time-slots). This means that the battery life is extended by a factor of k, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation algorithms for this problem.

Epigenomic and RNA structural correlates of polyadenylation - Khaladkar,Mugdha; Smyda,Mark; Hannenhalli, Sridhar (RNA Biology, 2011)
Polyadenylation (poly(A)) of mRNA plays a critical role in regulating gene expression. Identifying the sequence, structural, and epigenomic determinants of poly(A) site usage is an important long term goal. Several cis elements that mediate poly(A) regulation have been identified. Highly used poly(A) sites are also known to have a greater nucleosome occupancy in the immediate downstream. However, a detailed exploration of additional epigenomic and mRNA structural correlates of poly(A) site usage has not been reported. Importantly, functional interaction between sequence, structure, and the epigenome in determining the poly(A) site usage is not known. We show that highly used poly(A) sites are positively associated with an mRNA structure that is energetically more favorable and one that better exposes a critical polyadenylation cis element. In exploring potential interplay between RNA and chromatin structure, we found that a stronger nucleosome occupancy downstream of poly(A) site strongly correlated with (1) a more favorable mRNA structure, and (2) a greater accumulation of RNA Polymerase II (PolII) at the poly(A) site. Further analysis suggested a causal relationship pointing from PolII accumulation to a stable RNA structure. Additionally, we found that distinct patterns of histone modifications characterize poly(A) sites and these epigenetic patterns alone can distinguish true poly(A) sites with ~76% accuracy and also discriminate between high and low usage poly(A) sites with ~74% accuracy. Our results suggest a causative link between chromatin structure and mRNA structure whereby a compacted chromatin downstream of the poly(A) site slows down the elongating transcript, thus facilitating the folding of nascent mRNA in a favorable structure at poly(A) site during transcription. Additionally we report hitherto unknown epigenomic correlates for poly(A) site usage.

Evaluating visual and statistical exploration of scientific literature networks - Gove,R.; Dunne,C.; Shneiderman, Ben; Klavans,J.; Dorr, Bonnie J (2011 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), 2011)
Action Science Explorer (ASE) is a tool designed to support users in rapidly generating readily consumable summaries of academic literature. It uses citation network visualization, ranking and filtering papers by network statistics, and automatic clustering and summarization techniques. We describe how early formative evaluations of ASE led to a mature system evaluation, consisting of an in-depth empirical evaluation with four domain experts. The evaluation tasks were of two types: predefined tasks to test system performance in common scenarios, and user-defined tasks to test the system's usefulness for custom exploration goals. The primary contribution of this paper is a validation of the ASE design and recommendations to provide: easy-to-understand metrics for ranking and filtering documents, user control over which document sets to explore, and overviews of the document set in coordinated views along with details-on-demand of specific papers. We contribute a taxonomy of features for literature search and exploration tools and describe exploration goals identified by our participants.
Keywords: abstracting; academic literature; action science explorer; automatic clustering; citation analysis; citation network visualization; Communities; Context; custom exploration goal; Data visualization; Databases; Document filtering; document handling; document ranking; easy-to-understand metrics; empirical evaluation; Google; Graphical user interfaces; Information filtering; Information Visualization; Libraries; literature exploration; network statistics; paper filtering; paper ranking; scientific literature network; statistical exploration; summarization technique; user-defined tasks; visual exploration; Visualization

The Evolution of Network Configuration: A Tale of Two Campuses - Kim,H.; Benson,T.; Akella,A.; Feamster, Nick (Networks, 2011)
Studying network configuration evolution can improve our under- standing of the evolving complexity of networks and can be helpful in making network configuration less error-prone. Unfortunately, the nature of changes that operators make to network configuration is poorly understood. Towards improving our understanding, we examine and analyze five years of router, switch, and firewall con- figurations from two large campus networks using the logs from version control systems used to store the configurations. We study how network configuration is distributed across different network operations tasks and how the configuration for each task evolves over time, for different types of devices and for different loca- tions in the network. To understand the trends of how configura- tion evolves over time, we study the extent to which configuration for various tasks are added, modified, or deleted. We also study whether certain devices experience configuration changes more fre- quently than others, as well as whether configuration changes tend to focus on specific portions of the configuration (or on specific tasks). We also investigate when network operators make configu- ration changes of various types. Our results concerning configura- tion changes can help the designers of configuration languages un- derstand which aspects of configuration might be more automated or tested more rigorously and may ultimately help improve config- uration languages.

Extracting Between-Pathway Models from E-MAP Interactions Using Expected Graph Compression - Kelley,D. R; Kingsford, Carl (Journal of Computational Biology, 2011)

Face Detection - Gopalan,Raghuraman; Schwartz,William R.; Chellapa, Rama; Srivastava,Ankur (Visual Analysis of HumansVisual Analysis of Humans, 2011)
Face detection in still images and videos has been extensively studied over the last two decades. Attributed to the recent proliferation of cameras in consumer applications, research in face detection has gradually transformed into more unconstrained settings, with the goal of achieving performance close to humans. This presents two main challenges: (i) in addition to modeling the facial characteristics, understanding the information portrayed by the surrounding scene is important in resolving visual ambiguities, and (ii) the computational time needed for decision making should be compatible for real-time applications, since detection is primarily a front-end process on which additional knowledge extraction is built upon. This chapter begins with a review of recent work in modeling face-specific information, including appearance-based methods used by sliding window classifiers, concepts from learning and local interest-point descriptors, and then focuses on representing the contextual information shared by faces with the surrounding scene. To provide better understanding of working concepts, we discuss a method for learning the semantic context shared by the face with other human body parts that facilitates reasoning under occlusion, and then present an image representation which efficiently encodes contour information to enable fast detection of faces. We conclude the chapter by discussing some existing challenges.

Fast Rule-line Removal using Integral Images and Support Vector Machines - Kumar,Jayant; David Doermann (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
In this paper, we present a fast and effective method for removing pre-printed rule-lines in handwritten document images. We use an integral-image representation which allows fast computation of features and apply techniques for large scale Support Vector learning using a data selection strategy to sample a small subset of training data. Results on both constructed and real-world data sets show that the method is effective for rule-line removal. We compare our method to a subspace-based method and show that better accuracy can be achieved in considerably less time. The integral-image based features proposed in the paper are generic and can be applied to other problems as well.

Faster secure two-party computation using garbled circuits - Huang,Y.; Evans,D.; Katz, Jonathan; Malka,L. (USENIX Security Symposium, 2011)
Secure two-party computation enables two parties toevaluate a function cooperatively without revealing to ei- ther party anything beyond the function’s output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its in- efficiency. We demonstrate several techniques for im- proving the running time and memory requirements of the garbled-circuit technique, resulting in an implemen- tation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of cir- cuits with over 109 gates at a rate of roughly 10 µs per garbled gate, and showing order-of-magnitude improve- ments over the best previous privacy-preserving proto- cols for computing Hamming distance, Levenshtein dis- tance, Smith-Waterman genome alignment, and AES.

GameSec'11: Proceedings of the Second international conference on Decision and Game Theory for Security - Baras,John S; Katz, Jonathan; Altman,Eitan (Springer-Verlag, 2011)

Heterogeneous Design in Functional DIF - Plishker,William; Sane, Nimish; Kiemb, Mary; Bhattacharyya, Shuvra S. (Transactions on High-Performance Embedded Architectures and Compilers IV, 2011)
Dataflow formalisms have provided designers of digital signal processing (DSP) systems with analysis and optimizations for many years. As system complexity increases, designers are relying on more types of dataflow models to describe applications while retaining these implementation benefits. The semantic range of DSP-oriented dataflow models has expanded to cover heterogeneous models and dynamic applications, but efficient design, simulation, and scheduling of such applications has not. To facilitate implementing heterogeneous applications, we utilize a new dataflow model of computation and show how actors designed in other dataflow models are directly supported by this framework, allowing system designers to immediately compose and simulate actors from different models. Using examples, we show how this approach can be applied to quickly describe and functionally simulate a heterogeneous dataflow-based application such that a designer may analyze and tune trade-offs among different models and schedules for simulation time, memory consumption, and schedule size.
Keywords: Arithmetic and Logic Structures; Computer Communication Networks; Dataflow; heterogeneous; Input/Output and Data Communications; Logic Design; Processor Architectures; Programming Languages, Compilers, Interpreters; Signal processing

Image and Video-Based Biometrics - Patel, Vishal M.; Pillai,Jaishanker K.; Chellapa, Rama (Visual Analysis of HumansVisual Analysis of Humans, 2011)
Biometrics deals with the problem of identifying individuals based on physiological or behavioral characteristics. Since many physical characteristics, such as face, iris, etc., and behavioral characteristics, such as voice, expression, etc., are unique to an individual, biometric analysis offers a reliable and natural solution to the problem of identity verification. In this chapter, we discuss image and video-based biometrics involving face, iris and gait. In particular, we discuss several recent approaches to physiological biometrics based on Sparse Representations and Compressed Sensing. Some of the most compelling challenges and issues that confront research in biometrics are also addressed.

Impossibility of blind signatures from one-way permutations - Katz, Jonathan; Schröder,D.; Yerukhimovich,A. (Theory of Cryptography, 2011)
A seminal result in cryptography is that signature schemes can be constructed (in a black-box fashion) from any one-way function. The minimal assumptions needed to construct blind signature schemes, however, have remained unclear. Here, we rule out black-box constructions of blind signature schemes from one-way functions. In fact, we rule out constructions even from a random permutation oracle, and our results hold even for blind signature schemes for 1-bit messages that achieve security only against honest-but-curious behavior.

Increased gene sampling provides stronger support for higher-level groups within gracillariid leaf mining moths and relatives (Lepidoptera: Gracillariidae) - Kawahara,A. Y; Ohshima,I; Kawakita,A; Regier,J. C; Mitter,C; Cummings, Michael P.; Davis,DR; Wagner,DL; De Prinis,J; Lopez-Vaamonde,C (BMC Evol Biol, 2011)

Information Visualization: State of the Field and New Research Directions - Kerren,Andreas; Plaisant, Catherine; Stasko,John T (Information VisualizationInformation Visualization, 2011)

Interaction of Vibrio cholerae non-O1/non-O139 with Copepods, Cladocerans and Competing Bacteria in the Large Alkaline Lake Neusiedler See, Austria - Kirschner,A. K. T.; Schauer,S.; Steinberger,B.; Wilhartitz,I.; Grim,C. J.; Huq,A.; Rita R Colwell; Herzig,A.; Sommer,R. (Microbial ecology, 2011)
Vibrio cholerae is a human pathogen and natural inhabitant of aquatic environments. Serogroups O1/O139 have been associated with epidemic cholera, while non-O1/non-O139 serogroups usually cause human disease other than classical cholera. V. cholerae non-O1/non-O139 from the Neusiedler See, a large Central European lake, have caused ear and wound infections, including one case of fatal septicaemia. Recent investigations demonstrated rapid planktonic growth of V. cholerae non-O1/non-O139 and correlation with zooplankton biomass. The aim of this study was to elucidate the interaction of autochthonous V. cholerae with two dominant crustacean zooplankton species in the lake and investigate the influence of the natural bacterial community on this interaction. An existing data set was evaluated for statistical relationships between zooplankton species and V. cholerae and co-culture experiments were performed in the laboratory. A new fluorescence in situ hybridisation protocol was applied for quantification of V. cholerae non-O1/non-O139 cells, which significantly reduced analysis time. The experiments clearly demonstrated a significant relationship of autochthonous V. cholerae non-O1/non-O139 with cladocerans by promoting growth of V. cholerae non-O1/non-O139 in the water and on the surfaces of the cladocerans. In contrast, copepods had a negative effect on the growth of V. cholerae non-O1/non-O139 via competing bacteria from their surfaces. Thus, beside other known factors, biofilm formation by V. cholerae on crustacean zooplankton appears to be zooplankton taxon specific and may be controlled by the natural bacterial community.

Language Models for Semantic Extraction and Filtering in Video Action Recognition - Tzoukermann,Evelyne; Neumann, Jan; Kosecka,Jana; Fermüller, Cornelia; Perera,Ian; Ferraro,Frank; Sapp,Ben; Chaudhry,Rizwan; Singh,Gautam (Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011)
The paper addresses the following issues: (a) how to represent semantic information from natural language so that a vision model can utilize it? (b) how to extract the salient textual information relevant to vision? For a given domain, we present a new model of semantic extraction that takes into account word relatedness as well as word disambiguation in order to apply to a vision model. We automatically process the text transcripts and perform syntactic analysis to extract dependency relations. We then perform semantic extraction on the output to filter semantic entities related to actions. The resulting data are used to populate a matrix of co-occurrences utilized by the vision processing modules. Results show that explicitly modeling the co-occurrence of actions and tools significantly improved performance.

Limits of computational differential privacy in the client/server setting - Groce,A.; Katz, Jonathan; Yerukhimovich,A. (Theory of Cryptography, 2011)
Differential privacy is a well established definition guaranteeing that queries to a database do not reveal “too much” information about specific individuals who have contributed to the database. The standard definition of differential privacy is information theoretic in nature, but it is natural to consider computational relaxations and to explore what can be achieved with respect to such notions. Mironov et al. (Crypto 2009) and McGregor et al. (FOCS 2010) recently introduced and studied several variants of computational differential privacy, and show that in the two-party setting (where data is split between two parties) these relaxations can offer significant advantages.Left open by prior work was the extent, if any, to which computational differential privacy can help in the usual client/server setting where the entire database resides at the server, and the client poses queries on this data. We show, for queries with output in ℝ n (for constant n) and with respect to a large class of utilities, that any computationally private mechanism can be converted to a statistically private mechanism that is equally efficient and achieves roughly the same utility.

Limits on the power of zero-knowledge proofs in cryptographic constructions - Brakerski,Z.; Katz, Jonathan; Segev,G.; Yerukhimovich,A. (Theory of Cryptography, 2011)
For over 20 years, black-box impossibility results have been used to argue the infeasibility of constructing certain cryptographic primitives (e.g., key agreement) from others (e.g., one-way functions). A widely recognized limitation of such impossibility results, however, is that they say nothing about the usefulness of (known) nonblack-box techniques. This is unsatisfying, as we would at least like to rule out constructions using the set of techniques we have at our disposal.With this motivation in mind, we suggest a new framework for black-box constructions that encompasses constructions with a nonblack-box flavor: specifically, those that rely on zero-knowledge proofs relative to some oracle. We show that our framework is powerful enough to capture the Naor-Yung/Sahai paradigm for building a (shielding) CCA-secure public-key encryption scheme from a CPA-secure one, something ruled out by prior black-box separation results. On the other hand, we show that several black-box impossibility results still hold even in a setting that allows for zero-knowledge proofs.

Localizing parts of faces using a consensus of exemplars - Belhumeur,P. N.; Jacobs, David W.; Kriegman, D.J.; Kumar,N. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
We present a novel approach to localizing parts in images of human faces. The approach combines the output of local detectors with a non-parametric set of global models for the part locations based on over one thousand hand-labeled exemplar images. By assuming that the global models generate the part locations as hidden variables, we derive a Bayesian objective function. This function is optimized using a consensus of models for these hidden variables. The resulting localizer handles a much wider range of expression, pose, lighting and occlusion than prior ones. We show excellent performance on a new dataset gathered from the internet and show that our localizer achieves state-of-the-art performance on the less challenging BioID dataset.
Keywords: Bayesian; faces; lighting; occlusion; pose; Bayes; function; exemplar; images; expression; face; localization; human; methods; face; objective; part; recognition

Model-based precision analysis and optimization for digital signal processors - Kedilaya, Soujanya; Plishker,William; Purkovic, Aleksandar; Johnson, Brian; Bhattacharyya, Shuvra S. (Proceedings of the European Signal Processing Conference, 2011)
Embedded signal processing has witnessed explosive growth in re-cent years in both scientific and consumer applications, driving the need for complex, high-performance signal processing systems that are largely application driven. In order to efficiently implement these systems on programmable platforms such as digital signal processors (DSPs), it is important to analyze and optimize the ap- plication design from early stages of the design process. A key per- formance concern for designers is choosing the data format. In this work, we propose a systematic and efficient design flow involving model-based design to analyze application data sets and precision requirements. We demonstrate this design flow with an exploration study into the required precision for eigenvalue decomposition (EVD) using the Jacobi algorithm. We demonstrate that with a high degree of structured analysis and automation, we are able to analyze the data set to derive an efficient data format, and optimize important parts of the algorithm with respect to precision.

NetVisia: Heat Map & Matrix Visualization of Dynamic Social Network Statistics & Content - Gove,R.; Gramsky,N.; Kirby,R.; Sefer,E.; Sopan,A.; Dunne,C.; Shneiderman, Ben; Taieb-Maimon,M. (Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom), 2011)
Visualizations of static networks in the form of node-link diagrams have evolved rapidly, though researchers are still grappling with how best to show evolution of nodes over time in these diagrams. This paper introduces NetVisia, a social network visualization system designed to support users in exploring temporal evolution in networks by using heat maps to display node attribute changes over time. NetVisia's novel contributions to network visualizations are to (1) cluster nodes in the heat map by similar metric values instead of by topological similarity, and (2) align nodes in the heat map by events. We compare NetVisia to existing systems and describe a formative user evaluation of a NetVisia prototype with four participants that emphasized the need for tool tips and coordinated views. Despite the presence of some usability issues, in 30-40 minutes the user evaluation participants discovered new insights about the data set which had not been discovered using other systems. We discuss implemented improvements to NetVisia, and analyze a co-occurrence network of 228 business intelligence concepts and entities. This analysis confirms the utility of a clustered heat map to discover outlier nodes and time periods.
Keywords: business intelligence concept; business intelligence entity; competitive intelligence; data visualisation; dynamic networks; dynamic social network; heat map; Heating; Image color analysis; Information Visualization; Layout; matrix visualization; measurement; NetVisia system; network evolution; network visualization; node-link diagrams; outlier node; social network content; Social network services; social network statistics; social networking (online); social networks; static network visualization; time period; topological similarity; Training; usability; user evaluation; User interfaces

New models and algorithms for throughput maximization in broadcast scheduling - Chekuri,C.; Gal,A.; Im,S.; Khuller, Samir; Li,J.; McCutchen,R.; Moseley,B.; Raschid, Louiqa (Approximation and Online Algorithms, 2011)

Next Generation Sequence Assembly with AMOS - Treangen, T.J.; Sommer, D.D.; Angly, F.E.; Koren, S.; Pop, Mihai (Current Protocols in Bioinformatics, 2011)

NSF/IEEE-TCPP curriculum initiative on parallel and distributed computing: core topics for undergraduates - Prasad,S. K.; Chtchelkanova,A.; Das,S.; Dehne,F.; Gouda,M.; Gupta,A.; JaJa, Joseph F.; Kant,K.; La Salle,A.; LeBlanc,R.; others (Proceedings of the 42nd ACM technical symposium on Computer science education, 2011)

Object Detection and Tracking for Intelligent Video Surveillance - Kim,K.; Davis, Larry S. (Multimedia Analysis, Processing and Communications, 2011)
Appearing as an important task in computer vision, pedestrian detection has been widely investigated in the recent years. To design a robust detector, we propose a feature descriptor called Local Response Context (LRC). This descriptor captures discriminative information regarding the surrounding of the person’s location by sampling the response map obtained by a generic sliding window detector. A partial least squares regression model using LRC descriptors is learned and employed as a second classification stage (after the execution of the generic detector to obtain the response map). Experiments based on the ETHZ pedestrian dataset show that the proposed approach improves significantly the results achieved by the generic detector alone and is comparable to the state-of-the-art methods.

Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? - Huang,Y.; Evans,D.; Katz, Jonathan (19th Network and Distributed Security Symposium, 2011)
Cryptographic protocols for Private Set Intersection (PSI)are the basis for many important privacy-preserving ap- plications. Over the past few years, intensive research has been devoted to designing custom protocols for PSI based on homomorphic encryption and other public-key tech- niques, apparently due to the belief that solutions using generic approaches would be impractical. This paper ex- plores the validity of that belief. We develop three classes of protocols targeted to different set sizes and domains, all based on Yao’s generic garbled-circuit method. We then compare the performance of our protocols to the fastest custom PSI protocols in the literature. Our results show that a careful application of garbled circuits leads to solu- tions that can run on million-element sets on typical desk- tops, and that can be competitive with the fastest custom protocols. Moreover, generic protocols like ours can be used directly for performing more complex secure com- putations, something we demonstrate by adding a simple information-auditing mechanism to our PSI protocols.

Rapid understanding of scientific paper collections: integrating statistics, text analysis, and visualization - Dunne,C.; Shneiderman, Ben; Gove,R.; Klavans,J.; Dorr, Bonnie J (University of Maryland, Human-Computer Interaction Lab Tech Report HCIL-2011, 2011)
Keeping up with rapidly growing research fields, especially when there aremultiple interdisciplinary sources, requires substantial effort for researchers, program managers, or venture capital investors. Current theories and tools are directed at finding a paper or website, not gaining an understanding of the key papers, authors, controversies, and hypotheses. This report presents an effort to integrate statistics, text analytics, and visualization in a multiple coordinated window environment that supports exploration. Our prototype system, Action Science Explorer (ASE), provides an environment for demon- strating principles of coordination and conducting iterative usability tests of them with interested and knowledgeable users. We developed an under- standing of the value of reference management, statistics, citation context extraction, natural language summarization for single and multiple docu- ments, filters to interactively select key papers, and network visualization to see citation patterns and identify clusters. The three-phase usability study guided our revisions to ASE and led us to improve the testing methods.

Real-Time Planning for Covering an Initially-Unknown Spatial Environment - Shivashankar,V.; Jain, R.; Kuter,U.; Nau, Dana S. (2011)
We consider the problem of planning, on the fly, a path whereby a robotic vehicle will cover every point in an ini- tially unknown spatial environment. We describe four strate- gies (Iterated WaveFront, Greedy-Scan, Delayed Greedy- Scan and Closest-First Scan) for generating cost-effective coverage plans in real time for unknown environments. We give theorems showing the correctness of our planning strate- gies. Our experiments demonstrate that some of these strate- gies work significantly better than others, and that the best ones work very well; e.g., in environments having an average of 64,000 locations for the robot to cover, the best strategy re- turned plans with less than 6% redundant coverage, and took only an average of 0.1 milliseconds per action.

Research Directions in Data Wrangling: Visualizations and Transformations for Usable and Credible Data - Kandel,Sean; Heer,Jeffrey; Plaisant, Catherine; Kennedy,Jessie; Van Ham,Frank; Riche,Nathalie Henry; Weaver,Chris; Lee,Bongshin; Brodbeck,Dominique; Buono,Paolo (Information VisualizationInformation Visualization, 2011)
In spite of advances in technologies for working with data, analysts still spend an inordinate amount of time diagnosing data quality issues and manipulating data into a usable form. This process of ‘data wrangling’ often constitutes the most tedious and time-consuming aspect of analysis. Though data cleaning and integration arelongstanding issues in the database community, relatively little research has explored how interactive visualization can advance the state of the art. In this article, we review the challenges and opportunities associated with addressing data quality issues. We argue that analysts might more effectively wrangle data through new interactive systems that integrate data verification, transformation, and visualization. We identify a number of outstanding research questions, including how appropriate visual encodings can facilitate apprehension of missing data, discrepant values, and uncertainty; how interactive visualizations might facilitate data transform specification; and how recorded provenance and social interaction might enable wider reuse, verification, and modification of data transformations.
Keywords: data cleaning; data quality; data transformation; Uncertainty; Visualization

Round-optimal password-based authenticated key exchange - Katz, Jonathan; Vaikuntanathan,V. (Theory of Cryptography, 2011)
We show a general framework for constructing password-based authenticated key exchange protocols with optimal round complexity — one message per party, sent simultaneously — in the standard model, assuming a common reference string. When our framework is instantiated using bilinear-map cryptosystems, the resulting protocol is also (reasonably) efficient. Somewhat surprisingly, our framework can be adapted to give protocols in the standard model that are universally composable while still using only one (simultaneous) round.

Secure computation with sublinear amortized work - Gordon,D.; Katz, Jonathan; Kolesnikov,V.; Malkin,T.; Raykova,M.; Vahlis,Y. (Cryptology ePrint Archive, Report 2011/482, 2011)
Traditional approaches to secure computation begin by representing the function f beingcomputed as a circuit. For any function f that depends on each of its inputs, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for secure computation of non-trivial functions, since each party must “touch” every bit of their input lest information about other party’s input be leaked. This seems to rule out many interesting applications of secure computation in scenarios where at least one of the inputs is huge and sublinear-time algorithms can be utilized in the insecure setting; private database search is a prime example. We present an approach to secure two-party computation that yields sublinear-time proto- cols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine (RAM). Furthermore, a party whose input is “small” is required to maintain only small state. We provide a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.

Segmentation of Handwritten Textlines in Presence of Touching Components - Kumar,Jayant; Kang,Le; David Doermann; Abd-Almageed, Wael (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
This paper presents an approach to textline extraction in handwritten document images which combines local and global techniques. We propose a graph-based technique to detect touching and proximity errors that are common with handwritten text lines. In a refinement step, we use Expectation-Maximization (EM) to iteratively split the error segments to obtain correct text-lines. We show improvement in accuracies using our correction method on datasets of Arabic document images. Results on a set of artificially generated proximity images show that the method is effective for handling touching errors in handwritten document images.

Sensitivity analysis and explanations for robust query evaluation in probabilistic databases - Kanagal,B.; Li,J.; Deshpande, Amol (Proceedings of the 2011 international conference on Management of data, 2011)
Probabilistic database systems have successfully established them-selves as a tool for managing uncertain data. However, much of the research in this area has focused on efficient query evaluation and has largely ignored two key issues that commonly arise in uncer- tain data management: First, how to provide explanations for query results, e.g., “Why is this tuple in my result?” or “Why does this output tuple have such high probability?”. Second, the problem of determining the sensitive input tuples for the given query, e.g., users are interested to know the input tuples that can substantially alter the output, when their probabilities are modified (since they may be unsure about the input probability values). Existing systems pro- vide the lineage/provenance of each of the output tuples in addition to the output probabilities, which is a boolean formula indicating the dependence of the output tuple on the input tuples. However, lineage does not immediately provide a quantitative relationship and it is not informative when we have multiple output tuples. In this paper, we propose a unified framework that can handle both the issues mentioned above to facilitate robust query processing. We formally define the notions of influence and explanations and provide algorithms to determine the top-l influential set of variables and the top-l set of explanations for a variety of queries, including conjunctive queries, probabilistic threshold queries, top-k queries and aggregation queries. Further, our framework naturally enables highly efficient incremental evaluation when input probabilities are modified (e.g., if uncertainty is resolved). Our preliminary exper- imental results demonstrate the benefits of our framework for per- forming robust query processing over probabilistic databases.

Shape Codebook based Handwritten and Machine Printed Text Zone Extraction - Kumar,Jayant; Prasad,Rohit; Cao,Huiagu; Abd-Almageed, Wael; David Doermann; Natarajan,Prem (Document Recognition and Retrieval, 2011)
We present a novel method for extracting handwritten and printed text zones from noisy document images with mixed content. We use Triple-Adjacent-Segment (TAS) based features which encode local shape characteristics of text in a consistent manner. We first construct two different codebooks of the shape features extracted from a set of handwritten and printed text documents. In the next step, we compute the normalized histogram of codewords for each segmented zone and use it to train Support Vector Machine (SVM) classifier. Due to a codebook based approach, our method is robust to the background noise present in the image. The TAS features used are invariant to translation, scale and rotation of text. In our experimental results, we show that a pixel-weighted zone classification accuracy of 98% can be achieved for noisy Arabic documents. Further, we demonstrate the effectiveness of our method for document page classification and show that a high precision can be achieved for machine printed documents. The proposed method is robust to the size of zones, which may contain text content at word, line or paragraph level.

Speeding Up Network Layout and Centrality Measures for Social Computing Goals - Sharma,Puneet; Khurana,Udayan; Shneiderman, Ben; Scharrenbroich,Max; Locke,John (Social Computing, Behavioral-Cultural Modeling and PredictionSocial Computing, Behavioral-Cultural Modeling and Prediction, 2011)
This paper presents strategies for speeding up calculation of graph metrics and layout by exploiting the parallel architecture of modern day Graphics Processing Units (GPU), specifically Compute Unified Device Architecture ( CUDA ) by Nvidia . Graph centrality metrics like Eigenvector , Betweenness , Page Rank and layout algorithms like Fruchterman − Rheingold are essential components of Social Network Analysis ( SNA ). With the growth in adoption of SNA in different domains and increasing availability of huge networked datasets for analysis, social network analysts require faster tools that are also scalable. Our results, using NodeXL, show up to 802 times speedup for a Fruchterman-Rheingold graph layout and up to 17,972 times speedup for Eigenvector centrality metric calculations on a 240 core CUDA-capable GPU.

Temperature regulation of virulence factors in the pathogen Vibrio coralliilyticus - Kimes,Nikole E.; Grim,Christopher J.; Johnson,Wesley R.; Hasan,Nur A.; Tall,Ben D.; Kothary,Mahendra H.; Kiss,Hajnalka; Munk,A. Christine; Tapia,Roxanne; Green,Lance; Detter,Chris; Bruce,David C.; et al. (The ISME Journal, 2011)
Sea surface temperatures (SST) are rising because of global climate change. As a result, pathogenic Vibrio species that infect humans and marine organisms during warmer summer months are of growing concern. Coral reefs, in particular, are already experiencing unprecedented degradation worldwide due in part to infectious disease outbreaks and bleaching episodes that are exacerbated by increasing SST. For example, Vibrio coralliilyticus, a globally distributed bacterium associated with multiple coral diseases, infects corals at temperatures above 27 °C. The mechanisms underlying this temperature-dependent pathogenicity, however, are unknown. In this study, we identify potential virulence mechanisms using whole genome sequencing of V. coralliilyticus ATCC (American Type Culture Collection) BAA-450. Furthermore, we demonstrate direct temperature regulation of numerous virulence factors using proteomic analysis and bioassays. Virulence factors involved in motility, host degradation, secretion, antimicrobial resistance and transcriptional regulation are upregulated at the higher virulent temperature of 27 °C, concurrent with phenotypic changes in motility, antibiotic resistance, hemolysis, cytotoxicity and bioluminescence. These results provide evidence that temperature regulates multiple virulence mechanisms in V. coralliilyticus, independent of abundance. The ecological and biological significance of this temperature-dependent virulence response is reinforced by climate change models that predict tropical SST to consistently exceed 27 °C during the spring, summer and fall seasons. We propose V. coralliilyticus as a model Gram-negative bacterium to study temperature-dependent pathogenicity in Vibrio-related diseases.
Keywords: ecophysiology; ecosystems; environmental biotechnology; geomicrobiology; ISME J; microbe interactions; microbial communities; microbial ecology; microbial engineering; microbial epidemiology; microbial genomics; microorganisms

Template based Segmentation of Touching Components in Handwritten Text Lines - Kang,Le; David Doermann (11th Intl. Conf. on Document Analysis and Recognition (ICDAR'11), 2011)
In this paper, we present a template based approach to the segmentation of touching components in handwritten text lines. Local patches around touching components are identified and a dictionary is created consisting of template patches together with correct segmentations. We use two shape context based methods to compute similarity between input patches and dictionary templates to find the best match. The template's known segmentation is then transformed to segment the input patch. Experiments are carried on a dataset of touching text lines.

Toolchain for Programming, Simulating and Studying the XMT Many-Core Architecture - Keceli,F.; Tzannes,A.; Caragea,G.C.; Barua,R.; Vishkin, Uzi (Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on, 2011)
The Explicit Multi-Threading (XMT) is a general-purpose many-core computing platform, with the vision of a 1000-core chip that is easy to program but does not compromise on performance. This paper presents a publicly available tool chain for XMT, complete with a highly configurable cycle-accurate simulator and an optimizing compiler. The XMT tool chain has matured and has been validated to a point where its description merits publication. In particular, research and experimentation enabled by the tool chain played a central role in supporting the ease-of-programming and performance aspects of the XMT architecture. The compiler and the simulator are also important milestones for an efficient programmer's workflow from PRAM algorithms to programs that run on the shared memory XMT hardware. This workflow is a key component in accomplishing the dual goal of ease-of-programming and performance. The applicability of our tool chain extends beyond specific XMT choices. It can be used to explore the much greater design space of shared memory many-cores by system researchers or by programmers. As the tool chain can practically run on any computer, it provides a supportive environment for teaching parallel algorithmic thinking with a programming component. Unobstructed by techniques such as decomposition-first and programming for locality, this environment may be useful in deferring the teaching of these techniques, when desired, to more advanced or platform-specific courses.
Keywords: algorithm; XMT; architecture; XMT; architectures; shared; chain; cycle-accurate; compiler; programmer; compilers; parallel; component; shared; computing; optimizing; hardware; shared; many-core; many-core; concurrency; memory; multithreading; general-purpose; PRAM; simulator; ease-of-programming; explicit; systems; theory; multi-threading; optimising; tool; workflow; programming; XMT

Topological Patterns for Scalable Representation and Analysis of Dataflow Graphs - Sane, Nimish; Kee, Hojin; Seetharaman, Gunasekaran; Bhattacharyya, Shuvra S. (Journal of Signal Processing Systems, 2011)
Tools for designing signal processing systems with their semantic foundation in dataflow modeling often use high-level graphical user interfaces (GUIs) or text based languages that allow specifying applications as directed graphs. Such graphical representations serve as an initial reference point for further analysis and optimizations that lead to platform-specific implementations. For large-scale applications, the underlying graphs often consist of smaller substructures that repeat multiple times. To enable more concise representation and direct analysis of such substructures in the context of high level DSP specification languages and design tools, we develop the modeling concept of topological patterns, and propose ways for supporting this concept in a high-level language. We augment the dataflow interchange format (DIF) language—a language for specifying DSP-oriented dataflow graphs—with constructs for supporting topological patterns, and we show how topological patterns can be effective in various aspects of embedded signal processing design flows using specific application examples.
Keywords: Circuits and Systems; Computer Imaging, Vision, Pattern Recognition and Graphics; Dataflow graphs; Electrical Engineering; High-level languages; Image Processing and Computer Vision; model-based design; pattern recognition; Signal processing systems; Signal, Image and Speech Processing; Topological patterns

A Two Degree of Freedom Nanopositioner With Electrothermal Actuator for Decoupled Motion - Kim,Yong-Sik; Dagalakis,Nicholas G.; Gupta, Satyandra K. (ASME, 2011)
Building a two degree-of-freedom (2 DOF) MEMS nanopositioner with decoupled X-Y motion has been a challenge in nanopositioner design. In this paper a novel design concept on making the decoupled motion of the MEMS nanopositioner is suggested. The suggested nanopositioner has two electrothermal actuators and employs a fully nested motion platform with suspended anchors. The suggested MEMS nanopositioner is capable of delivering displacement from the electrothermal actuator to the motion platform without coupled motion between the two X-Y axes. The design concept, finite element analysis (FEA) results, fabrication procedures and the performance of the 2 DOF nanopositioner is presented. In order to test the nanopositioner moving platform decoupled motion, one actuator moves the platform by 60 µm, while the other actuator is kept at the same position. The platform position cross talk error was measured to be less than 1 µm standard deviation.

Understanding Scientific Literature Networks: An Evaluation of Action Science Explorer - Gove,R.; Dunne,C.; Shneiderman, Ben; Klavans,J.; Dorr, Bonnie J (University of Maryland at College Park, 2011)
Action Science Explorer (ASE) is a tool designed to supportusers in rapidly generating readily consumable summaries of academic literature. The authors describe ASE and report on how early formative evaluations led to a mature system evaluation, consisting of an in-depth empirical evaluation with 4 domain expert participants. The user study tasks were of two types: predefined tasks to test system perfor- mance in common scenarios, and user-defined tasks to test the system’s usefulness for custom exploration goals. This paper concludes by describing ASE’s attribute ranking ca- pability which is a novel contribution for exploring scientific literature networks. It makes design recommendations to: give the users control over which documents to explore, easy- to-understand metrics for ranking documents, and overviews of the document set in coordinated views along with details- on-demand of specific papers.

Universally composable synchronous computation - Katz, Jonathan; Maurer,U.; Tackmann,B.; Zikas,V. (Cryptology ePrint Archive, Report 2011/310, 2011. http://eprint. iacr. org, 2011)
In synchronous networks, protocols can achieve security guarantees that are not possible in an asynchronousworld: i.e., they can simultaneously achieve input completeness (all honest parties’ inputs are included in the computation) and guaranteed termination (honest parties do not “hang” indefinitely). In practice truly syn- chronous networks rarely exist, but synchrony can be emulated if channels have (known) latency and parties have loosely synchronized clocks. The framework of universal composability (UC) is inherently asynchronous, but several approaches for adding synchrony to the framework have been proposed. However, we show that the existing proposals do not provide the expected guarantees. Given this, we propose a “clean slate” approach to defining synchrony in the UC framework by introducing functionalities exactly meant to model, respectively, bounded-delay networks and loosely synchronized clocks. We show that the expected guarantees of synchronous computation can be realized given these functionalities, and that previous models can all be expressed within our new framework.

Vectorization and mapping of software defined radio applications on heterogeneous multi-processor platforms - Zaki, G.F.; Plishker,W.; Bhattacharyya, Shuvra S.; Clancy, C.; Kuykendall, J. (2011 IEEE Workshop on Signal Processing Systems (SiPS), 2011)
A variety of multiprocessor architectures have proliferated even for off-the-shelf computing platforms. To improve performance and productivity for common heterogeneous systems, we have developed a workflow to generate efficient solutions. By starting with a formal description of an application and the mapping problem we are able to generate a range of designs that efficiently trade-of latency and throughput. In this approach, efficient utilization of SIMD cores is achieved by applying extensive block processing in conjunction with efficient mapping and scheduling. We demonstrate our approach through an integration into the GNU Radio environment for software defined radio system design.
Keywords: Benchmark testing; block processing; Design methodology; formal description; GNU radio environment; Graphic Processor Unit; Graphics processing unit; heterogeneous multiprocessor platform; mapping problem; Multicore processing; Multiprocessing systems; multiprocessor architecture; multiprocessor scheduling; operating systems (computers); PARALLEL PROCESSING; Processor scheduling; Schedules; SIMD core; Software Defined Radio; software defined radio system design; software radio; telecommunication computing; Throughput; vectorization; workflow

Vehicle Detection Using Partial Least Squares - Kembhavi,A.; Harwood,D.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2011)
Detecting vehicles in aerial images has a wide range of applications, from urban planning to visual surveillance. We describe a vehicle detector that improves upon previous approaches by incorporating a very large and rich set of image descriptors. A new feature set called Color Probability Maps is used to capture the color statistics of vehicles and their surroundings, along with the Histograms of Oriented Gradients feature and a simple yet powerful image descriptor that captures the structural characteristics of objects named Pairs of Pixels. The combination of these features leads to an extremely high-dimensional feature set (approximately 70,000 elements). Partial Least Squares is first used to project the data onto a much lower dimensional subspace. Then, a powerful feature selection analysis is employed to improve the performance while vastly reducing the number of features that must be calculated. We compare our system to previous approaches on two challenging data sets and show superior performance.
Keywords: aerial images; color probability maps; oriented gradients feature; partial least squares; powerful feature selection analysis; urban planning; vehicle detection; visual surveillance; gradient methods; image colour analysis; least squares approximations; road vehicle; Automated

Visual Analysis of Temporal Trends in Social Networks Using Edge Color Coding and Metric Timelines - Khurana,U.; Nguyen,Viet-An; Hsueh-Chien Cheng; Ahn,Jae-wook; Chen,Xi; Shneiderman, Ben (Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom), 2011)
We present Net EvViz, a visualization tool for analysis and exploration of a dynamic social network. There are plenty of visual social network analysis tools but few provide features for visualization of dynamically changing networks featuring the addition or deletion of nodes or edges. Our tool extends the code base of the Node XL template for Microsoft Excel, a popular network visualization tool. The key features of this work are (1) The ability of the user to specify and edit temporal annotations to the network components in an Excel sheet, (2) See the dynamics of the network with multiple graph metrics plotted over the time span of the graph, called the Timeline, and (3) Temporal exploration of the network layout using an edge coloring scheme and a dynamic Time slider. The objectives of the new features presented in this paper are to let the data analysts, computer scientists and others to observe the dynamics or evolution in a network interactively. We presented Net EvViz to five users of Node XL and received positive responses.
Keywords: Color; computer scientists; data analysts; data visualisation; Data visualization; dynamic social network; dynamic timeslider; edge color coding; excel sheet; Image coding; image colour analysis; Layout; measurement; metric timelines; Microsoft excel; multiple graph metrics; Net EvViz; network components; network layout; network visualization tool; NodeXL template; social networking (online); temporal trends; Twitter; Visualization

Wide-area routing dynamics of malicious networks - Konte,Maria; Feamster, Nick (Proceedings of the ACM SIGCOMM 2011 conference, 2011)
This paper studies the routing dynamics of malicious networks. We characterize the routing behavior of malicious networks on both short and long timescales. We find that malicious networks more consistently advertise prefixes with short durations and long inter- arrival times; over longer timescales, we find that malicious ASes connect with more upstream providers than legitimate ASes, and they also change upstream providers more frequently.
Keywords: BGP; Security; spam

Achieving anonymity via clustering - Aggarwal,Gagan; Panigrahy,Rina; Feder,Tomás; Thomas,Dilys; Kenthapadi,Krishnaram; Khuller, Samir; Zhu,An (ACM Trans. Algorithms, 2010)
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. However, recent research has shown that a large fraction of the U.S. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k-anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, that is, deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
Keywords: anonymity; Approximation algorithms; clustering; privacy

AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead - Horvitz,Eric; Getoor, Lise; Guestrin,Carlos; Hendler,James; Konstan,Joseph; Subramanian,Devika; Wellman,Michael; Kautz,Henry (AI Magazine, 2010)
AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead

Alignment and clustering of phylogenetic markers - implications for microbial diversity studies - White,James R; Navlakha,Saket; Nagarajan,Niranjan; Ghodsi,Mohammad-Reza; Kingsford, Carl; Pop, Mihai (BMC Bioinformatics, 2010)
Molecular studies of microbial diversity have provided many insights into the bacterial communities inhabiting the human body and the environment. A common first step in such studies is a survey of conserved marker genes (primarily 16S rRNA) to characterize the taxonomic composition and diversity of these communities. To date, however, there exists significant variability in analysis methods employed in these studies.

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design - Chekuri,C.; Hajiaghayi, Mohammad T.; Kortsarz,G.; Salavatipour,M. R (SIAM Journal on Computing, 2010)

Are developers complying with the process: an XP study - Zazworka, Nico; Stapel,Kai; Knauss,Eric; Shull, Forrest; Basili, Victor R.; Schneider,Kurt (Proceedings of the 2010 ACM-IEEE International Symposium on Empirical Software Engineering and Measurement, 2010)
Adapting new software processes and practices in organizational and academic environments requires training the developers and validating the applicability of the newly introduced activities. Investigating process conformance during training and understanding if programmers are able and willing to follow the specific steps are crucial to evaluating whether the process improves various software product quality factors. In this paper we present a process model independent approach to detect process non-conformance. Our approach is based on non-intrusively collected data captured by a version control system and provides the project manager with timely updates. Further, we provide evidence of the applicability of our approach by investigating process conformance in a five day training class on eXtreme Programming (XP) practices at the Leibniz Universität Hannover. Our results show that the approach enabled researchers to formulate minimal intrusive methods to check for conformance and that for the majority of the investigated XP practices violations could be detected.
Keywords: process conformance; process improvement; XP programming

Assembly complexity of prokaryotic genomes using short reads - Kingsford, Carl; Schatz,Michael C; Pop, Mihai (BMC Bioinformatics, 2010)
De Bruijn graphs are a theoretical framework underlying several modern genome assembly programs, especially those that deal with very short reads. We describe an application of de Bruijn graphs to analyze the global repeat structure of prokaryotic genomes.

Authenticated broadcast with a partially compromised public-key infrastructure - Gordon,S.; Katz, Jonathan; Kumaresan,R.; Yerukhimovich,A. (Stabilization, Safety, and Security of Distributed Systems, 2010)
Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. Almost all existing protocols, however, do not distinguish between corrupted parties (who do not follow the protocol), and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly). We explore conditions under which it is possible to construct broadcast protocols that still provide the usual guarantees (i.e., validity/agreement) to the latter.Consider a network of n parties, where an adversary has compromised the secret keys of up to t c honest parties and, in addition, fully controls the behavior of up to t a other parties. We show that for any fixed t c  > 0, and any fixed t a , there exists an efficient protocol for broadcast if and only if 2t a  + min (t a , t c ) < n. (When t c  = 0, standard results imply feasibility.) We also show that if t c , t a are not fixed, but are only guaranteed to satisfy the bound above, then broadcast is impossible to achieve except for a few specific values of n; for these “exceptional” values of n, we demonstrate a broadcast protocol. Taken together, our results give a complete characterization of this problem.

Bounds on the efficiency of black-box commitment schemes - Horvitz,Omer; Katz, Jonathan (Theoretical Computer Science, 2010)
Constructions of cryptographic primitives based on general assumptions (e.g., one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) cryptographic constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. Our bounds hold in an extension of the Impagliazzo–Rudich model: we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a statistically-binding commitment scheme could be constructed “from scratch”).
Keywords: Commitment schemes; cryptography

Brief announcement: decentralized network bandwidth prediction - Song,S.; Keleher,P.; Bhattacharjee, Bobby; Sussman, Alan (Distributed Computing, 2010)
Distributed applications can often benefit from knowledge of the bandwidth between hosts, without performing measurements between all host pairs. For example, if a peer-to-peer (P2P) computational grid system predicts pairwise bandwidth between all nodes in the system, that information could increase overall system performance by finding high-bandwidth nodes to store large scientific input or output datasets. Another possible beneficiary is a P2P online game, which can provide users a seamless gaming experience by selecting a coordinator node that has high-bandwidth connections to the players in a game region.

Broadcasting on networks of workstations - Khuller, Samir; Kim,Y. A; Wan,Y. C.J (Algorithmica, 2010)
Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message to a machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C(≥1) time units. The clusters may have arbitrary sizes. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending node does not block for C time units when the message is in transit.

Buffer management for multi-application image processing on multi-core platforms: Analysis and case study - Ko,Dong-Ik; Won, N.; Bhattacharyya, Shuvra S. (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
Due to the limited amounts of on-chip memory, large volumes of data, and performance and power consumption overhead associated with interprocessor communication, efficient management of buffer memory is critical to multi-core image processing. To address this problem, this paper develops new modeling and analysis techniques based on dataflow representations, and demonstrates these techniques on a multi-core implementation case study involving multiple, concurrently-executing image processing applications. Our techniques are based on careful representation and exploitation of frame- or block-based operations, which involve repeated invocations of the same computations across regularly- arranged subsets of data. Using these new approaches to manage block-based image data, this paper demonstrates methods to analyze synchronization overhead and FIFO buffer sizes when mapping image processing applications onto heterogeneous, multi core architectures.
Keywords: block-based image data; buffer memory management; buffer storage; concurrently-executing image processing application; data flow computing; data flow representation; data subset; Dataflow; Digital signal processing; Energy consumption; Energy management; Engineering management; FIFO buffer sizes; Hardware; Image analysis; IMAGE PROCESSING; image processing application; image representation; interprocessor communication; memory architecture; Memory management; multiapplication image processing; multicore image processing; multiprocessing; on-chip memory; power consumption; power consumption overhead; Runtime; scheduling; set theory; shared memory; storage management chips; synchronization overhead

Cellular traffic offloading through opportunistic communications: a case study - Han,Bo; Hui,Pan; Kumar,V. S. Anil; Marathe,Madhav V.; Guanhong Pei; Srinivasan, Aravind (Proceedings of the 5th ACM workshop on Challenged networks, 2010)
Due to the increasing popularity of various applications for smartphones, 3G networks are currently overloaded by mobile data traffic. Offloading cellular traffic through opportunistic communications is a promising solution to partially solve this problem, because there is no monetary cost for it. As a case study, we investigate the target-set selection problem for information delivery in the emerging Mobile Social Networks (MoSoNets). We propose to exploit opportunistic communications to facilitate the information dissemination and thus reduce the amount of cellular traffic. In particular, we study how to select the target set with only k users, such that we can minimize the cellular data traffic. In this scenario, initially the content service providers deliver information over cellular networks to only users in the target set. Then through opportunistic communications, target-users will further propagate the information among all the subscribed users. Finally, service providers will send the information to users who fail to receive it before the delivery deadline (i.e., delay-tolerance threshold). We propose three algorithms, called Greedy, Heuristic, and Random, for this problem and evaluate their performance through an extensive trace-driven simulation study. The simulation results verify the efficiency of these algorithms for both synthetic and real-world mobility traces. For example, the Heuristic algorithm can offload cellular traffic by up to 73.66% for a real-world mobility trace.
Keywords: cellular traffic offloading; mobile social networks; opportunistic communications; target-set selection

Coherent turbulent motions in a Mach 3 boundary layer - Beekman,I.; Kan,Y. C; Priebe,S.; Martin, M.P (Bulletin of the American Physical Society, 2010)

Common Mode Analysis of Ethernet Transformers - Bowen,D.; Mayergoyz, Issak D; Krafft,C.; Kroop,D. (Magnetics Letters, IEEE, 2010)
In this letter, a distributed model for Ethernet transformers subject to common mode signals is developed.Explicit formulas for transfer functions are derived and illustrated by numerical examples.

Computational Approaches for Genome Assembly Validation - Choi,J.H.; Tang,H.; Kim,S.; Pop, Mihai (Biological Data Mining, 2010)

On Computing Compression Trees for Data Collection in Wireless Sensor Networks - Li,Jian; Deshpande, Amol; Khuller, Samir (2010 Proceedings IEEE INFOCOM, 2010)
We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
Keywords: Approximation algorithms; Base stations; Communications Society; Computer networks; Computer science; computing compression trees; Costs; data collection; Data communication; data compression; designing algorithms; Educational institutions; Entropy; graph concept; Monitoring; Protocols; trees (mathematics); weakly connected dominating sets; Wireless sensor networks

Conversion of viable but nonculturable Vibrio cholerae to the culturable state by co‐culture with eukaryotic cells - Senoh,Mitsutoshi; Ghosh‐Banerjee,Jayeeta; Ramamurthy,Thandavarayan; Hamabata,Takashi; Kurakawa,Takashi; Takeda,Makoto; Rita R Colwell; Nair,G. Balakrish; Takeda,Yoshifumi (Microbiology and Immunology, 2010)
VBNC Vibrio cholerae O139 VC-280 obtained by incubation in 1% solution of artificial sea water IO at 4°C for 74 days converted to the culturable state when co-cultured with CHO cells. Other eukaryotic cell lines, including HT-29, Caco-2, T84, HeLa, and Intestine 407, also supported conversion of VBNC cells to the culturable state. Conversion of VBNC V. cholerae O1 N16961 and V. cholerae O139 VC-280/pG13 to the culturable state, under the same conditions, was also confirmed. When VBNC V. cholerae O139 VC-280 was incubated in 1% IO at 4°C for up to 91 days, the number of cells converted by co-culture with CHO cells declined with each additional day of incubation and after 91 days conversion was not observed.
Keywords: conversion to culturability; co‐culture; eukaryotic cell; viable but nonculturable (VBNC) Vibrio cholerae

Decentralized dynamic scheduling across heterogeneous multi-core desktop grids - Jaehwan Lee; Keleher,P.; Sussman, Alan (2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010)
The recent advent of multi-core computing environments increases both the heterogeneity and complexity of managing desktop grid resources, making efficient load balancing challenging even for a centralized manager. Even with good initial job assignments, dynamic scheduling is still needed to adapt to dynamic environments, as well as for applications whose running times are not known a priori. In this paper, we propose new decentralized scheduling schemes that backfill jobs locally and dynamically migrate waiting jobs across nodes to leverage residual resources, while guaranteeing bounded waiting times for all jobs. The methods attempt to maximize total throughput while balancing load across available grid resources. Experimental results via simulation show that our scheduling scheme has performance competitive with an online centralized scheduler.
Keywords: backfill jobs; bounded waiting time; Computer science; decentralized dynamic scheduling; desktop grid resource management; Dynamic scheduling; Educational institutions; Environmental management; grid computing; heterogeneous multicore desktop grid; job assignment; job migration; load balancing; Load management; multicore computing environment; Peer to peer computing; Processor scheduling; residual resources; resource allocation; Resource management; scheduling; Scheduling algorithm; Throughput

Decoupling policy from configuration in campus and enterprise networks - Feamster, Nick; Nayak,A.; Kim,Hyojoon; Clark,R.; Mundada,Y.; Ramachandran,A.; bin Tariq,M. (Local and Metropolitan Area Networks (LANMAN), 2010 17th IEEE Workshop on, 2010)
This paper surveys our ongoing work on the use of software-defined networking to simplify two acute policy problems in campus and enterprise network operations: access control and information flow control. We describe how the current coupling of high-level policy with low-level configuration makes these problems challenging today. We describe the specific policy problems faced by campus and enterprise network operators; illustrate our approach, which leverages recent trends in separating the network's #x201C;control plane #x201D; from the data plane; and show how this approach can be applied to simplify these two enterprise network management tasks. We also describe our ongoing deployment efforts to build a campus network testbed where trial designs can be deployed and evaluated. We close with a summary of current and future research challenges for solving challenges within enterprise networks within the context of this new paradigm.
Keywords: Access control; Business communication; campus network; decoupling policy; enterprise network management tasks; enterprise network operator; information flow control; software defined network; software radio; telecommunication network management; telecommunication security

Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs - Saha,B.; Hoch,A.; Khuller, Samir; Raschid, Louiqa; Zhang,X. N (Research in Computational Molecular Biology, 2010)
In this paper, we focus on finding complex annotation patterns representing novel and interesting hypotheses from gene annotation data. We define a generalization of the densest subgraph problem by adding an additional distance restriction (defined by a separate metric) to the nodes of the subgraph. We show that while this generalization makes the problem NP-hard for arbitrary metrics, when the metric comes from the distance metric of a tree, or an interval graph, the problem can be solved optimally in polynomial time. We also show that the densest subgraph problem with a specified subset of vertices that have to be included in the solution can be solved optimally in polynomial time. In addition, we consider other extensions when not just one solution needs to be found, but we wish to list all subgraphs of almost maximum density as well. We apply this method to a dataset of genes and their annotations obtained from The Arabidopsis Information Resource (TAIR). A user evaluation confirms that the patterns found in the distance restricted densest subgraph for a dataset of photomorphogenesis genes are indeed validated in the literature; a control dataset validates that these are not random patterns. Interestingly, the complex annotation patterns potentially lead to new and as yet unknown hypotheses. We perform experiments to determine the properties of the dense subgraphs, as we vary parameters, including the number of genes and the distance.

Developing Autonomy for Unmanned Surface Vehicles by Using Virtual Environments - Kavetsky,R.; Gupta,S.K. (ENERGETICS TECHNOLOGY CENTER INC LA PLATA MD, 2010)
We address the problem of automated synthesis of an action selection policy for an unmanned vehicle operating in an environment with a deceptive adversary. We introduce a new synthesis approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. Our focus is specifically on automated synthesis of a policy used for blocking the advancement of an intruder boat toward a valuable target. The USV must generate specific maneuvers for blocking. The intruder is human competitive and exhibits a deceptive behavior so that the USV cannot exploit regularity in its attacking behavior. We compared the performance of a hand coded USVs blocking policy to the performance of a policy that was automatically synthesized. Our results show that the performance of the automatically generated USVs policy exceed the performance of the hand coded policy and thus demonstrates the feasibility of the proposed approach.

Digital Signatures - Yung,Moti; Katz, Jonathan (Springer, 2010)
Digital Signatures is the first comprehensive account of the theoretical principles and techniques used in the design of provably secure signature schemes. In addition to providing the reader with a better understanding of the security guarantees provided by digital signatures, the book also contains full descriptions and detailed proofs for essentially all known secure signature schemes in the cryptographic literature. A valuable reference for students, professors, and researchers, Digital Signature Schemes can be used for self-study, as a supplement to a course on theoretical cryptography, or as a textbook in a graduate-level seminar.
Keywords: Computers / Computer Science; Computers / Hardware / General; Computers / Information Theory; Computers / Networking / Hardware; Computers / Security / General; Technology & Engineering / Telecommunications

Dynamic and Multidimensional Dataflow Graphs - Bhattacharyya, Shuvra S.; Deprettere, Ed F.; Keinert, Joachim (Handbook of Signal Processing Systems, 2010)
Much of the work to date on dataflow models for signal processing system design has focused decidable dataflow models that are best suited for onedimensional signal processing. In this chapter, we review more general dataflow modeling techniques that are targeted to applications that include multidimensional signal processing and dynamic dataflow behavior. As dataflow techniques are applied to signal processing systems that are more complex, and demand increasing degrees of agility and flexibility, these classes of more general dataflow models are of correspondingly increasing interest. We begin with a discussion of two dataflow modeling techniques - multi-dimensional synchronous dataflow and windowed dataflow - that are targeted towards multidimensional signal processing applications. We then provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. Our coverage of dynamic dataflowmodels in this chapter includes Boolean dataflow, the stream-based function model, CAL, parameterized dataflow, and enable-invoke dataflow.
Keywords: Communications Engineering, Networks; Computer Systems Organization and Communication Networks; Processor Architectures; Signal, Image and Speech Processing

Effect on Human Cells of Environmental Vibrio Parahaemolyticus Strains Carrying Type III Secretion System 2 - Caburlotto,Greta; Lleò,Maria M.; Hilton,Tamara; Huq,Anwar; Rita R Colwell; Kaper,James B. (Infection and ImmunityInfect. Immun., 2010)
Vibrio parahaemolyticus is an inhabitant of estuarine and marine environments that causes seafood-borne gastroenteritis worldwide. Recently, a type 3 secretion system (T3SS2) able to secrete and translocate virulence factors into the eukaryotic cell has been identified in a pathogenicity island (VP-PAI) located on the smaller chromosome. These virulence-related genes have previously been detected only in clinical strains. Classical virulence genes for this species (tdh, trh) are rarely detected in environmental strains, which are usually considered to lack virulence potential. However, during screening of a collection of environmental V. parahaemolyticus isolates obtained in the North Adriatic Sea in Italy, a number of marine strains carrying virulence-related genes, including genes involved in the T3SS2, were detected. In this study, we investigated the pathogenic potential of these marine V. parahaemolyticus strains by studying their adherence ability, their cytotoxicity, their effect on zonula occludin protein 1 (ZO-1) of the tight junctions, and their effect on transepithelial resistance (TER) in infected Caco-2 cells. By performing a reverse transcription-PCR, we also tested the expression of the T3SS2 genes vopT and vopB2, encoding an effector and a translocon protein, respectively. Our results indicate that, similarly to clinical strains, marine V. parahaemolyticus strains carrying vopT and vopB2 and that other genes included in the VP-PAI are capable of adhering to human cells and of causing cytoskeletal disruption and loss of membrane integrity in infected cells. On the basis of data presented here, environmental V. parahaemolyticus strains should be included in coastal water surveillance plans, as they may represent a risk for human health.

Efficient rational secret sharing in standard communication networks - Fuchsbauer,G.; Katz, Jonathan; Naccache,D. (Theory of Cryptography, 2010)
We propose a new methodology for rational secret sharing leading to various instantiations (in both the two-party and multi-party settings) that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks.We also propose new equilibrium notions (namely, computational versions of strict Nash equilibrium and stability with respect to trembles) and prove that our protocols satisfy them. These notions guarantee, roughly speaking, that at each point in the protocol there is a unique legal message a party can send. This, in turn, ensures that protocol messages cannot be used as subliminal channels, something achieved in prior work only by making strong assumptions on the communication network.

Efficient static buffering to guarantee throughput-optimal FPGA implementation of synchronous dataflow graphs - Kee, Hojin; Bhattacharyya, Shuvra S.; Kornerup, J. (2010 International Conference on Embedded Computer Systems (SAMOS), 2010)
When designing DSP applications for implementation on field programmable gate arrays (FPGAs), it is often important to minimize consumption of limited FPGA resources while satisfying real-time performance constraints. In this paper, we develop efficient techniques to determine dataflow graph buffer sizes that guarantee throughput-optimal execution when mapping synchronous dataflow (SDF) representations of DSP applications onto FPGAs. Our techniques are based on a novel two-actor SDF graph Model (TASM), which efficiently captures the behavior and costs associated with SDF graph edges (flow-graph connections). With our proposed techniques, designers can automatically generate upper bounds on SDF graph buffer distributions that realize maximum achievable throughput performance for the corresponding applications. Furthermore, our proposed technique is characterized by low polynomial time complexity, which is useful for rapid prototyping in DSP system design.
Keywords: buffer memory; circuit complexity; Complexity theory; Computational modeling; data flow graphs; Digital signal processing; digital signal processing chips; DSP system design; efficient static buffering; Field programmable gate arrays; FPGA; graph buffer distributions; integrated circuit design; low polynomial time complexity; Random access memory; Schedules; SDF graph edges; Signal processing systems; Synchronous dataflow; synchronous dataflow graph mapping; Throughput; throughput-optimal execution; throughput-optimal FPGA implementation; two-actor SDF graph model; upper bounds

Electromagnetic Modeling of Ethernet Transformers - Bowen,D.; Mayergoyz, Issak D; Krafft,C. (Magnetics, IEEE Transactions on, 2010)
The unique features of Ethernet transformers are reviewed, and novel testing techniques for identification of lumped parameters of equivalent circuits are presented. To account for the distributed nature of the cross-winding and intrawinding capacitances, novel distributed models for electromagnetic analysis of Ethernet transformers are presented.
Keywords: analysis; electromagnetic; area; capacitances; lumped; circuits; ethernet; circuits; local; cross-winding; distributed; modeling; equivalent; models; electromagnetic; networks; lumped; networks; transformer; parameter; parameters; novel; techniques; capacitance; equivalent; Testing; transformers; intrawinding; windings; transformers

Emergence of cooperative societies in evolutionary games - Cheng,Kan-Leung; Zuckerman,Inon; Kuter,Ugur; Nau, Dana S. (ACM, 2010)
We utilize evolutionary game theory to study the evolution of cooperative societies and the behaviors of individual agents (i.e., players) in it. We present a novel player model based upon empirical evidence from the social and behavioral sciences, stating that: (1) an individual's behavior may often be motivated not only by self-interest but also by the consequences for the others, and (2) individuals vary in their interpersonal social tendencies, which reflect stable personal orientations that influence their choices. Alongside the formal player model we provide an analysis that considers possible interactions between different types of individuals. We present series of evolutionary simulations that ratify previous findings on evolution of cooperation, and provide new insights on the evolutionary process of cooperative behavior in a society as well as on the emergence of cooperative societies. Our main experimental result demonstrate that in contrast to previous common knowledge, increasing the value of mutual Reward or increasing mutual Punishment in the Prisoner's dilemma game do not result in the same type of cooperative society: while increasing R does result in a more cooperative society, increasing P does not.
Keywords: evolutionary game theory; social orientations

Energy efficient scheduling via partial shutdown - Khuller, Samir; Li,Jian; Saha,Barna (Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010)
Motivated by issues of saving energy in data centers we define a collection of new problems referred to as "machine activation" problems. The central framework we introduce considers a collection of m machines (unrelated or related) with each machine i having an activation cost of ai. There is also a collection of n jobs that need to be performed, and pi, j is the processing time of job j on machine i. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of A - we would like to select a subset S of the machines to activate with total cost a(S) ≤ A and find a schedule for the n jobs on the machines in S minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine i has activation cost ai and speed si, and the processing time of job j on machine i is pi, j = pjsi, where pj is the processing requirement of job j. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan T and activation cost A then we can obtain a schedule with makespan (2 + ε)T and activation cost 2(1 + 1/ε)(ln n/OPT + 1)A, for any ε > 0. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. In addition, we present a greedy algorithm which only works for the basic version and yields a makespan of 2T and an activation cost A(1 + ln n). For the uniformly related parallel machine sceduling problem, we develop a polynomial time approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most A and the makespan is at most (1 + ε)T for any ε > 0. For the special case of m identical speed machines, the machine activation problem is trivial, since the cheapest subset of k machines is always the best choice if the optimal solution activates k machines. In addition, we consider the case whem some jobs can be dropped (and are treated as outliers).

Energy-driven distribution of signal processing applications across wireless sensor networks - Chung-Ching Shen; Plishker, William L.; Ko,Dong-Ik; Bhattacharyya, Shuvra S.; Goldsman,Neil (ACM Trans. Sen. Netw., 2010)
Wireless sensor network (WSN) applications have been studied extensively in recent years. Such applications involve resource-limited embedded sensor nodes that have small size and low power requirements. Based on the need for extended network lifetimes in WSNs in terms of energy use, the energy efficiency of computation and communication operations in the sensor nodes becomes critical. Digital Signal Processing (DSP) applications typically require intensive data processing operations and as a result are difficult to implement directly in resource-limited WSNs. In this article, we present a novel design methodology for modeling and implementing computationally intensive DSP applications applied to wireless sensor networks. This methodology explores efficient modeling techniques for DSP applications, including data sensing and processing; derives formulations of Energy-Driven Partitioning (EDP) for distributing such applications across wireless sensor networks; and develops efficient heuristic algorithms for finding partitioning results that maximize the network lifetime. To address such an energy-driven partitioning problem, this article provides a new way of aggregating data and reducing communication traffic among nodes based on application analysis. By considering low data token delivery points and the distribution of computation in the application, our approach finds energy-efficient trade-offs between data communication and computation.
Keywords: DSP; Energy efficiency; network lifetime; Speech recognition; Wireless sensor networks

Evolutionary framework for Lepidoptera model systems - Roe,A.; Weller,S.; Baixeras,J.; Brown,J. W; Cummings, Michael P.; Davis,DR; Horak,M; Kawahara,A. Y; Mitter,C; Parr,C.S.; Regier,J. C; Rubinoff,D; et al. (Genetics and Molecular Biology of LepidopteraGenetics and Molecular Biology of Lepidoptera, 2010)
“Model systems” are specific organisms upon which detailed studies have been conducted examining a fundamental biological question. If the studies are robust, their results can be extrapolated among an array of organisms that possess features in common with the subject organism. The true power of model systems lies in the ability to extrapolate these details across larger groups of organisms. In order to generalize these results, comparative studies are essential and require that model systems be placed into their evolutionary or phylogenetic context. This chapter examines model systems in the insect order Lepidoptera from the perspective of several different superfamilies. Historically, many species of Lepidoptera have been essential in the development of invaluable model systems in the fields of development biology, genetics, molecular biology, physiology, co-evolution, population dynamics, and ecology.

Exploring Biological Network Dynamics with Ensembles of Graph Partitions - Navlakha,S.; Kingsford, Carl (Proceedings of the PSB Pacific Symposium on Biocomputing, 2010)

Finding Biologically Accurate Clusterings in Hierarchical Tree Decompositions Using the Variation of Information - Navlakha,Saket; White,James; Nagarajan,Niranjan; Pop, Mihai; Kingsford, Carl (Journal of Computational Biology, 2010)
Hierarchical clustering is a popular method for grouping together similar elements based on a distance measure between them. In many cases, annotations for some elements are known beforehand, which can aid the clustering process. We present a novel approach for decomposing a hierarchical clustering into the clusters that optimally match a set of known annotations, as measured by the variation of information metric. Our approach is general and does not require the user to enter the number of clusters desired. We apply it to two biological domains: finding protein complexes within protein interaction networks and identifying species within metagenomic DNA samples. For these two applications, we test the quality of our clusters by using them to predict complex and species membership, respectively. We find that our approach generally outperforms the commonly used heuristic methods.

FPGA-based design and implementation of the 3GPP-LTE physical layer using parameterized synchronous dataflow techniques - Kee, Hojin; Bhattacharyya, Shuvra S.; Wong, I.; Yong Rao (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
Synchronous dataflow (SDF) is an ubiquitous dataflow model of computation that has been studied extensively for efficient simulation and software synthesis of DSP applications. In recent years, parameterized SDF (PSDF) has evolved as a useful framework for modeling SDF graphs in which arbitrary parameters can be changed dynamically. However, the potential to enable efficient hardware synthesis has been treated relatively sparsely in the literature for SDF and even more so for the newer, more general PSDF model. This paper investigates efficient FPGA-based design and implementation of the physical layer for 3GPP-Long Term Evolution (LTE), a next generation cellular standard. To capture the SDF behavior of the functional core of LTE along with higher level dynamics in the standard, we use a novel PSDF-based FPGA architecture framework. We implement our PSDF-based, LTE design framework using National Instrument's LabVIEW FPGA, a recently-introduced commercial platform for reconfigurable hardware implementation. We show that our framework can effectively model the dynamics of the LTE protocol, while also providing a synthesis framework for efficient FPGA implementation.
Keywords: 3G mobile communication; 3GPP-long term evolution; 3GPP-LTE physical layer; 4G communication systems; Computational modeling; data flow analysis; data flow graphs; Dataflow modeling; Digital signal processing; DSP applications; Field programmable gate arrays; FPGA architecture framework; FPGA implementation; FPGA-based design; Hardware; hardware synthesis; Instruments; LabVIEW FPGA; Logic Design; LTE; next generation cellular standard; parameterized synchronous data flow technique; Pervasive computing; Physical layer; Physics computing; Production; PSDF graph; reconfigurable hardware implementation; Runtime; software synthesis; Ubiquitous Computing; ubiquitous data flow model

GasSense: Appliance-Level, Single-Point Sensing of Gas Activity in the Home - Cohn,Gabe; Gupta,Sidhant; Jon Froehlich; Larson,Eric; Patel,Shwetak (Pervasive Computing, 2010)
This paper presents GasSense, a low-cost, single-point sensing solution for automatically identifying gas use down to its source (e.g., water heater, furnace, fireplace). This work adds a complementary sensing solution to the growing body of work in infrastructure-mediated sensing. GasSense analyzes the acoustic response of a home’s government mandated gas regulator, which provides the unique capability of sensing both the individual appliance at which gas is currently being consumed as well as an estimate of the amount of gas flow. Our approach provides a number of appealing features including the ability to be easily and safely installed without the need of a professional. We deployed our solution in nine different homes and initial results show that GasSense has an average accuracy of 95.2% in identifying individual appliance usage.

General-purpose vs. gpu: Comparison of many-cores on irregular workloads - Caragea,G.C.; Keceli,F.; Tzannes,A.; Vishkin, Uzi (Proceedings of the Second Usenix Workshop on Hot Topics in Parallelism, 2010)
XMT1 is a general-purpose many-core parallel architec-ture. The foremost design objective for XMT was to meet the highest standards for ease of parallel programming. GPUs, on the other hand, have acquired a strong reputa- tion on performance, sometimes at the expense of ease- of-programming. The current paper presents a perfor- mance comparison on diverse workloads between XMT and an NVIDIA CUDA-enabled GPU. Configured with roughly the same amount of chip resources as the GPU, XMT achieves an average speedup of 6.05x on irregu- lar applications, while incurring an average slowdown of 2.07x on regular ones. Namely, XMT comes ahead for significant applications without having to pay a (possibly worthwhile) price for easier programming. This surpris- ing result suggests a yet untapped opportunity: A high- performance easy-to-program general-purpose 1000-core computer.

A graph-theoretic approach to protect static and moving targets from adversaries - Dickerson,J. P.; Simari,G. I; V.S. Subrahmanian; Kraus,Sarit (Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1, 2010)
The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.
Keywords: adversarial reasoning; agent systems; game theory

A group signature scheme from lattice assumptions - Gordon,S.; Katz, Jonathan; Vaikuntanathan,V. (Advances in Cryptology-ASIACRYPT 2010, 2010)
Group signature schemes allow users to sign messages on behalf of a group while (1) maintaining anonymity (within that group) with respect to an outside observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assumption), in the random oracle model. Towards our goal, we construct a new algorithm for sampling a basis for an orthogonal lattice, together with a trapdoor, that may be of independent interest.

Handwritten Arabic text line segmentation using affinity propagation - Kumar,Jayant; Abd-Almageed, Wael; Kang,Le; David Doermann (Proceedings of the 9th IAPR International Workshop on Document Analysis Systems, 2010)
In this paper, we present a novel graph-based method for extracting handwritten text lines in monochromatic Arabic document images. Our approach consists of two steps - Coarse text line estimation using primary components which define the line and assignment of diacritic components which are more difficult to associate with a given line. We first estimate local orientation at each primary component to build a sparse similarity graph. We then, use a shortest path algorithm to compute similarities between non-neighboring components. From this graph, we obtain coarse text lines using two estimates obtained from Affinity propagation and Breadth-first search. In the second step, we assign secondary components to each text line. The proposed method is very fast and robust to non-uniform skew and character size variations, normally present in handwritten text lines. We evaluate our method using a pixel-matching criteria, and report 96% accuracy on a dataset of 125 Arabic document images. We also present a proximity analysis on datasets generated by artificially decreasing the spacings between text lines to demonstrate the robustness of our approach.
Keywords: affinity propagation; arabic; arabic documents; breadth-first search; clustering; dijkstra's shortest path algorithm; handwritten documents; line detection; text line segmentation

Hopx and Hdac2 Interact to Modulate Gata4 Acetylation and Embryonic Cardiac Myocyte Proliferation - Trivedi,Chinmay M.; Zhu,Wenting; Wang,Qiaohong; Jia,Cheng; Kee,Hae Jin; Li,Li; Hannenhalli, Sridhar; Epstein,Jonathan A. (Developmental Cell, 2010)
SummaryRegulation of chromatin structure via histone modification has recently received intense attention. Here, we demonstrate that the chromatin-modifying enzyme histone deacetylase 2 (Hdac2) functions with a small homeodomain factor, Hopx, to mediate deacetylation of Gata4, which is expressed by cardiac progenitor cells and plays critical roles in the regulation of cardiogenesis. In the absence of Hopx and Hdac2 in mouse embryos, Gata4 hyperacetylation is associated with a marked increase in cardiac myocyte proliferation, upregulation of Gata4 target genes, and perinatal lethality. Hdac2 physically interacts with Gata4, and this interaction is stabilized by Hopx. The ability of Gata4 to transactivate cell cycle genes is impaired by Hopx/Hdac2-mediated deacetylation, and this effect is abrogated by loss of Hdac2-Gata4 interaction. These results suggest that Gata4 is a nonhistone target of Hdac2-mediated deacetylation and that Hdac2, Hopx, and Gata4 coordinately regulate cardiac myocyte proliferation during embryonic development.

Identification of Pathogenic Vibrio Species by Multilocus PCR-Electrospray Ionization Mass Spectrometry and Its Application to Aquatic Environments of the Former Soviet Republic of Georgia - Whitehouse,Chris A.; Baldwin,Carson; Sampath,Rangarajan; Blyn,Lawrence B.; Melton,Rachael; Li,Feng; Hall,Thomas A.; Harpin,Vanessa; Matthews,Heather; Tediashvili,Marina; Jaiani,Ekaterina; Kokashvili,Tamar; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2010)
The Ibis T5000 is a novel diagnostic platform that couples PCR and mass spectrometry. In this study, we developed an assay that can identify all known pathogenic Vibrio species and field-tested it using natural water samples from both freshwater lakes and the Georgian coastal zone of the Black Sea. Of the 278 total water samples screened, 9 different Vibrio species were detected, 114 (41%) samples were positive for V. cholerae, and 5 (0.8%) samples were positive for the cholera toxin A gene (ctxA). All ctxA-positive samples were from two freshwater lakes, and no ctxA-positive samples from any of the Black Sea sites were detected.

Illusory motion due to causal time filtering - Fermüller, Cornelia; Ji,H.; Kitaoka,A. (Vision research, 2010)

Improving translation via targeted paraphrasing - Resnik, Philip; Buzek,O.; Hu,C.; Kronrod,Y.; Quinn,A.; Bederson, Benjamin B. (Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010)

Insights into head-related transfer function: Spatial dimensionality and continuous representation - Zhang,Wen; Abhayapala,Thushara D.; Kennedy,Rodney A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2010)
This paper studies head-related transfer function (HRTF) sampling and synthesis in a three-dimensional auditory scene based on a general modal decomposition of the HRTF in all frequency-range-angle domains. The main finding is that the HRTF decomposition with the derived spatial basis function modes can be well approximated by a finite number, which is defined as the spatial dimensionality of the HRTF. The dimensionality determines the minimum number of parameters to represent the HRTF corresponding to all directions and also the required spatial resolution in HRTF measurement. The general model is further developed to a continuous HRTF representation, in which the normalized spatial modes can achieve HRTF near-field and far-field representations in one formulation. The remaining HRTF spectral components are compactly represented using a Fourier spherical Bessel series, where the aim is to generate the HRTF with much higher spectral resolution in fewer parameters from typical measurements, which usually have limited spectral resolution constrained by sampling conditions. A low-computation algorithm is developed to obtain the model coefficients from the existing measurements. The HRTF synthesis using the proposed model is validated by three sets of data: (i) synthetic HRTFs from the spherical head model, (ii) the MIT KEMAR (Knowles Electronics Mannequin for Acoustics Research) data, and (iii) 45-subject CIPIC HRTF measurements.
Keywords: acoustic signal processing; Bessel functions; Fourier series; hearing; Transfer functions