Evaluation of information retrieval for E-discovery - Oard, Douglas; Baron,Jason R.; Hedin,Bruce; Lewis,David D.; Tomlinson,Stephen (Artificial Intelligence and Law, 2010)

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.

From bowling alone to tweeting together: technology-mediated social participation - Hochheiser,H.; Shneiderman, Ben (Interactions, 2010)

A general framework for efficient geographic routing in wireless networks - Lee,Seungjoon; Bhattacharjee, Bobby; Banerjee,Suman; Han,Bo (Computer Networks, 2010)
We propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic routing, NADV enables an adaptive and efficient cost-aware routing strategy. Depending on the objective or message priority, applications can use the NADV framework to minimize various types of link cost.We present efficient methods for link cost estimation and perform detailed experiments in simulated environments. Our results show that NADV outperforms current schemes in many aspects: for example, in high noise environments with frequent packet losses, the use of NADV leads to 81% higher delivery ratio. When compared to centralized routing under certain settings, geographic routing using NADV finds paths whose cost is close to the optimum. We also conducted experiments in Emulab testbed and the results demonstrate that our proposed approach performs well in practice.
Keywords: Geographic routing; Link cost estimation; Routing metric; Wireless multihop networks

Genetic and Physiological Activation of Osmosensitive Gene Expression Mimics Transcriptional Signatures of Pathogen Infection in C. elegans - Rohlfing,Anne-Katrin; Miteva,Yana; Hannenhalli, Sridhar; Lamitina,Todd (PLoS ONEPLoS ONE, 2010)
The soil-dwelling nematode C. elegans is a powerful system for comparative molecular analyses of environmental stress response mechanisms. Infection of worms with bacterial and fungal pathogens causes the activation of well-characterized innate immune transcriptional programs in pathogen-exposed hypodermal and intestinal tissues. However, the pathophysiological events that drive such transcriptional responses are not understood. Here, we show that infection-activated transcriptional responses are, in large part, recapitulated by either physiological or genetic activation of the osmotic stress response. Microarray profiling of wild type worms exposed to non-lethal hypertonicity identified a suite of genes that were also regulated by infection. Expression profiles of five different osmotic stress resistant (osr) mutants under isotonic conditions reiterated the wild type transcriptional response to osmotic stress and also showed substantial similarity to infection-induced gene expression under isotonic conditions. Computational, transgenic, and functional approaches revealed that two GATA transcription factors previously implicated in infection-induced transcriptional responses, elt-2 and elt-3, are also essential for coordinated tissue-specific activation of osmosensitive gene expression and promote survival under osmotically stressful conditions. Together, our data suggest infection and osmotic adaptation share previously unappreciated transcriptional similarities which might be controlled via regulation of tissue-specific GATA transcription factors.

Genome Sequence of Hybrid Vibrio Cholerae O1 MJ-1236, B-33, and CIRS101 and Comparative Genomics with V. Cholerae - Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Haley,Bradd; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Detter,J. Chris; Han,Cliff S.; Chertkov,Olga; Challacombe,Jean; Huq,Anwar; et al. (Journal of BacteriologyJ. Bacteriol., 2010)
The genomes of Vibrio cholerae O1 Matlab variant MJ-1236, Mozambique O1 El Tor variant B33, and altered O1 El Tor CIRS101 were sequenced. All three strains were found to belong to the phylocore group 1 clade of V. cholerae, which includes the 7th-pandemic O1 El Tor and serogroup O139 isolates, despite displaying certain characteristics of the classical biotype. All three strains were found to harbor a hybrid variant of CTXΦ and an integrative conjugative element (ICE), leading to their establishment as successful clinical clones and the displacement of prototypical O1 El Tor. The absence of strain- and group-specific genomic islands, some of which appear to be prophages and phage-like elements, seems to be the most likely factor in the recent establishment of dominance of V. cholerae CIRS101 over the other two hybrid strains.

GPUML: Graphical processors for speeding up kernel machines - Srinivasan,B.V.; Hu,Q.; Duraiswami, Ramani (Workshop on High Performance Analytics-Algorithms, Implementations, and Applications, 2010)
Algorithms based on kernel methods play a central rolein statistical machine learning. At their core are a num- ber of linear algebra operations on matrices of kernel functions which take as arguments the training and test- ing data. These range from the simple matrix-vector product, to more complex matrix decompositions, and iterative formulations of these. Often the algorithms scale quadratically or cubically, both in memory and op- erational complexity, and as data sizes increase, kernel methods scale poorly. We use parallelized approaches on a multi-core graphical processor (GPU) to partially address this lack of scalability. GPUs are used to scale three different classes of problems, a simple kernel- matrix-vector product, iterative solution of linear sys- tems of kernel function and QR and Cholesky decom- position of kernel matrices. Application of these accel- erated approaches in scaling several kernel based learn- ing approaches are shown, and in each case substantial speedups are obtained. The core software is released as an open source package, GPUML.

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.

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)

Interlingual Annotation of Parallel Text Corpora: A New Framework for Annotation and Evaluation - Dorr, Bonnie J; Passonneau,Rebecca J.; Farwell,David; Green,Rebecca; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Miller,Keith J.; Mitamura,Teruko; Rambow,Owen; Siddharthan,Advaith (Natural Language Engineering, 2010)
This paper focuses on an important step in the creation of a system of meaning representation and the development of semantically annotated parallel corpora, for use in applications such as machine translation, question answering, text summarization, and information retrieval. The work described below constitutes the first effort of any kind to annotate multiple translations of foreign-language texts with interlingual content. Three levels of representation are introduced: deep syntactic dependencies (IL0), intermediate semantic representations (IL1), and a normalized representation that unifies conversives, nonliteral language, and paraphrase (IL2). The resulting annotated, multilingually induced, parallel corpora will be useful as an empirical basis for a wide range of research, including the development and evaluation of interlingual NLP systems and paraphrase-extraction systems as well as a host of other research and development efforts in theoretical and applied linguistics, foreign language pedagogy, translation studies, and other related disciplines.

An Internet Wide View into DNS Lookup Patterns - Hao,S.; Feamster, Nick; Pandrangi,R. (VeriSign Labs, School of Computer Science, Georgia Tech, 2010)
This paper analyzes the DNS lookup patterns from a largeauthoritative top-level domain server and characterizes how the lookup patterns for unscrupulous domains may differ from those for legitimate domains. We examine domains for phishing attacks and spam and malware related domains, and see how these lookup patterns vary in terms of both their temporal and spatial characteristics. We find that malicious domains tend to exhibit more variance in the networks that look up these domains, and we also find that these domains become popular considerably more quickly after their initial registration time. We also note that miscreant domains ex- hibit distinct clusters, in terms to the networks that look up these domains. The distinct spatial and temporal character- istics of these domains, and their tendency to exhibit simi- lar lookup behavior, suggests that it may be possible to ulti- mately develop more effective blacklisting techniques based on these differing lookup patterns.

A Learning Approach Towards Detection and Tracking of Lane Markings - Gopalan,R.; Hong, T.; Shneier, M.; Chellapa, Rama (IEEE Transactions on Intelligent Transportation Systems, 2010)
Road scene analysis is a challenging problem that has applications in autonomous navigation of vehicles. An integral component of this system is the robust detection and tracking of lane markings. It is a hard problem primarily due to large appearance variations in lane markings caused by factors such as occlusion (traffic on the road), shadows (from objects like trees), and changing lighting conditions of the scene (transition from day to night). In this paper, we address these issues through a learning-based approach using visual inputs from a camera mounted in front of a vehicle. We propose the following: 1) a pixel-hierarchy feature descriptor to model the contextual information shared by lane markings with the surrounding road region; 2) a robust boosting algorithm to select relevant contextual features for detecting lane markings; and 3) particle filters to track the lane markings, without knowledge of vehicle speed, by assuming the lane markings to be static through the video sequence and then learning the possible road scene variations from the statistics of tracked model parameters. We investigate the effectiveness of our algorithm on challenging daylight and night-time road video sequences.
Keywords: Boosting; Context; Context modeling; Feature extraction; lane marking detection; outlier robustness; Roads; tracking and learning; Training; Vehicles

Linking Software Development and Business Strategy Through Measurement - Basili, Victor R.; Lindvall,M.; Regardie,M.; Seaman,C.; Heidrich,J.; Munch,J.; Rombach,D.; Trendowicz,A. (Computer, 2010)
The GQM+Strategies approach extends the goal/question/metric paradigm for measuring the success or failure of goals and strategies, adding enterprise-wide support for determining action on the basis of measurement results. An organization can thus integrate its measurement program across all levels.
Keywords: approach; business; aspects; software; development; organisational; engineering; GQM+Strategies; program; software; strategy; enterprise; support; measurement; wide

Maranello: practical partial packet recovery for 802.11 - Han,Bo; Schulman,Aaron; Gringoli,Francesco; Spring, Neil; Bhattacharjee, Bobby; Nava,Lorenzo; Ji,Lusheng; Lee,Seungjoon; Miller,Robert (Proceedings of the 7th USENIX conference on Networked systems design and implementation, 2010)
Partial packet recovery protocols attempt to repair corrupted packets instead of retransmitting them in their entirety. Recent approaches have used physical layer confidence estimates or additional error detection codes embedded in each transmission to identify corrupt bits, or have applied forward error correction to repair without such explicit knowledge. In contrast to these approaches, our goal is a practical design that simultaneously: (a) requires no extra bits in correct packets, (b) reduces recovery latency, except in rare instances, (c) remains compatible with existing 802.11 devices by obeying timing and backoff standards, and (d) can be incrementally deployed on widely available access points and wireless cards. In this paper, we design, implement, and evaluate Maranello, a novel partial packet recovery mechanism for 802.11. In Maranello, the receiver computes checksums over blocks in corrupt packets and bundles these checksums into a negative acknowledgment sent when the sender expects to receive an acknowledgment. The sender then retransmits only those blocks for which the checksum is incorrect, and repeats this partial retransmission until it receives an acknowledgment. Successful transmissions are not burdened by additional bits and the receiver needs not infer which bits were corrupted. We implemented Maranello using OpenFWWF (open source firmware for Broadcom wireless cards) and deployed it in a small testbed. We compare Maranello to alternative recovery protocols using a trace-driven simulation and to 802.11 using a live implementation under various channel conditions. To our knowledge, Maranello is the first partial packet recovery design to be implemented in commonly available firmware.

Method for fingerprinting multimedia content - He,Shan; M. Wu (2010)
To identify participants in collusion directed to altering a digital fingerprint embedded in multimedia content, an ECC based fingerprinting technique establishes a code symbol for each of a plurality of segments of digital data forming the multimedia content. The code symbols are concatenated to form a fingerprint signal, which is subdivided into a plurality of subsegments for each segment in the digital data. The subsegments are permuted and embedded into the digital data. When a suspicious copy of the multimedia content is discovered, the permuted fingerprint signal is extracted from the content and inversely permuted to form a test fingerprint. The identity of one of the colluders is determined by correlation with characteristics of the codeword originally assigned to the user. The determination of identity may be enhanced by the addition of group data embedded as an additional fingerprint in the digital data. Joint consideration of coding and embedding provide benefits over...

Mimosa: Mixture model of co-expression to detect modulators of regulatory interaction - Hansen,Matthew; Everett,Logan; Singh,Larry; Hannenhalli, Sridhar (Algorithms for Molecular Biology, 2010)
Functionally related genes tend to be correlated in their expression patterns across multiple conditions and/or tissue-types. Thus co-expression networks are often used to investigate functional groups of genes. In particular, when one of the genes is a transcription factor (TF), the co-expression-based interaction is interpreted, with caution, as a direct regulatory interaction. However, any particular TF, and more importantly, any particular regulatory interaction, is likely to be active only in a subset of experimental conditions. Moreover, the subset of expression samples where the regulatory interaction holds may be marked by presence or absence of a modifier gene, such as an enzyme that post-translationally modifies the TF. Such subtlety of regulatory interactions is overlooked when one computes an overall expression correlation.

Mobile data offloading in metropolitan area networks - Han,Bo; Hui,Pan; Srinivasan, Aravind (SIGMOBILE Mob. Comput. Commun. Rev., 2010)
Cellular networks, especially 3G networks, are currently overloaded with mobile data traffic. It is thus imperative to develop novel communication architectures and protocols for this problem. In this paper, we propose to exploit the delay-tolerant nature of non-realtime applications to offload mobile data traffic through opportunistic communications and WiFi networks. We argue that it is necessary for cellular network operators, WiFi service providers, and end-users to cooperate to make the offloading more effective. We also present several preliminary experiment results about the work we have been conducting, which show that it is promising to offload mobile data traffic in metropolitan area networks.

Modeling perspective using adaptor grammars - Hardisty,Eric A.; Jordan Boyd-Graber; Resnik, Philip (Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010)
Strong indications of perspective can often come from collocations of arbitrary length; for example, someone writing get the government out of my X is typically expressing a conservative rather than progressive viewpoint. However, going beyond unigram or bigram features in perspective classification gives rise to problems of data sparsity. We address this problem using nonparametric Bayesian modeling, specifically adaptor grammars (Johnson et al., 2006). We demonstrate that an adaptive naïve Bayes model captures multiword lexical usages associated with perspective, and establishes a new state-of-the-art for perspective classification results using the Bitter Lemons corpus, a collection of essays about mid-east issues from Israeli and Palestinian points of view.

Multi-Camera Tracking with Adaptive Resource Allocation - Han,B.; Joo, S.W.; Davis, Larry S. (International Journal of Computer Vision, 2010)

New Constructive Aspects of the Lovasz Local Lemma - Haeupler,B.; Saha,B.; Srinivasan, Aravind (2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010)
The Lov'asz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of ``bad'' events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emphconditional LLL-distribution – the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized ``core'' subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this.
Keywords: acyclic edge coloring; Algorithm design and analysis; Approximation algorithms; Approximation methods; computational complexity; Computer science; constant factor approximation algorithm; graph colouring; Linearity; Lovasz Local Lemma; MAX k-SAT; Monte Carlo Algorithm; Monte Carlo methods; Moser-Tardos algorithm; nonrepetitive graph coloring; output distribution; polynomial sized core subset; Polynomials; Probabilistc Method; probabilistic analysis; probabilistic logic; probability; Ramsey type graph; Sampling methods; Santa Claus Problem

Nfsight: netflow-based network awareness tool - Berthier,R.; Michel Cukier; Hiltunen,M.; Kormann,D.; Vesonder,G.; Sheleheda,D. (2010)
Network awareness is highly critical for network and se-curity administrators. It enables informed planning and management of network resources, as well as detection and a comprehensive understanding of malicious activ- ity. It requires a set of tools to efficiently collect, process, and represent network data. While many such tools al- ready exist, there is no flexible and practical solution for visualizing network activity at various granularities, and quickly gaining insights about the status of network as- sets. To address this issue, we developed Nfsight, a Net- Flow processing and visualization application designed to offer a comprehensive network awareness solution. Nfsight constructs bidirectional flows out of the unidi- rectional NetFlow flows and leverages these bidirectional flows to provide client/server identification and intrusion detection capabilities. We present in this paper the in- ternal architecture of Nfsight, the evaluation of the ser- vice, and intrusion detection algorithms. We illustrate the contributions of Nfsight through several case studies conducted by security administrators on a large univer- sity network.

Occurrence of the Vibrio cholerae seventh pandemic VSP-I island and a new variant - Grim,Christopher J.; Choi,Jinna; Jongsik Chun; Jeon,Yoon-Seong; Taviani,Elisa; Hasan,Nur A.; Haley,Bradd; Huq,Anwar; Rita R Colwell (OMICS: A Journal of Integrative Biology, 2010)

Overlap-based cell tracker - Chalfoun, J; Cardone, Antonio; Dima, A.A.; Allen, D.P.; Halter, M.W. (The Journal of Research of the National Institute of Standards and Technology, 2010)
order to facilitate the extraction of quantitative data from live cell image sets, automated image analysis methods are needed. This paper presents an introduction to the general principle of an overlap cell tracking software developed by the National Institute of Standards and Technology (NIST). This cell tracker has the ability to track cells across a set of time lapse images acquired at high rates based on the amount of overlap between cellular regions in consecutive frames. It is designed to be highly flexible, requires little user parameterization, and has a fast execution time.

Perturbing the Ubiquitin Pathway Reveals How Mitosis Is Hijacked to Denucleate and Regulate Cell Proliferation and Differentiation In Vivo - Caceres,Andrea; Shang,Fu; Wawrousek,Eric; Liu,Qing; Avidan,Orna; Cvekl,Ales; Yang,Ying; Haririnia,Aydin; Storaska,Andrew; Fushman, David; Kuszak,Jer; Dudek,Edward; et al. (PLoS ONEPLoS ONE, 2010)
BackgroundThe eye lens presents a unique opportunity to explore roles for specific molecules in cell proliferation, differentiation and development because cells remain in place throughout life and, like red blood cells and keratinocytes, they go through the most extreme differentiation, including removal of nuclei and cessation of protein synthesis. Ubiquitination controls many critical cellular processes, most of which require specific lysines on ubiquitin (Ub). Of the 7 lysines (K) least is known about effects of modification of K6. Methodology and Principal Findings We replaced K6 with tryptophan (W) because K6 is the most readily modified K and W is the most structurally similar residue to biotin. The backbone of K6W-Ub is indistinguishable from that of Wt-Ub. K6W-Ub is effectively conjugated and deconjugated but the conjugates are not degraded via the ubiquitin proteasome pathways (UPP). Expression of K6W-ubiquitin in the lens and lens cells results in accumulation of intracellular aggregates and also slows cell proliferation and the differentiation program, including expression of lens specific proteins, differentiation of epithelial cells into fibers, achieving proper fiber cell morphology, and removal of nuclei. The latter is critical for transparency, but the mechanism by which cell nuclei are removed has remained an age old enigma. This was also solved by expressing K6W-Ub. p27kip, a UPP substrate accumulates in lenses which express K6W-Ub. This precludes phosphorylation of nuclear lamin by the mitotic kinase, a prerequisite for disassembly of the nuclear membrane. Thus the nucleus remains intact and DNAseIIβ neither gains entry to the nucleus nor degrades the DNA. These results could not be obtained using chemical proteasome inhibitors that cannot be directed to specific tissues. Conclusions and Significance K6W-Ub provides a novel, genetic means to study functions of the UPP because it can be targeted to specific cells and tissues. A fully functional UPP is required to execute most stages of lens differentiation, specifically removal of cell nuclei. In the absence of a functional UPP, small aggregate prone, cataractous lenses are formed.

The pre‐seventh pandemic Vibrio cholerae BX 330286 El Tor genome: evidence for the environment as a genome reservoir - Haley,Bradd J.; Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Challacombe,Jean F.; Detter,J. Chris; Han,Cliff S.; Huq,Anwar; Nair,G. Balakrish; et al. (Environmental Microbiology Reports, 2010)
Vibrio cholerae O1 El Tor BX 330286 was isolated from a water sample in Australia in 1986, 9 years after an indigenous outbreak of cholera occurred in that region. This environmental strain encodes virulence factors highly similar to those of clinical strains, suggesting an ability to cause disease in humans. We demonstrate its high similarity in gene content and genome-wide nucleotide sequence to clinical V. cholerae strains, notably to pre-seventh pandemic O1 El Tor strains isolated in 1910 (V. cholerae NCTC 8457) and 1937 (V. cholerae MAK 757), as well as seventh pandemic strains isolated after 1960 globally. Here we demonstrate that this strain represents a transitory clone with shared characteristics between pre-seventh and seventh pandemic strains of V. cholerae. Interestingly, this strain was isolated 25 years after the beginning of the seventh pandemic, suggesting the environment as a genome reservoir in areas where cholera does not occur in sporadic, endemic or epidemic form.

Regulating the Regulators: Modulators of Transcription Factor Activity - Everett,Logan; Hansen,Matthew; Hannenhalli, Sridhar (Computational Biology of Transcription Factor BindingComputational Biology of Transcription Factor Binding, 2010)
Gene transcription is largely regulated by DNA-binding transcription factors ( TFs ). However, the TF activity itself is modulated via, among other things, post-translational modifications ( PTMs ) by specific modification enzymes in response to cellular stimuli. TF-PTMs thus serve as “molecular switchboards” that map upstream signaling events to the downstream transcriptional events. An important long-term goal is to obtain a genome-wide map of “regulatory triplets” consisting of a TF, target gene, and a modulator gene that specifically modulates the regulation of the target gene by the TF. A variety of genome-wide data sets can be exploited by computational methods to obtain a rough map of regulatory triplets, which can guide directed experiments. However, a prerequisite to developing such computational tools is a systematic catalog of known instances of regulatory triplets. We first describe PTM-Switchboard, a recent database that stores triplets of genes such that the ability of one gene (the TF) to regulate a target gene is dependent on one or more PTMs catalyzed by a third gene, the modifying enzyme. We also review current computational approaches to infer regulatory triplets from genome-wide data sets and conclude with a discussion of potential future research. PTM-Switchboard is accessible at http://cagr.pcbi.upenn.edu/PTMswitchboard /

Repairing GUI Test Suites Using a Genetic Algorithm - Huang,Si; Cohen,M. B; Memon, Atif M. (Software Testing, Verification and Validation (ICST), 2010 Third International Conference on, 2010)
Recent advances in automated functional testing of Graphical User Interfaces (GUIs) rely on deriving graph models that approximate all possible sequences of events that may be executed on the GUI, and then use the graphs to generate test cases (event sequences) that achieve a specified coverage goal. However, because these models are only approximations of the actual event flows, the generated test cases may suffer from problems of infeasibility, i.e., some events may not be available for execution causing the test case to terminate prematurely. In this paper we develop a method to automatically repair GUI test suites, generating new test cases that are feasible. We use a genetic algorithm to evolve new test cases that increase our test suite's coverage while avoiding infeasible sequences. We experiment with this algorithm on a set of synthetic programs containing different types of constraints and for test sequences of varying lengths. Our results suggest that we can generate new test cases to cover most of the feasible coverage and that the genetic algorithm outperforms a random algorithm trying to achieve the same goal in almost all cases.
Keywords: automated functional testing; genetic algorithm; Genetic algorithms; graph model; graphical user interface; Graphical user interfaces; GUI test suite; program testing; random algorithm; synthetic program; test case

REPORTS AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead - Horvitz,E.; Getoor, Lise; Guestrin,C.; Hendler,J.; Kautz,H.; Konstan,J.; Subramanian,D.; Wellman,M. (AI Magazine, 2010)

Reversible Post-Translational Carboxylation Modulates the Enzymatic Activity of N-Acetyl-l-ornithine Transcarbamylase - Li,Yongdong; Yu,Xiaolin; Ho,Jeremy; Fushman, David; Allewell,Norma M.; Tuchman,Mendel; Shi,Dashuang (Biochemistry, 2010)
N-Acetyl-l-ornithine transcarbamylase (AOTCase), rather than ornithine transcarbamylase (OTCase), is the essential carbamylase enzyme in the arginine biosynthesis of several plant and human pathogens. The specificity of this unique enzyme provides a potential target for controlling the spread of these pathogens. Recently, several crystal structures of AOTCase from Xanthomonas campestris (xc) have been determined. In these structures, an unexplained electron density at the tip of the Lys302 side chain was observed. Using 13C NMR spectroscopy, we show herein that Lys302 is post-translationally carboxylated. The structure of wild-type AOTCase in a complex with the bisubstrate analogue Nδ-(phosphonoacetyl)-Nα-acetyl-l-ornithine (PALAO) indicates that the carboxyl group on Lys302 forms a strong hydrogen bonding network with surrounding active site residues, Lys252, Ser253, His293, and Glu92 from the adjacent subunit either directly or via a water molecule. Furthermore, the carboxyl group is involved in binding N-acetyl-l-ornithine via a water molecule. Activity assays with the wild-type enzyme and several mutants demonstrate that the post-translational modification of lysine 302 has an important role in catalysis.N-Acetyl-l-ornithine transcarbamylase (AOTCase), rather than ornithine transcarbamylase (OTCase), is the essential carbamylase enzyme in the arginine biosynthesis of several plant and human pathogens. The specificity of this unique enzyme provides a potential target for controlling the spread of these pathogens. Recently, several crystal structures of AOTCase from Xanthomonas campestris (xc) have been determined. In these structures, an unexplained electron density at the tip of the Lys302 side chain was observed. Using 13C NMR spectroscopy, we show herein that Lys302 is post-translationally carboxylated. The structure of wild-type AOTCase in a complex with the bisubstrate analogue Nδ-(phosphonoacetyl)-Nα-acetyl-l-ornithine (PALAO) indicates that the carboxyl group on Lys302 forms a strong hydrogen bonding network with surrounding active site residues, Lys252, Ser253, His293, and Glu92 from the adjacent subunit either directly or via a water molecule. Furthermore, the carboxyl group is involved in binding N-acetyl-l-ornithine via a water molecule. Activity assays with the wild-type enzyme and several mutants demonstrate that the post-translational modification of lysine 302 has an important role in catalysis.

Saliency Guided Summarization of Molecular Dynamics Simulations - Patro,R.; Ip,C. Y; Varshney, Amitabh; Hagen,H. (Scientific Visualization: Advanced Concepts, 2010)
We present a novel method to measure saliency in molecular dynamics simulation data. This saliency measure is based on a multiscale center-surround mechanism, which is fast and efficient to compute. We explore the use of the saliency function to guide the selection of representative and anomalous timesteps for summarization of simulations. To this end, we also introduce a multiscale keyframe selection procedure which automatically provides keyframes representing the simulation at varying levels of coarseness. We compare our saliency guided keyframe approach against other methods, and show that it consistently selects superior keyframes as measured by their predictive power in reconstructing the simulation.

Scaling Populations of a Genetic Algorithm for Job Shop Scheduling Problems Using MapReduce - Di-Wei Huang; Jimmy Lin (Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on, 2010)
Inspired by Darwinian evolution, a genetic algorithm (GA) approach is one popular heuristic method for solving hard problems such as the Job Shop Scheduling Problem (JSSP), which is one of the hardest problems lacking efficient exact solutions today. It is intuitive that the population size of a GA may greatly affect the quality of the solution, but it is unclear what are the effects of having population sizes that are significantly greater than typical experiments. The emergence of MapReduce, a framework running on a cluster of computers that aims to provide large-scale data processing, offers great opportunities to investigate this issue. In this paper, a GA is implemented to scale the population using MapReduce. Experiments are conducted on a large cluster, and population sizes up to 107 are inspected. It is shown that larger population sizes not only tend to yield better solutions, but also require fewer generations. Therefore, it is clear that when dealing with a hard problem such as JSSP, an existing GA can be improved by massively scaling up populations with MapReduce, so that the solution can be parallelized and completed in reasonable time.
Keywords: algorithm; job; algorithms; job; computing; genetic; data; large-scale; MapReduce; cloud; problems; parallel; processing; processing; cloud; scheduling; scheduling; parallel; shop

SCORE: agile research group management - Hicks, Michael W.; Foster, Jeffrey S. (Commun. ACM, 2010)
Adapting agile software development methodology toward more efficient management of academic research groups.

Serializing C intermediate representations for efficient and portable parsing - Meister,Jeffrey A; Foster, Jeffrey S.; Hicks, Michael W. (Software: Practice and Experience, 2010)
C static analysis tools often use intermediate representations (IRs) that organize program data in a simple, well-structured manner. However, the C parsers that create IRs are slow, and because they are difficult to write, only a few implementations exist, limiting the languages in which a C static analysis can be written. To solve these problems, we investigate two language-independent, on-disk representations of C IRs: one using XML and the other using an Internet standard binary encoding called eXternal Data Representation (XDR). We benchmark the parsing speeds of both options, finding the XML to be about a factor of 2 slower than parsing C and the XDR over 6 times faster. Furthermore, we show that the XML files are far too large at 19 times the size of C source code, whereas XDR is only 2.2 times the C size. We also demonstrate the portability of our XDR system by presenting a C source code querying tool in Ruby. Our solution and the insights we gained from building it will be useful to analysis authors and other clients of C IRs. We have made our software freely available for download at http://www.cs.umd.edu/projects/PL/scil/. Copyright © 2010 John Wiley&Sons, Ltd.
Keywords: C; intermediate representations; parsing; static analysis; XDR; XML

Serodiversity and ecological distribution of Vibrio parahaemolyticus in the Venetian Lagoon, Northeast Italy - Caburlotto,Greta; Haley,Bradd J.; Lleò,Maria M.; Huq,Anwar; Rita R Colwell (Environmental Microbiology Reports, 2010)
Vibrio parahaemolyticus is a natural inhabitant of estuarine and marine environments constituting part of the autochthonous microflora. This species is associated with human gastroenteritis caused by ingestion of contaminated water and undercooked seafood. During the past several years, the number of V. parahaemolyticus gastroenteritis cases have increased worldwide, causing over half of all food-poisoning outbreaks of bacterial origin. Vibrio populations in water are known to be influenced by environmental factors. Notably, it has been shown that in different parts of the world the distribution of V. parahaemolyticus in the marine environment is related to the water temperature. In this study, we identified environmental determinants affecting distribution of V. parahaemolyticus in the Venetian Lagoon, in the Italian North Adriatic Sea. Data obtained revealed that sea surface temperature constitutes the key factor influencing occurrence of V. parahaemolyticus, but salinity and chlorophyll concentration are also important. Serotyping of a collection of V. parahaemolyticus environmental isolates revealed high serodiversity, with serotypes O3:KUT and O1:KUT, belonging to the ‘pandemic group’, occurring with higher frequency. From our results, we conclude that there is no correlation between serotype and specific geographic site or season of the year. However, certain serotypes were isolated in the Lagoon during the entire 18 months of the study, strongly suggesting persistence in this environment.

Simulating dynamic communication systems using the core functional dataflow model - Sane, N.; Chia-Jui Hsu; Pino,J. L; Bhattacharyya, Shuvra S. (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
The latest communication technologies invariably consist of modules with dynamic behavior. There exists a number of design tools for communication system design with their foundation in dataflow modeling semantics. These tools must not only support the functional specification of dynamic communication modules and subsystems but also provide accurate estimation of resource requirements for efficient simulation and implementation. We explore this trade-off - between flexible specification of dynamic behavior and accurate estimation of resource requirements - using a representative application employing an adaptive modulation scheme. We propose an approach for precise modeling of such applications based on a recently-introduced form of dynamic dataflow called core functional dataflow. From our proposed modeling approach, we show how parameterized looped schedules can be generated and analyzed to simulate applications with low run-time overhead as well as guaranteed bounded memory execution. We demonstrate our approach using the Advanced Design System from Agilent Technologies, Inc., which is a commercial tool for design and simulation of communication systems.
Keywords: adaptive modulation; Analytical models; Application software; Computational modeling; core functional dataflow model; Dataflow; dataflow modeling semantics; design tools; Digital signal processing; dynamic communication systems; functional specification; Hardware; modeling and simulation; Power system modeling; Predictive models; Processor scheduling; Production; Signal processing; software tools; wireless communication

Sites Inferred by Metabolic Background Assertion Labeling (SIMBAL): adapting the Partial Phylogenetic Profiling algorithm to scan sequences for signatures that predict protein function. - Jeremy D Selengut; Rusch, Douglas B; Haft, Daniel H (BMC Bioinformatics, 2010)
BACKGROUND: Comparative genomics methods such as phylogenetic profiling can mine powerful inferences from inherently noisy biological data sets. We introduce Sites Inferred by Metabolic Background Assertion Labeling (SIMBAL), a method that applies the Partial Phylogenetic Profiling (PPP) approach locally within a protein sequence to discover short sequence signatures associated with functional sites. The approach is based on the basic scoring mechanism employed by PPP, namely the use of binomial distribution statistics to optimize sequence similarity cutoffs during searches of partitioned training sets. RESULTS: Here we illustrate and validate the ability of the SIMBAL method to find functionally relevant short sequence signatures by application to two well-characterized protein families. In the first example, we partitioned a family of ABC permeases using a metabolic background property (urea utilization). Thus, the TRUE set for this family comprised members whose genome of origin encoded a urea utilization system. By moving a sliding window across the sequence of a permease, and searching each subsequence in turn against the full set of partitioned proteins, the method found which local sequence signatures best correlated with the urea utilization trait. Mapping of SIMBAL "hot spots" onto crystal structures of homologous permeases reveals that the significant sites are gating determinants on the cytosolic face rather than, say, docking sites for the substrate-binding protein on the extracellular face. In the second example, we partitioned a protein methyltransferase family using gene proximity as a criterion. In this case, the TRUE set comprised those methyltransferases encoded near the gene for the substrate RF-1. SIMBAL identifies sequence regions that map onto the substrate-binding interface while ignoring regions involved in the methyltransferase reaction mechanism in general. Neither method for training set construction requires any prior experimental characterization. CONCLUSIONS: SIMBAL shows that, in functionally divergent protein families, selected short sequences often significantly outperform their full-length parent sequence for making functional predictions by sequence similarity, suggesting avenues for improved functional classifiers. When combined with structural data, SIMBAL affords the ability to localize and model functional sites.
Keywords: algorithms; Amino Acid Sequence; Gene Expression Profiling; Molecular Sequence Data; Phylogeny; Proteins; Sequence Analysis, Protein; Structure-Activity Relationship

Special Section on Distributed Camera Networks: Sensing, Processing, Communication, and Implementation - Chellapa, Rama; Heinzelman, W.; Konrad, J.; Schonfeld, D.; Wolf, M. (Image Processing, IEEE Transactions on, 2010)
The eight papers in this special section span across theoretical and practical considerations of various aspects of distributed camera networks, including adaptive sensing, distributed processing, efficient communications, and versatile implementations.

SPECIAL SECTION ON SHAPE ANALYSIS AND ITS APPLICATIONS IN IMAGE UNDERSTANDING - Srivastava, A.; Damon,J.N.; Dryden,I.L.; Jermyn,I.H.; Das,S.; Vaswani, N.; Huckemann,S.; Hotz,T.; Munk,A.; Lin,Z.; others (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010)

The state of visual analytics: Views on what visual analytics is and where it is going - May,R.; Hanrahan,P.; Keim,D. A; Shneiderman, Ben; Card,S. (2010 IEEE Symposium on Visual Analytics Science and Technology (VAST), 2010)
In the 2005 publication "Illuminating the Path" visual analytics was defined as "the science of analytical reasoning facilitated by interactive visual interfaces." A lot of work has been done in visual analytics over the intervening five years. While visual analytics started in the United States with a focus on security, it is now a worldwide research agenda with a broad range of application domains. This is evidenced by efforts like the European VisMaster program and the upcoming Visual Analytics and Knowledge Discovery (VAKD) workshop, just to name two.There are still questions concerning where and how visual analytics fits in the large body of research and applications represented by the VisWeek community. This panel will present distinct viewpoints on what visual analytics is and its role in understanding complex information in a complex world. The goal of this panel is to engender discussion from the audience on the emergence and continued advancement of visual analytics and its role relative to fields of related research. Four distinguished panelists will provide their perspective on visual analytics focusing on what it is, what it should be, and thoughts about a development path between these two states. The purpose of the presentations is not to give a critical review of the literature but rather to give a review on the field and to provide a contextual perspective based on the panelists' years of experience and accumulated knowledge.
Keywords: analytical reasoning; Data analysis; data mining; data visualisation; European VisMaster program; interactive visual interfaces; knowledge discovery; United States; visual analytics; VisWeek community

Structural and dynamic determinants of ligand binding and regulation of cyclin-dependent kinase 5 by pathological activator p25 and inhibitory peptide CIP. - Cardone, Antonio; Hassan, S A; Albers,R.W.; Sriram,R.D.; Pant,H.C. (Journal of molecular biology, 2010)
The crystal structure of the cdk5/p25 complex has provided information on possible molecular mechanisms of the ligand binding, specificity, and regulation of the kinase. Comparative molecular dynamics simulations are reported here for physiological conditions. This study provides new insight on the mechanisms that modulate such processes, which may be exploited to control pathological activation by p25. The structural changes observed in the kinase are stabilized by a network of interactions involving highly conserved residues within the cyclin-dependent kinase (cdk) family. Collective motions of the proteins (cdk5, p25, and CIP) and their complexes are identified by principal component analysis, revealing two conformational states of the activation loop upon p25 complexation, which are absent in the uncomplexed kinase and not apparent from the crystal. Simulations of the uncomplexed inhibitor CIP show structural rearrangements and increased flexibility of the interfacial loop containing the critical residue E240, which becomes fully hydrated and available for interactions with one of several positively charged residues in the kinase. These changes provide a rationale for the observed high affinity and enhanced inhibitory action of CIP when compared to either p25 or the physiological activators of cdk5.
Keywords: Crystallography, X-Ray; Cyclin-Dependent Kinase 5; Cyclin-Dependent Kinase Inhibitor Proteins; HUMANS; Ligands; molecular dynamics simulation; Nerve Tissue Proteins; Principal component analysis; Protein Binding; Protein Conformation

System and Method for Confidentiality-Preserving Rank-Ordered Search - Swaminathan,Ashwin; Mao,Yinian; Su,Guan-Ming; Gou,Hongmei; Varna,Avinash L.; He,Shan; M. Wu; Oard, Douglas (2010)
A confidentiality preserving system and method for performing a rank-ordered search and retrieval of contents of a data collection. The system includes at least one computer system including a search and retrieval algorithm using term frequency and/or similar features for rank-ordering selective contents of the data collection, and enabling secure retrieval of the selective contents based on the rank-order. The search and retrieval algorithm includes a baseline algorithm, a partially server oriented algorithm, and/or a fully server oriented algorithm. The partially and/or fully server oriented algorithms use homomorphic and/or order preserving encryption for enabling search capability from a user other than an owner of the contents of the data collection. The confidentiality preserving method includes using term frequency for rank-ordering selective contents of the data collection, and retrieving the selective contents based on the rank-order.

Technology-Mediated Social Participation: Deep Science and Extreme Technology - Shneiderman, Ben (Active Media TechnologyActive Media Technology, 2010)
The dramatic success of social media such as Facebook, Twitter, YouTube, Flickr, blogs, and traditional discussion groups empowers individuals to become active in local and global communities. With modest redesign, these technologies can be harnessed to support national priorities such as healthcare/wellness, disaster response, community safety, energy sustainability, etc. This talk describes a research agenda for these topics that develops deep science questions and extreme technology challenges.

Unexpected abundance of coenzyme F(420)-dependent enzymes in Mycobacterium tuberculosis and other actinobacteria. - Jeremy D Selengut; Haft, Daniel H (J Bacteriol, 2010)
Regimens targeting Mycobacterium tuberculosis, the causative agent of tuberculosis (TB), require long courses of treatment and a combination of three or more drugs. An increase in drug-resistant strains of M. tuberculosis demonstrates the need for additional TB-specific drugs. A notable feature of M. tuberculosis is coenzyme F(420), which is distributed sporadically and sparsely among prokaryotes. This distribution allows for comparative genomics-based investigations. Phylogenetic profiling (comparison of differential gene content) based on F(420) biosynthesis nominated many actinobacterial proteins as candidate F(420)-dependent enzymes. Three such families dominated the results: the luciferase-like monooxygenase (LLM), pyridoxamine 5'-phosphate oxidase (PPOX), and deazaflavin-dependent nitroreductase (DDN) families. The DDN family was determined to be limited to F(420)-producing species. The LLM and PPOX families were observed in F(420)-producing species as well as species lacking F(420) but were particularly numerous in many actinobacterial species, including M. tuberculosis. Partitioning the LLM and PPOX families based on an organism's ability to make F(420) allowed the application of the SIMBAL (sites inferred by metabolic background assertion labeling) profiling method to identify F(420)-correlated subsequences. These regions were found to correspond to flavonoid cofactor binding sites. Significantly, these results showed that M. tuberculosis carries at least 28 separate F(420)-dependent enzymes, most of unknown function, and a paucity of flavin mononucleotide (FMN)-dependent proteins in these families. While prevalent in mycobacteria, markers of F(420) biosynthesis appeared to be absent from the normal human gut flora. These findings suggest that M. tuberculosis relies heavily on coenzyme F(420) for its redox reactions. This dependence and the cofactor's rarity may make F(420)-related proteins promising drug targets.
Keywords: Actinobacteria; Amino Acid Sequence; Binding Sites; Coenzymes; Flavonoids; Gene Expression Profiling; Gene Expression Regulation, Bacterial; Genome, Bacterial; molecular biology; Molecular Sequence Data; Molecular Structure; Mycobacterium tuberculosis; Phylogeny; Protein Conformation; Riboflavin

Using a Trust Model in Decision Making for Supply Chain Management - Haghpanah,Y.; desJardins, Marie; others (Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010)

Using Generalized Annotated Programs to Solve Social Network Optimization Problems - Shakarian,P.; V.S. Subrahmanian; Sapino,M. L; Hermenegildo,M.; Schaub,T. (ICLP, 2010)
Reasoning about social networks (labeled, directed, weighted graphs) is be-coming increasingly important and there are now models of how certain phenomena (e.g. adoption of products/services by consumers, spread of a given disease) “diffuse” through the network. Some of these diffusion models can be expressed via generalized annotated programs (GAPs). In this paper, we consider the following problem: suppose we have a given goal to achieve (e.g. maximize the expected number of adoptees of a product or minimize the spread of a disease) and suppose we have limited resources to use in trying to achieve the goal (e.g. give out a few free plans, provide medication to key people in the SN) - how should these resources be used so that we optimize a given objective function related to the goal? We define a class of social network optimization problems (SNOPs) that supports this type of reasoning. We formalize and study the complexity of SNOPs and show how they can be used in conjunction with existing economic and disease diffusion models.

Viewpoint Adapting agile software development methodology toward more efficient management of academic research groups. - Hicks, Michael W.; Foster, Jeffrey S. (Communications of the ACM, 2010)

Visualizing Threaded Conversation Networks: Mining Message Boards and Email Lists for Actionable Insights - Hansen,Derek; Shneiderman, Ben; Smith,Marc (Active Media TechnologyActive Media Technology, 2010)
Analyzing complex online relationships is a difficult job, but new information visualization tools are enabling a wider range of users to make actionable insights from the growing volume of online data. This paper describes the challenges and methods for conducting analyses of threaded conversations such as found in enterprise message boards, email lists, and forums. After defining threaded conversation, we characterize the types of networks that can be extracted from them. We then provide 3 mini case studies to illustrate how actionable insights for community managers can be gained by applying the network analysis metrics and visualizations available in the free, open source NodeXL tool, which is a powerful, yet easy-to-use tool embedded in Excel 2007/2010.

Who's Hogging the Bandwidth: The Consequences of Revealing the Invisible in the Home - Marshini Chetty; Banks, Richard; Harper, Richard; Regan, Tim; Sellen, Abigail; Gkantsidis, Christos; Karagiannis, Thomas; Key, Peter (SIGCHI '10, 2010)
As more technologies enter the home, householders are burdened with the task of digital housekeeping-managing and sharing digital resources like bandwidth. In response to this, we created and evaluated a domestic tool for bandwidth management called Home Watcher. Our field trial showed that when resource contention amongst different household members is made visible, people's understanding of bandwidth changes and household politics are revealed. In this paper, we describe the consequences of showing real time resource usage in a home, and how this varies depending on the social make up of the household.
Keywords: bandwidth monitoring; home broadband; home networks

Workshop on experimental evaluation of software and systems in computer science (Evaluate 2010) - Blackburn,Steven M.; Diwan,Amer; Hauswirth,Matthias; Memon, Atif M.; Sweeney,Peter F. (Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, 2010)
We call ourselves 'computer scientists', but are we scientists? If we are scientists, then we must practice the scientific method. This includes a solid experimental evaluation. In our experience, our experimental methodology is ad hoc at best, and nonexistent at worst. This workshop brings together experts from different areas of computer science to discuss, explore, and attempt to identify the principles of sound experimental evaluation
Keywords: Evaluation; METHODOLOGY

Young Proteins Experience More Variable Selection Pressures Than Old Proteins - Vishnoi,Anchal; Kryazhimskiy,Sergey; Bazykin,Georgii A; Hannenhalli, Sridhar; Plotkin,Joshua B. (Genome ResearchGenome Res., 2010)
It is well known that young proteins tend to experience weaker purifying selection and evolve more quickly than old proteins. Here, we show that, in addition, young proteins tend to experience more variable selection pressures over time than old proteins. We demonstrate this pattern in three independent taxonomic groups: yeast, Drosophila, and mammals. The increased variability of selection pressures on young proteins is highly significant even after controlling for the fact that young proteins are typically shorter and experience weaker purifying selection than old proteins. The majority of our results are consistent with the hypothesis that the function of a young gene tends to change over time more readily than that of an old gene. At the same time, our results may be caused in part by young genes that serve constant functions over time, but nevertheless appear to evolve under changing selection pressures due to depletion of adaptive mutations. In either case, our results imply that the evolution of a protein-coding sequence is partly determined by its age and origin, and not only by the phenotypic properties of the encoded protein. We discuss, via specific examples, the consequences of these findings for understanding of the sources of evolutionary novelty.

Algorithms for distributional and adversarial pipelined filter ordering problems - Condon,Anne; Deshpande, Amol; Hellerstein,Lisa; Wu,Ning (ACM Trans. Algorithms, 2009)
Pipelined filter ordering is a central problem in database query optimization. The problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as to find, as efficiently as possible, the tuples that satisfy all of the filters. Optimization of pipelined filter ordering has recently received renewed attention in the context of environments such as the Web, continuous high-speed data streams, and sensor networks. Pipelined filter ordering problems are also studied in areas such as fault detection and machine learning under names such as learning with attribute costs, minimum-sum set cover, and satisficing search. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional-type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial-type problem where the goal is to minimize the expected value of multiplicative regret. We present two related algorithms for solving (1), both running in time O(n2), which improve on the O(n3 log n) algorithm of Kodialam. We use techniques from our algorithms for (1) to obtain an algorithm for (2).
Keywords: flow algorithms; Pipelined filter ordering; Query optimization; selection ordering

All Bits Are Not Equal - A Study of IEEE 802.11 Communication Bit Errors - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Bhattacharjee, Bobby; Miller,R.R. (INFOCOM 2009, IEEE, 2009)
In IEEE 802.11 Wireless LAN (WLAN) systems, techniques such as acknowledgement, retransmission, and transmission rate adaptation, are frame-level mechanisms designed for combating transmission errors. Recently sub-frame level mechanisms such as frame combining have been proposed by the research community. In this paper, we present results obtained from our bit error study for identifying sub-frame error patterns because we believe that identifiable bit error patterns can potentially introduce new opportunities in channel coding, network coding, forward error correction (FEC), and frame combining mechanisms. We have constructed a number of IEEE 802.11 wireless LAN testbeds and conducted extensive experiments to study the characteristics of bit errors and their location distribution. Conventional wisdom dictates that bit error probability is the result of channel condition and ought to follow corresponding distribution. However our measurement results identify three repeatable bit error patterns that are not induced by channel conditions. We have verified that such error patterns are present in WLAN transmissions in different physical environments and across different wireless LAN hardware platforms. We also discuss our current hypotheses for the reasons behind these bit error probability patterns and how identifying these patterns may help improving WLAN transmission robustness.
Keywords: 802.11; bit; coding; error; coding; forward; coding; subframe; combining; Communication; correction; frame; correction; wireless; error; errors; channel; errors; wireless; IEEE; LAN; LAN; channel; mechanisms; network; patterns; transmission; statistics; forward

Approximate kernel matrix computation on GPUs forlarge scale learning applications - Hussein,Mohamed E; Abd-Almageed, Wael (Proceedings of the 23rd international conference on Supercomputing, 2009)
Kernel-based learning methods require quadratic space and time complexities to compute the kernel matrix. These complexities limit the applicability of kernel methods to large scale problems with millions of data points. In this paper, we introduce a novel representation of kernel matrices on Graphics Processing Units (GPU). The novel representation exploits the sparseness of the kernel matrix to address the space complexity problem. It also respects the guidelines for memory access on GPUs, which are critical for good performance, to address the time complexity problem. Our representation utilizes the locality preserving properties of space filling curves to obtain a band approximation of the kernel matrix. To prove the validity of the representation, we use Affinity Propagation, an unsupervised clustering algorithm, as an example of kernel methods. Experimental results show a 40x speedup of AP using our representation without degradation in clustering performance.
Keywords: affinity propagation; algorithms; arrays; gpu; kernel methods; parallel programming; performance; space filling curves; sparse matrices

Attacking cryptographic schemes based on "perturbation polynomials" - Albrecht,Martin; Gentry,Craig; Halevi,Shai; Katz, Jonathan (Proceedings of the 16th ACM conference on Computer and communications security, 2009)
We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomialbased systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes. Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc 2007), the access-control schemes of Subramanian et al. (PerCom 2007), and the authentication schemes of Zhang et al. (INFOCOM 2008). Our results cast doubt on the viability of using "perturbation polynomials" for designing secure cryptographic schemes.
Keywords: pairwise key establishment; random perturbation polynomial; sensor network security

Avid interactions underlie the Lys63-linked polyubiquitin binding specificities observed for UBA domains - Sims,Joshua J.; Haririnia,Aydin; Dickinson,Bryan C.; Fushman, David; Cohen,Robert E. (Nature Structural & Molecular Biology, 2009)
Ubiquitin (denoted Ub) receptor proteins as a group must contain a diverse set of binding specificities to distinguish the many forms of polyubiquitin (polyUb) signals. Previous studies suggested that the large class of ubiquitin-associated (UBA) domains contains members with intrinsic specificity for Lys63-linked polyUb or Lys48-linked polyUb, thus explaining how UBA-containing proteins can mediate diverse signaling events. Here we show that previously observed Lys63-polyUb selectivity in UBA domains is the result of an artifact in which the dimeric fusion partner, glutathione S-transferase (GST), positions two UBAs for higher affinity, avid interactions with Lys63-polyUb, but not with Lys48-polyUb. Freed from GST, these UBAs are either nonselective or prefer Lys48-polyUb. Accordingly, NMR experiments reveal no Lys63-polyUb–specific binding epitopes for these UBAs. We reexamine previous conclusions based on GST-UBAs and present an alternative model for how UBAs achieve a diverse range of linkage specificities.
Keywords: apoptosis; basic cellular processes; Biochemistry; biophysics; cell biology; cell cycle; cell surface proteins; cell-cell interactions; checkpoints; chromatin; chromatin remodeling; chromatin structure; content; DNA recombination; DNA repair; DNA replication; Gene expression; Genetics; intracellular signaling; journal; macromolecules; mechanism; membrane processes; molecular; molecular basis of disease; molecular biology; molecular interactions; multi-component complexes; nature publishing group; nature structural molecular biology; nucleic acids; protein degradation; protein folding; protein processing; Proteins; regulation of transcription; regulation of translation; RNA; RNA processing; RNAi; signal transduction; single molecule studies; structure and function of proteins; transcription; translation

Channel Access Throttling for Improving WLAN QoS - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON '09. 6th Annual IEEE Communications Society Conference on, 2009)
The de facto QoS channel access method for the IEEE 802.11 Wireless LANs is the Enhanced Distributed Channel Access (EDCA) mechanism, which differentiates transmission treatments for data frames belonging to different traffic categories with four different levels of channel access priority. In this paper, we propose extending EDCA with Channel Access Throttling (CAT) for more flexible and efficient QoS support. By assigning different member stations different channel access parameters, CAT differentiates channel access priorities not between traffic categories but between member stations. Then by dynamically changing the channel access parameters of each member station based on a pre-computed schedule, CAT enables EDCA WLANs the benefits of scheduled access QoS. We also present evaluation results of CAT obtained from both simulations and experiments conducted using off-the-shelf WLAN hardware and open-source device driver. Our results show that CAT can proportionally partition channel capacity, significantly improve performance of multimedia applications, effectively achieve performance protection for admitted flows, and increase per cell VoIP call capacity by up to 41%.
Keywords: 802.11; access; area; call; capacity; data; capacity; quality; capacity; WLAN; categories; transmission; channel; device; distributed; driver; quality; facto; frames; de; IEEE; LAN; LAN; VoIP; local; mechanism; member; method; enhanced; multimedia; network; wireless; networks; channel; of; parameters; channel; priority; channel; QoS; QoS; channel; service; telecommunication; service; traffic; standards; telecommunication; stations; open-source; throttling; channel; traffic; wireless; treatments; wireless; wireless

Channel Access Throttling for Overlapping BSS Management - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Communications, 2009. ICC '09. IEEE International Conference on, 2009)
Multiple co-channel WLAN BSSes (i.e., WLAN cells) overlapping in coverage are generally considered undesirable because members of the OBSSes compete for channel access, which typically increases the contention level of wireless medium access and reduces overall system performance. In this paper, we propose to use channel access throttling (CAT) for managing Wireless LAN radio resources for overlapping BSSes (OBSSes). CAT provides an access point (AP) of each BSS with a mechanism to control channel access parameters of its member stations on the fly. By coordinating the CAT operations of the OBSS APs, we can enable privileged channel access to an individual BSS at a particular time, for example, by assigning high priority access parameters to member stations associated with the BSS. By controlling how much each BSS may be given the privileged channel access, we can also achieve a proportional partitioning of channel capacity among OBSSes. We present evaluation results obtained from both simulations and experiments using testbed built with commercial off-the-shelf (COTS) WLAN hardware and open-source device driver. Our results show that with CAT, not only can we proportionally partition channel capacity among the OBSSes, but also improve channel utilization efficiency and increase overall capacity.
Keywords: access; access; cellular; allocation; channel; BSS; capacity; computer; capacity; proportional; cell; open-source; channel; channels; co-channel; device; driver; overlapping; efficiency; high-priority; LAN; wireless; management; partition; management; wireless; medium; network; parameters; multiple; partitioning; radio; radio; channel; resources; wireless; throttling; channel; utilization; WLAN

Classification of non-manifold singularities from transformations of 2-manifolds - Leon,J.-C.; De Floriani, Leila; Hetroy,F. (Shape Modeling and Applications, 2009. SMI 2009. IEEE International Conference on, 2009)
Non-manifold models are frequently encountered in engineering simulations and design as well as in computer graphics. However, these models lack shape characterization for modelling and searching purposes. Topological properties act as a kernel for deriving key features of objects. Here we propose a classification for the non-manifold singularities of non-manifold objects through continuous shape transformations of 2-manifolds without boundary up to the creation of non-manifold singularities. As a result, the non-manifold objects thus created can be categorized and contribute to the definition of a general purpose taxonomy for non-manifold shapes.
Keywords: classification; search; Computer; graphic; continuous; graphics; pattern; model; nonmanifold; problems; topology; property; computer; SHAPE; singularity; topological; transformation; nonmanifold

Combining powerful local and global statistics for texture description - Yong Xu; Si-Bin Huang; Hui Ji; Fermüller, Cornelia (IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009, 2009)
A texture descriptor is proposed, which combines local highly discriminative features with the global statistics of fractal geometry to achieve high descriptive power, but also invariance to geometric and illumination transformations. As local measurements SIFT features are estimated densely at multiple window sizes and discretized. On each of the discretized measurements the fractal dimension is computed to obtain the so-called multifractal spectrum, which is invariant to geometric transformations and illumination changes. Finally to achieve robustness to scale changes, a multi-scale representation of the multifractal spectrum is developed using a framelet system, that is, a redundant tight wavelet frame system. Experiments on classification demonstrate that the descriptor outperforms existing methods on the UIUC as well as the UMD high-resolution dataset.
Keywords: Computer science; discretized measurements; fractal geometry; Fractals; geometric transformations; global statistics; Histograms; illumination transformations; image classification; image resolution; Image texture; lighting; local measurements SIFT features; local statistics; MATHEMATICS; multifractal spectrum; multiscale representation; Power engineering and energy; Power engineering computing; Robustness; Solids; Statistics; texture description; UMD high-resolution dataset; wavelet frame system; Wavelet transforms

Comparative genomics reveals mechanism for short-term and long-term clonal transitions in pandemic Vibrio cholerae - Chun,J.; Grim,C. J.; Hasan,N. A.; Lee,J. H.; Choi,S. Y.; Haley,B. J.; Taviani,E.; Jeon,Y. S.; Kim,D.W.; Lee,J. H.; Rita R Colwell (Proceedings of the National Academy of Sciences, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the sixth and the current seventh pandemics, respectively. Cholera researchers continually face newly emerging and reemerging pathogenic clones carrying diverse combinations of phenotypic and genotypic properties, which significantly hampered control of the disease. To elucidate evolutionary mechanisms governing genetic diversity of pandemic V. cholerae, we compared the genome sequences of 23 V. cholerae strains isolated from a variety of sources over the past 98 years. The genome-based phylogeny revealed 12 distinct V. cholerae lineages, of which one comprises both O1 classical and El Tor biotypes. All seventh pandemic clones share nearly identical gene content. Using analogy to influenza virology, we define the transition from sixth to seventh pandemic strains as a “shift” between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages. In contrast, transition among clones during the present pandemic period is characterized as a “drift” between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V. cholerae O139 and V. cholerae O1 El Tor hybrid clones. Based on the comparative genomics it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.

A Comprehensive Evaluation Framework and a Comparative Study for Human Detectors - Hussein,M.; Porikli, F.; Davis, Larry S. (Intelligent Transportation Systems, IEEE Transactions on, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.
Keywords: classification; infrared; classifier; comprehensive; curve; INRIA; dataset; average; DET; DETECTION; detection; detector; image; error; Evaluation; framework; cropped; image; image; imaging; object; log; miss; person; rate; cascade; rate; feature; rate; multisize; resize; human; resize; miss; scanning; near-infrared; sliding-window; tradeoff; false-alarm; window; detection

Compressed sensing for Synthetic Aperture Radar imaging - Patel, Vishal M.; Easley,G. R; Healy,D. M; Chellapa, Rama (2009 16th IEEE International Conference on Image Processing (ICIP), 2009)
In this paper, we introduce a new Synthetic Aperture Radar (SAR) imaging modality that provides a high resolution map of the spatial distribution of targets and terrain based on a significant reduction in the number of transmitted and/or received electromagnetic waveforms. This new imaging scheme, which requires no new hardware components, allows the aperture to be compressed and presents many important applications and advantages among which include resolving ambiguities, strong resistance to countermeasures and interception, and reduced on-board storage constraints.
Keywords: Compressed sensing; High-resolution imaging; Image coding; image resolution; Optical imaging; Radar antennas; radar imaging; Radar polarimetry; Reflectivity; SAR; spatial distribution; synthetic aperture radar; synthetic aperture radar imaging

Computing and visualizing a graph-based decomposition for non-manifold shapes - De Floriani, Leila; Panozzo,D.; Hui,A. (Graph-Based Representations in Pattern Recognition, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an effective support to modeling, analyzing and understanding non-manifold shapes.

Concurrent transition and shot detection in football videos using Fuzzy Logic - Refaey,M.A.; Elsayed,K.M.; Hanafy,S.M.; Davis, Larry S. (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
Shot detection is a fundamental step in video processing and analysis that should be achieved with high degree of accuracy. In this paper, we introduce a unified algorithm for shot detection in sports video using fuzzy logic as a powerful inference mechanism. Fuzzy logic overcomes the problems of hard cut thresholds and the need to large training data used in previous work. The proposed algorithm integrates many features like color histogram, edgeness, intensity variance, etc. Membership functions to represent different features and transitions between shots have been developed to detect different shot boundary and transition types. We address the detection of cut, fade, dissolve, and wipe shot transitions. The results show that our algorithm achieves high degree of accuracy.
Keywords: analysis; inference; boundary; shot; Color; colour; detection; sports; functions; shot; histogram; concurrent; logic; image; logic; inference; mechanism; intensity; mechanisms; sport; video; processing; processing; videonanalysis; fuzzy; signal; transition; edgeness; football; variance; membership; video; video; videos; fuzzy

A cost-effective lexical acquisition process for large-scale thesaurus translation - Jimmy Lin; Murray,G. C; Dorr, Bonnie J; Hajič,J.; Pecina,P. (Language resources and evaluation, 2009)
Thesauri and controlled vocabularies facilitate access to digital collections by explicitly representing the underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most thesauri precludes fully-automatic translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations to construct domain-specific lexical resources. This process is illustrated on a thesaurus of 56,000 concepts used to catalog a large archive of oral histories. We elicited human translations on a small subset of concepts, induced a probabilistic phrase dictionary from these translations, and used the resulting resource to automatically translate the rest of the thesaurus. Two separate evaluations demonstrate the acceptability of the automatic translations and the cost-effectiveness of our approach.

Cross-tier, label-based security enforcement for web applications - Corcoran,Brian J.; Swamy,Nikhil; Hicks, Michael W. (Proceedings of the 35th SIGMOD international conference on Management of data, 2009)
This paper presents SELinks, a programming language focused on building secure multi-tier web applications. SELinks provides a uniform programming model, in the style of LINQ and Ruby on Rails, with language syntax for accessing objects residing either in the database or at the server. Object-level security policies are expressed as fully-customizable, first-class labels which may themselves be subject to security policies. Access to labeled data is mediated via trusted, user-provided policy enforcement functions. SELinks has two novel features that ensure security policies are enforced correctly and efficiently. First, SELinks implements a type system called Fable that allows a protected object's type to refer to its protecting label. The type system can check that labeled data is never accessed directly by the program without first consulting the appropriate policy enforcement function. Second, SELinks compiles policy enforcement code to database-resident user-defined functions that can be called directly during query processing. Database-side checking avoids transferring data to the server needlessly, while still allowing policies to be expressed in a customizable and portable manner. Our experience with two sizable web applications, a modelhealth-care database and a secure wiki with fine-grained security policies, indicates that cross-tier policy enforcement in SELinks is flexible, relatively easy to use, and, when compared to a single-tier approach, improves throughput by nearly an order of magnitude. SELinks is freely available.
Keywords: compilers; database programming; security enforcement; type systems; web applications

CTCF binding site classes exhibit distinct evolutionary, genomic, epigenomic and transcriptomic features - Essien,Kobby; Vigneau,Sebastien; Apreleva,Sofia; Singh,Larry N.; Bartolomei,Marisa S.; Hannenhalli, Sridhar (Genome Biology, 2009)
CTCF (CCCTC-binding factor) is an evolutionarily conserved zinc finger protein involved in diverse functions ranging from negative regulation of MYC, to chromatin insulation of the beta-globin gene cluster, to imprinting of the Igf2 locus. The 11 zinc fingers of CTCF are known to differentially contribute to the CTCF-DNA interaction at different binding sites. It is possible that the differences in CTCF-DNA conformation at different binding sites underlie CTCF's functional diversity. If so, the CTCF binding sites may belong to distinct classes, each compatible with a specific functional role.

Detecting spammers with SNARE: spatio-temporal network-level automatic reputation engine - Hao,Shuang; Syed,Nadeem Ahmed; Feamster, Nick; Gray,Alexander G.; Krasser,Sven (Proceedings of the 18th conference on USENIX security symposium, 2009)
Users and network administrators need ways to filter email messages based primarily on the reputation of the sender. Unfortunately, conventional mechanisms for sender reputation--notably, IP blacklists--are cumbersome to maintain and evadable. This paper investigates ways to infer the reputation of an email sender based solely on network-level features, without looking at the contents of a message. First, we study first-order properties of network-level features that may help distinguish spammers from legitimate senders. We examine features that can be ascertained without ever looking at a packet's contents, such as the distance in IP space to other email senders or the geographic distance between sender and receiver. We derive features that are lightweight, since they do not require seeing a large amount of email from a single IP address and can be gleaned without looking at an email's contents--many such features are apparent from even a single packet. Second, we incorporate these features into a classification algorithm and evaluate the classifier's ability to automatically classify email senders as spammers or legitimate senders. We build an automated reputation engine, SNARE, based on these features using labeled data from a deployed commercial spam-filtering system. We demonstrate that SNARE can achieve comparable accuracy to existing static IP blacklists: about a 70%detection rate for less than a 0.3%false positive rate. Third, we show how SNARE can be integrated into existing blacklists, essentially as a first-pass filter.

Detection of toxigenic Vibrio cholerae O1 in freshwater lakes of the former Soviet Republic of Georgia - Grim,Christopher J.; Jaiani,Ekaterina; Whitehouse,Chris A.; Janelidze,Nino; Kokashvili,Tamuna; Tediashvili,Marina; Rita R Colwell; Huq,Anwar (Environmental Microbiology Reports, 2009)
Three freshwater lakes, Lisi Lake, Kumisi Lake and Tbilisi Sea, near Tbilisi, Georgia, were studied from January 2006 to December 2007 to determine the presence of Vibrio cholerae employing both bacteriological culture method and direct detection methods, namely PCR and direct fluorescent antibody (DFA). For PCR, DNA extracted from water samples was tested for presence of V. cholerae and genes coding for selected virulence factors. Vibrio cholerae non-O1/non-O139 was routinely isolated by culture from all three lakes; whereas V. cholerae O1 and O139 were not. Water samples collected during the summer months from Lisi Lake and Kumisi Lake were positive for both V. cholerae and V. cholerae ctxA, tcpA, zot, ompU and toxR by PCR. Water samples collected during the same period from both Lisi and Kumisi Lake were also positive for V. cholerae serogroup O1 by DFA. All of the samples were negative for V. cholerae serotype O139. The results of this study provide evidence for an environmental presence of toxigenic V. cholerae O1, which may represent a potential source of illness as these lakes serve as recreational water in Tbilisi, Georgia.

Directing JavaScript with arrows - Khoo,Yit Phang; Hicks, Michael W.; Foster, Jeffrey S.; Sazawal,Vibha (Proceedings of the 5th symposium on Dynamic languages, 2009)
JavaScript programmers make extensive use of event-driven programming to help build responsive web applications. However, standard approaches to sequencing events are messy, and often lead to code that is difficult to understand and maintain. We have found that arrows, a generalization of monads, are an elegant solution to this problem. Arrows allow us to easily write asynchronous programs in small, modular units of code, and flexibly compose them in many different ways, while nicely abstracting the details of asynchronous program composition. In this paper, we present Arrowlets, a new JavaScript library that offers arrows to the everyday JavaScript programmer. We show how to use Arrowlets to construct a variety of state machines, including state machines that branch and loop. We also demonstrate how Arrowlets separate computation from composition with examples such as a drag-and-drop handler and a bubblesort animation.
Keywords: arrowlets; arrows; events; javascript; web programming

Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks - Han,Bo; Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2009, 2009)
Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
Keywords: access hash function; Channel allocation; channel assignment algorithm; channel capacity; collision avoidance; Computer science; cryptography; distributed algorithm; distributed algorithms; Educational institutions; inductive-scheduling technique; Interference; interference set; packet scheduling algorithm; Peer to peer computing; Radio network; radio networks; radiofrequency interference; random oracle methodology; scheduling; Scheduling algorithm; simultaneous channel allocation; software radio; software-defined radio wireless network capacity; telecommunication congestion control; telecommunication security; Throughput; wireless channels; Wireless networks

Do you know the way to SNA?: A process model for analyzing and visualizing social media data - Hansen,D. L; Rotman,D.; Bonsignore,E.; Milic-Frayling,N.; Rodrigues,E.M.; Smith,M.; Shneiderman, Ben (University of Maryland Tech Report: HCIL-2009-17, 2009)
Traces of activity left by social media users can shed lighton individual behavior, social relationships, and community efficacy. Tools and processes to analyze social traces are essential for enabling practitioners to study and nurture meaningful and sustainable social interaction. Yet such tools and processes remain in their infancy. We conducted a study of 15 graduate students who were learning to apply Social Network Analysis (SNA) to data from online communities. Based on close observations of their emergent practices, we derived the Network Analysis and Visualization (NAV) process model and identified stages where intervention from peers, experts, and an SNA tool were most useful. We show how the NAV model informs the design of SNA tools and services, education practices, and support for social media practitioners.

Dynamic software updates: a VM-centric approach - Subramanian,Suriya; Hicks, Michael W.; McKinley,Kathryn S. (Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, 2009)
Software evolves to fix bugs and add features. Stopping and restarting programs to apply changes is inconvenient and often costly. Dynamic software updating (DSU) addresses this problem by updating programs while they execute, but existing DSU systems for managed languages do not support many updates that occur in practice and are inefficient. This paper presents the design and implementation of Jvolve, a DSU-enhanced Java VM. Updated programs may add, delete, and replace fields and methods anywhere within the class hierarchy. Jvolve implements these updates by adding to and coordinating VM classloading, just-in-time compilation, scheduling, return barriers, on-stack replacement, and garbage collection. Jvolve, is safe: its use of bytecode verification and VM thread synchronization ensures that an update will always produce type-correct executions. Jvolve is flexible: it can support 20 of 22 updates to three open-source programs--Jetty web server, JavaEmailServer, and CrossFTP server--based on actual releases occurring over 1 to 2 years. Jvolve is efficient: performance experiments show that incurs no overhead during steady-state execution. These results demonstrate that this work is a significant step towards practical support for dynamic updates in virtual machines for managed languages.
Keywords: dynamic software updating; garbage collection; virtual machine technology

Dynamic software updates for Java: A VM-centric approach - Subramanian,S.; Hicks, Michael W.; McKinley,K.S. (Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), 2009)
Software evolves to fix bugs and add features, but stopping andrestarting existing programs to take advantage of these changes can be inconvenient and costly. Dynamic software updating (DSU) addresses these problems by updating programs while they run. The challenge is to develop DSU infrastructure that is flexible, safe, and efficient—DSU should enable updates that are likely to occur in practice, and updated programs should be as reliable and as efficient as those started from scratch. This paper presents the design and implementation of a JVM we call JVOLVE that is enhanced with DSU support. The pa- per’s key insight is that flexible, safe, and efficient DSU can be supported by naturally extending existing VM services. By piggybacking on classloading and garbage collection, JVOLVE can flexibly support additions and replacements of fields and methods anywhere within the class hierarchy, and in a manner that may alter class signatures. By utilizing bytecode verifi- cation and thread synchronization support, JVOLVE can ensure that an applied update will never violate type-safety. Finally, by employing JIT compilation, all DSU-related overhead be- fore or after an update can be effectively eliminated. Using JVOLVE, we successfully applied dynamic continuous updates corresponding to 20 of the 22 releases that occurred over nearly two years’ time, one update per release, for three open-source programs, Jetty web server, JavaEmailServer, and CrossFTP server. Our results indicate that the VM is well-suited to sup- port practical DSU services.

Efficient band approximation of Gram matrices for large scale kernel methods on GPUs - Hussein,Mohamed; Abd-Almageed, Wael (Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, 2009)
Kernel-based methods require O(N2) time and space complexities to compute and store non-sparse Gram matrices, which is prohibitively expensive for large scale problems. We introduce a novel method to approximate a Gram matrix with a band matrix. Our method relies on the locality preserving properties of space filling curves, and the special structure of Gram matrices. Our approach has several important merits. First, it computes only those elements of the Gram matrix that lie within the projected band. Second, it is simple to parallelize. Third, using the special band matrix structure makes it space efficient and GPU-friendly. We developed GPU implementations for the Affinity Propagation (AP) clustering algorithm using both our method and the COO sparse representation. Our band approximation is about 5 times more space efficient and faster to construct than COO. AP gains up to 6x speedup using our method without any degradation in its clustering performance.
Keywords: affinity propagation; algorithms; gpu

Efficient systematic testing for dynamically updatable software - Hayden,Christopher M; Hardisty,Eric A.; Hicks, Michael W.; Foster, Jeffrey S. (Proceedings of the 2nd International Workshop on Hot Topics in Software Upgrades, 2009)
Recent years have seen significant advances in dynamic software updating (DSU) systems, which allow programs to be patched on the fly. However, a significant challenge remains: How can we ensure the act of applying a patch does not itself introduce errors? In this paper, we address this problem by presenting a new systematic testing methodology for updatable programs. Our idea is to transform standard system tests into update tests that execute as before, but each transformed test applies a patch at a different update point during execution. To mitigate the increase in the number of tests, we developed an algorithm for test suite minimization that finds a subset of update points that, if fully tested, yields the equivalent to full update point coverage. We implemented our approach and evaluated it on OpenSSH and vsftpd, two widely used server applications. We found that minimization is highly effective, reducing the number of update tests required for full coverage by 93%.

Efficient systematic testing for dynamically updatable software - Hayden,C.M.; Hardisty,E.A.; Hicks, Michael W.; Foster, Jeffrey S. (Proceedings of the 2nd International Workshop on Hot Topics in Software Upgrades, 2009)

Encryption Algorithm Based on Circle Property - Ge,L.N.; He,Z.H.; Zhuolin Jiang (Jisuanji Gongcheng/ Computer Engineering, 2009)

Enhancing sparsity using gradients for compressive sensing - Patel, Vishal M.; Easley,G. R; Chellapa, Rama; Healy,D. M (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
In this paper, we propose a reconstruction method that recovers images assumed to have a sparse representation in a gradient domain by using partial measurement samples that are collected in the Fourier domain. A key improvement of this technique is that it makes use of a robust generalized Poisson solver that greatly aids in achieving a significantly improved performance over similar proposed methods. Experiments provided also demonstrate that this new technique is more flexible to work with either random or restricted sampling scenarios better than its competitors.
Keywords: analysis; gradient; domain; compressive; domain; image; Fourier; generalized; measurement; methods; methods; image; Poisson; reconstruction; image; reconstruction; partial; representation; Fourier; representation; sampling; samples; robust; scenarios; sparse; sensing; enhancing; solver; sampling; sparsity; gradient

Evidence for Coregulation of Myocardial Gene Expression by MEF2 and NFAT in Human Heart Failure / CLINICAL PERSPECTIVE - Putt,Mary E.; Hannenhalli, Sridhar; Lu,Yun; Haines,Philip; Chandrupatla,Hareesh R.; Morrisey,Edward E.; Margulies,Kenneth B.; Cappola,Thomas P. (Circulation: Cardiovascular Genetics, 2009)
Background— Pathological stresses induce heart failure in animal models through activation of multiple cardiac transcription factors (TFs) working cooperatively. However, interactions among TFs in human heart failure are less understood. Here, we use genomic data to examine the evidence that 5 candidate TF families coregulate gene expression in human heart failure.Methods and Results— RNA isolates from failing (n=86) and nonfailing (n=16) human hearts were hybridized with Affymetrix HU133A arrays. For each gene on the array, we determined conserved MEF2, NFAT, NKX , GATA , and FOX binding motifs within the −1-kb promoter region using human-murine sequence alignments and the TRANSFAC database. Across 9076 genes expressed in the heart, TF-binding motifs tended to cluster together in nonrandom patterns within promoters of specific genes (P values ranging from 10−2 to 10−21), suggesting coregulation. We then modeled differential expression as a function of TF combinations present in promoter regions. Several combinations predicted increased odds of differential expression in the failing heart, with the highest odds ratios noted for genes containing both MEF2 and NFAT binding motifs together in the same promoter region (peak odds ratio, 3.47; P=0.005).Conclusions— These findings provide genomic evidence for coregulation of myocardial gene expression by MEF2 and NFAT in human heart failure. In doing so, they extend the paradigm of combinatorial regulation of gene expression to the human heart and identify new target genes for mechanistic study. More broadly, we demonstrate how integrating diverse sources of genomic data yields novel insight into human cardiovascular disorders.

The evolution of Fox genes and their role in development and disease - Hannenhalli, Sridhar; Kaestner,Klaus H. (Nature reviews. GeneticsNat Rev Genet, 2009)
The forkhead box (Fox) family of transcription factors, which originated in unicellular eukaryotes, has expanded over time through multiple duplication events, and sometimes through gene loss, to over 40 members in mammals. Fox genes have evolved to acquire a specialized function in many key biological processes. Mutations in Fox genes have a profound effect on human disease, causing phenotypes as varied as cancer, glaucoma and language disorders. We summarize the salient features of the evolution of the Fox gene family and highlight the diverse contribution of various Fox subfamilies to developmental processes, from organogenesis to speech acquisition.

Fingerprinting Compressed Multimedia Signals - Varna,A.L.; He,Shan; Swaminathan,A.; M. Wu (Information Forensics and Security, IEEE Transactions on, 2009)
Digital fingerprinting is a technique to deter unauthorized redistribution of multimedia content by embedding a unique identifying signal in each legally distributed copy. The embedded fingerprint can later be extracted and used to trace the originator of an unauthorized copy. A group of users may collude and attempt to create a version of the content that cannot be traced back to any of them. As multimedia data is commonly stored in compressed form, this paper addresses the problem of fingerprinting compressed signals. Analysis is carried out to show that due to the quantized nature of the host signal and the embedded fingerprint, directly extending traditional fingerprinting techniques for uncompressed signals to the compressed case leads to low collusion resistance. To overcome this problem and improve the collusion resistance, a new technique for fingerprinting compressed signals called Anti-Collusion Dither (ACD) is proposed, whereby a random dither signal is added to the compressed host before embedding so as to make the effective host signal appear more continuous. The proposed technique is shown to reduce the accuracy with which attackers can estimate the host signal, and from an information theoretic perspective, the proposed ACD technique increases the maximum number of users that can be supported by the fingerprinting system under a given attack. Both analytical and experimental studies confirm that the proposed technique increases the probability of identifying a guilty user and can approximately quadruple the collusion resistance compared to conventional Gaussian fingerprinting.
Keywords: coding; coding; copy; collusion; digital; communication; video; compression; digital; compression; video; dither; collusion; domain; fingerprinting; anti-collusion; fingerprinting; multimedia; Gaussian; management; multimedia; protection; data; resistance; compressed; rights

First Steps to Netviz Nirvana: Evaluating Social Network Analysis with NodeXL - Bonsignore,E. M; Dunne,C.; Rotman,D.; Smith,M.; Capone,T.; Hansen,D. L; Shneiderman, Ben (International Conference on Computational Science and Engineering, 2009. CSE '09, 2009)
Social Network Analysis (SNA) has evolved as a popular, standard method for modeling meaningful, often hidden structural relationships in communities. Existing SNA tools often involve extensive pre-processing or intensive programming skills that can challenge practitioners and students alike. NodeXL, an open-source template for Microsoft Excel, integrates a library of common network metrics and graph layout algorithms within the familiar spreadsheet format, offering a potentially low-barrier-to-entry framework for teaching and learning SNA. We present the preliminary findings of 2 user studies of 21 graduate students who engaged in SNA using NodeXL. The majority of students, while information professionals, had little technical background or experience with SNA techniques. Six of the participants had more technical backgrounds and were chosen specifically for their experience with graph drawing and information visualization. Our primary objectives were (1) to evaluate NodeXL as an SNA tool for a broad base of users and (2) to explore methods for teaching SNA. Our complementary dual case-study format demonstrates the usability of NodeXL for a diverse set of users, and significantly, the power of a tightly integrated metrics/visualization tool to spark insight and facilitate sense-making for students of SNA.
Keywords: Computer science; computer science education; data visualisation; Data visualization; Educational institutions; graph drawing; graph layout algorithm; Information services; Information Visualization; Internet; Libraries; Microsoft Excel open-source template; MILC; multi-dimensional in-depth long-term case studies; Netviz Nirvana; NodeXL; Open source software; Programming profession; SNA; social network analysis; Social network services; social networking (online); spreadsheet programs; structural relationship; teaching; visual analytics; visualization tool; Web sites

Flexible and efficient querying and ranking on hyperlinked data sources - Varadarajan,R.; Hristidis,V.; Raschid, Louiqa; Vidal,M. E; Ibá\ nez,L.; Rodríguez-Drumond,H. (Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, 2009)

Gene Profiling of Human Adipose Tissue During Evoked Inflammation In Vivo - Shah,Rachana; Lu,Yun; Hinkle,Christine C; McGillicuddy,Fiona C; Kim,Roy; Hannenhalli, Sridhar; Cappola,Thomas P.; Heffron,Sean; Wang,XingMei; Mehta,Nehal N; Putt,Mary; Reilly,Muredach P (DiabetesDiabetes, 2009)
OBJECTIVE Adipose inflammation plays a central role in obesity-related metabolic and cardiovascular complications. However, few human adipose-secreted proteins are known to mediate these processes. We hypothesized that microarray mRNA profiling of human adipose during evoked inflammation could identify novel adipocytokines.RESEARCH DESIGN AND METHODS Healthy human volunteers (n = 14) were treated with intravenous endotoxin (3 ng/kg lipopolysaccharide [LPS]) and underwent subcutaneous adipose biopsies before and after LPS. On Affymetrix U133Plus 2.0 arrays, adipose mRNAs modulated >1.5-fold (with P < 0.00001) were selected. SignalP 3.0 and SecretomeP 2.0 identified genes predicted to encode secreted proteins. Of these, 86 candidates were chosen for validation in adipose from an independent human endotoxemia protocol (N = 7, with 0.6 ng/kg LPS) and for exploration of cellular origin in primary human adipocytes and macrophages in vitro. RESULTS Microarray identified 776 adipose genes modulated by LPS; 298 were predicted to be secreted. Of detectable prioritized genes, 82 of 85 (96% [95% CI 90–99]) were upregulated (fold changes >1.0) during the lower-dose (LPS 0.6 ng/kg) validation study and 51 of 85 (59% [49–70]) were induced greater than 1.5-fold. Treatment of primary adipocytes with LPS and macrophage polarization to M1 proinflammatory phenotype increased expression by 1.5-fold for 58 and 73% of detectable genes, respectively. CONCLUSIONS We demonstrate that evoked inflammation of human adipose in vivo modulated expression of multiple genes likely secreted by adipocytes and monocytes. These included established adipocytokines and chemokines implicated in recruitment and activation of lymphocytes, adhesion molecules, antioxidants, and several novel genes with unknown function. Such candidates may represent biomarkers and therapeutic targets for obesity-related complications.

Generating surveys of scientific paradigms - Mohammad,S.; Dorr, Bonnie J; Egan,M.; Hassan,A.; Muthukrishan,P.; Qazvinian,V.; Radev,D.; Zajic, David (Proceedings of HLT-NAACL, 2009)
The number of research publications in var-ious disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of tech- nical material. In this paper we present the first steps in producing an automatically gen- erated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization tech- niques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the frame- work of multi-document survey creation, cita- tion texts can play a crucial role.

Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains - Brettin,Thomas S[Los Alamos National Laboratory; Bruce,David C[Los Alamos National Laboratory; Challacombe,Jean F[Los Alamos National Laboratory; Detter,John C[Los Alamos National Laboratory; Han,Cliff S[Los Alamos National Laboratory; Munik,A. C[Los Alamos National Laboratory; Chertkov,Olga[Los Alamos National Laboratory; Meincke,Linda[Los Alamos National Laboratory; Saunders,Elizabeth[Los Alamos National Laboratory; Choi,Seon Y[SEOUL NATL UNIV; Haley,Bradd J[U MARYLAND; Taviani,Elisa[U MARYLAND; et al. (Nature, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a 'shift' between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a 'drift' between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.
Keywords: 59; CHOLERA; GENES; GENETICS; GENOTYPE; ISLANDS; ORIGIN; PHENOTYPE; PUBLIC HEALTH; RECOMBINATION; STRAINS; TOXINS

Hat guessing games - Butler,S.; Hajiaghayi, Mohammad T.; Kleinberg,R. D; Leighton,T. (SIAM review, 2009)

High-Fidelity Data Embedding for Image Annotation - He,Shan; Kirovski,D.; M. Wu (Image Processing, IEEE Transactions on, 2009)
High fidelity is a demanding requirement for data hiding, especially for images with artistic or medical value. This correspondence proposes a high-fidelity image watermarking for annotation with robustness to moderate distortion. To achieve the high fidelity of the embedded image, we introduce a visual perception model that aims at quantifying the local tolerance to noise for arbitrary imagery. Based on this model, we embed two kinds of watermarks: a pilot watermark that indicates the existence of the watermark and an information watermark that conveys a payload of several dozen bits. The objective is to embed 32 bits of metadata into a single image in such a way that it is robust to JPEG compression and cropping. We demonstrate the effectiveness of the visual model and the application of the proposed annotation technology using a database of challenging photographic and medical images that contain a large amount of smooth regions.
Keywords: Automated; Product Labeling; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Computer-Assisted; Computer-Assisted; Information Storage and Retrieval; Pattern Recognition; JPEG compression; JPEG cropping; arbitrary imagery; data hiding; high-fidelity data embedding; image annotation; image watermarking; medical images; photographic images; data compression; image coding; watermarking; Algorithms; Computer Graphics; Documentation; Image En

How children search the internet with keyword interfaces - Druin, Allison; Foss,E.; Hatley,L.; Golub,E.; Guha,M.L.; Fails,J.; Hutchinson,H. (Proceedings of the 8th International Conference on Interaction Design and Children, 2009)

Human detection using partial least squares analysis - Schwartz,William Robson; Kembhavi,Aniruddha; Harwood,David; Davis, Larry S. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
Significant research has been devoted to detecting people in images and videos. In this paper we describe a human detection method that augments widely used edge-based features with texture and color information, providing us with a much richer descriptor set. This augmentation results in an extremely high-dimensional feature space (more than 170,000 dimensions). In such high-dimensional spaces, classical machine learning algorithms such as SVMs are nearly intractable with respect to training. Furthermore, the number of training samples is much smaller than the dimensionality of the feature space, by at least an order of magnitude. Finally, the extraction of features from a densely sampled grid structure leads to a high degree of multicollinearity. To circumvent these data characteristics, we employ Partial Least Squares (PLS) analysis, an efficient dimensionality reduction technique, one which preserves significant discriminative information, to project the data onto a much lower dimensional subspace (20 dimensions, reduced from the original 170,000). Our human detection system, employing PLS analysis over the enriched descriptor set, is shown to outperform state-of-the-art techniques on three varied datasets including the popular INRIA pedestrian dataset, the low-resolution gray-scale DaimlerChrysler pedestrian dataset, and the ETHZ pedestrian dataset consisting of full-length videos of crowded scenes.

HydroSense: infrastructure-mediated single-point sensing of whole-home water activity - Jon Froehlich; Larson,E.; Campbell,T.; Haggerty,C.; Fogarty,J.; Patel,S.N. (Proceedings of the 11th international conference on Ubiquitous computing, September, 2009)

Improved approximation algorithms for prize-collecting Steiner tree and TSP - Archer,A.; Bateni,M. H; Hajiaghayi, Mohammad T.; Karloff,H. (2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009)

Improving rule extraction from neural networks by modifying hidden layer representations - Huynh,T. Q; Reggia, James A. (Neural Networks, 2009. IJCNN 2009. International Joint Conference on, 2009)

Interlingual annotation of multilingual text corpora and FrameNet - Farwell,David; Dorr, Bonnie J; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Green,Rebecca; Levin,Lori; Miller,Keith; Mitamura,Teruko; Rambow,Owen; Reeder,Flo; Siddharthan,Advaith (Multilingual FrameNets in Computational LexicographyMultilingual FrameNets in Computational Lexicography, 2009)

Inverse halftoning using a shearlet representation - Easley,G. R; Patel, Vishal M.; Healy Jr,D.M. (Proceedings of SPIE, 2009)

Mimosa: mixture model of co-expression to detect modulators of regulatory interaction - Hansen,Matthew; Everett,Logan; Singh,Larry; Hannenhalli, Sridhar (Proceedings of the 9th international conference on Algorithms in bioinformatics, 2009)
Functionally related genes tend to be correlated in their expression patterns across multiple conditions and/or tissue-types. Thus co-expression networks are often used to investigate functional groups of genes. In particular, when one of the genes is a transcription factor (TF), the co-expression-based interaction is interpreted, with caution, as a direct regulatory interaction. However, any particular TF, and more importantly, any particular regulatory interaction, is likely to be active only in a subset of experimental conditions. Moreover, the subset of expression samples where the regulatory interaction holds may be marked by presence or absence of a modifier gene, such as an enzyme that post-translationally modifies the TF. Such subtlety of regulatory interactions is overlooked when one computes an overall expression correlation. Here we present a novel mixture modeling approach where a TF-Gene pair is presumed to be significantly correlated (with unknown coefficient) in a (unknown) subset of expression samples. The parameters of the model are estimated using a Maximum Likelihood approach. The estimated mixture of expression samples is then mined to identify genes potentially modulating the TF-Gene interaction. We have validated our approach using synthetic data and on three biological cases in cow and in yeast. While limited in some ways, as discussed, the work represents a novel approach to mine expression data and detect potential modulators of regulatory interactions.

Mobile Living Labs 09: Methods and Tools for Evaluation in the Wild - ter Hofte,Henri; Jensen,Kasper Løvborg; Nurmi,Petteri; Jon Froehlich (Proceedings of the 11th International Conference on Human-Computer Interaction with Mobile Devices and Services, 2009)
In a Mobile Living Lab, mobile devices are used to evaluate concepts and prototypes in real-life settings. In other words, the lab is brought to the people. This workshop provides a forum for researchers and practitioners to share experiences and issues with methods and tools for Mobile Living Labs. In particular, we seek to bring together people who have applied methods for Mobile Living Labs and people who build tools for those methods.The aim of the workshop is twofold. First, to make an up-to-date overview of current methods and tools for conducting user studies in Mobile Living Labs -- highlighting their individual strengths and weaknesses. Second, to uncover challenges that are not adequately addressed by current methods and tools and to come up with ideas and requirements that could fill this gap thus serving as beacons for further research and development in this area.
Keywords: field study; in-situ evaluation; living labs; methods; mobile; tools; user experience

Motifs and cis-regulatory modules mediating the expression of genes co-expressed in presynaptic neurons - Liu,Rui; Hannenhalli, Sridhar; Bucan,Maja (Genome Biology, 2009)
Hundreds of proteins modulate neurotransmitter release and synaptic plasticity during neuronal development and in response to synaptic activity. The expression of genes in the pre- and post-synaptic neurons is under stringent spatio-temporal control, but the mechanism underlying the neuronal expression of these genes remains largely unknown.

Multiple instance Feature for robust part-based object detection - Lin,Z.; Hua,G.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)

Network-aware forward caching - Erman,Jeffrey; Gerber,Alexandre; Hajiaghayi, Mohammad T.; Pei,Dan; Spatscheck,Oliver (Proceedings of the 18th international conference on World wide web, 2009)
This paper proposes and evaluates a Network Aware Forward Caching approach for determining the optimal deployment strategy of forward caches to a network. A key advantage of this approach is that we can reduce the network costs associated with forward caching to maximize the benefit obtained from their deployment. We show in our simulation that a 37% increase to net benefits could be achieved over the standard method of full cache deployment to cache all POPs traffic. In addition, we show that this maximal point occurs when only 68% of the total traffic is cached. Another contribution of this paper is the analysis we use to motivate and evaluate this problem. We characterize the Internet traffic of 100K subscribers of a US residential broadband provider. We use both layer 4 and layer 7 analysis to investigate the traffic volumes of the flows as well as study the general characteristics of the applications used. We show that HTTP is a dominant protocol and account for 68% of the total downstream traffic and that 34% of that traffic is multimedia. In addition, we show that multimedia content using HTTP exhibits a 83% annualized growth rate and other HTTP traffic has a 53% growth rate versus the 26% over all annual growth rate of broadband traffic. This shows that HTTP traffic will become ever more dominent and increase the potential caching opportunities. Furthermore, we characterize the core backbone traffic of this broadband provider to measure the distance travelled by content and traffic. We find that CDN traffic is much more efficient than P2P content and that there is large skew in the Air Miles between POP in a typical network. Our findings show that there are many opportunties in broadband provider networks to optimize how traffic is delivered and cached.
Keywords: caching; Web

New records of phytoplankton for Bangladesh. 9. Some rare and a new species - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2009)
Ten taxa belonging to Chlorophyceae, Cyanophyceae, Bacillariophyceae and Euglenophyceae, and one with an uncertain taxonomic position have been described in this paper. Of these, 10 taxa have been found to be globally rare and new records for Bangladesh, whereas Strombomonas islamii Khondker sp. nov. has been described as new to science.

Object detection via boosted deformable features - Hussein,M.; Porikli, F.; Davis, Larry S. (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
It is a common practice to model an object for detection tasks as a boosted ensemble of many models built on features of the object. In this context, features are defined as subregions with fixed relative locations and extents with respect to the object's image window. We introduce using deformable features with boosted ensembles. A deformable features adapts its location depending on the visual evidence in order to match the corresponding physical feature. Therefore, deformable features can better handle deformable objects. We empirically show that boosted ensembles of deformable features perform significantly better than boosted ensembles of fixed features for human detection.
Keywords: boosted; detection; object; detection; statistics; detection; visual; ensembles; deformable; evidence; feature; extraction; object; features; human

Passive aggressive measurement with MGRP - Papageorge,Pavlos; McCann,Justin; Hicks, Michael W. (SIGCOMM Comput. Commun. Rev., 2009)
We present the Measurement Manager Protocol (MGRP), an in-kernel service that schedules and transmits probes on behalf of active measurement tools. Unlike prior measurement services, MGRP transparently piggybacks application packets inside the often significant amounts of empty padding contained in typical probes. Using MGRP thus combines the modularity, flexibility, and accuracy of standalone active measurement tools with the lower overhead of passive measurement techniques. Microbenchmark experiments show that the resulting bandwidth savings makes it possible to measure the network accurately, but faster and more aggressively than without piggybacking, and with few ill effects to piggybacked application or competing traffic. When using MGRP to schedule measurements on behalf of MediaNet, an overlay service that adaptively schedules media streams, we show MediaNet can achieve significantly higher streaming rates under the same network conditions.
Keywords: active; available bandwidth; kernel module; passive; piggybacking; probing; streaming; transport protocol

PERCEPTION AND NAVIGATION FOR AUTONOMOUS VEHICLES - Hussein,M.; Porikli, F.; Davis, Larry S. (IEEE Transactions on intelligent transportation systems, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA Person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.

Planning for Interactions among Autonomous Agents - Au,Tsz-Chiu; Kuter,Ugur; Nau, Dana S. (Programming Multi-Agent Systems, 2009)
AI planning research has traditionally focused on offline pl- anning for static single-agent environments. In environments where an agent needs to plan its interactions with other autonomous agents, planning is much more complicated, because the actions of the other agents can induce a combinatorial explosion in the number of contingencies that the planner will need to consider. This paper discusses several ways to alleviate the combinatorial explosion, and illustrates their use in several different kinds of multi-agent planning domains.
Keywords: Computer science

Predicting the distribution of Vibrio spp. in the Chesapeake Bay: a Vibrio cholerae case study - Constantin de Magny,G.; Long,W.; Brown,C. W.; Hood,R. R.; Huq,A.; Murtugudde,R.; Rita R Colwell (EcoHealth, 2009)
Vibrio cholerae, the causative agent of cholera, is a naturally occurring inhabitant of the Chesapeake Bay and serves as a predictor for other clinically important vibrios, including Vibrio parahaemolyticus and Vibrio vulnificus. A system was constructed to predict the likelihood of the presence of V. cholerae in surface waters of the Chesapeake Bay, with the goal to provide forecasts of the occurrence of this and related pathogenic Vibrio spp. Prediction was achieved by driving an available multivariate empirical habitat model estimating the probability of V. cholerae within a range of temperatures and salinities in the Bay, with hydrodynamically generated predictions of ambient temperature and salinity. The experimental predictions provided both an improved understanding of the in situ variability of V. cholerae, including identification of potential hotspots of occurrence, and usefulness as an early warning system. With further development of the system, prediction of the probability of the occurrence of related pathogenic vibrios in the Chesapeake Bay, notably V. parahaemolyticus and V. vulnificus, will be possible, as well as its transport to any geographical location where sufficient relevant data are available.

Probabilistic fusion-based parameter estimation for visual tracking - Han,Bohyung; Davis, Larry S. (Computer Vision and Image Understanding, 2009)
In object tracking, visual features may not be discriminative enough to estimate high dimensional motion parameters accurately, and complex motion estimation is computationally expensive due to a large search space. To tackle these problems, a reasonable strategy is to track small components within the target independently in lower dimensional motion parameter spaces (e.g., translation only) and then estimate the overall high dimensional motion (e.g., translation, scale and rotation) by statistically integrating the individual tracking results. Although tracking each component in a lower dimensional space is more reliable and faster, it is not trivial to combine the local motion information and estimate global parameters in a robust way because the individual component motions are frequently inconsistent. We propose a robust fusion algorithm to estimate the complex motion parameters using variable-bandwidth mean-shift. By employing correlation-based uncertainty modeling and fusion of individual components, the motion parameter that is robust to outliers can be detected with variable-bandwidth density-based fusion (VBDF) algorithm. In addition, we describe a method to update target appearance model for each component adaptively based on the component motion consistency. We present various tracking results and compare the performance of our algorithm with others using real video sequences.
Keywords: Component-based tracking; Density-based fusion; Mean-shift; visual tracking

PTM-Switchboard--a database of posttranslational modifications of transcription factors, the mediating enzymes and target genes - Everett,L.; Vo,A.; Hannenhalli, Sridhar (Nucleic Acids ResearchNucleic Acids Research, 2009)

Reducing complexity assumptions for statistically-hiding commitment - Haitner,I.; Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R.; Shaltiel,R. (Journal of cryptology, 2009)
We revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Naor et al. show how to construct such schemes based on any one-way permutation. We improve upon this by showing a construction based on any approximable preimage-size one-way function. These are one-way functions for which it is possible to efficiently approximate the number of pre-images of a given output. A special case is the class of regular one-way functions where all points in the image of the function have the same (known) number of pre-images.We also prove two additional results related to statistically-hiding commitment. First, we prove a (folklore) parallel composition theorem showing, roughly speaking, that the statistical hiding property of any such commitment scheme is amplified exponentially when multiple independent parallel executions of the scheme are carried out. Second, we show a compiler which transforms any commitment scheme which is statistically hiding against an honest-but-curious receiver into one which is statistically hiding even against a malicious receiver.

Replication and automation of expert judgments: Information engineering in legal e-discovery - Hedin,B.; Oard, Douglas (IEEE International Conference on Systems, Man and Cybernetics, 2009. SMC 2009, 2009)
The retrieval of digital evidence responsive to discovery requests in civil litigation, known in the United States as ÃÂ¿e-discovery,ÃÂ¿ presents several important and understudied conditions and challenges. Among the most important of these are (i) that the definition of responsiveness that governs the search effort can be learned and made explicit through effective interaction with the responding party, (ii) that the governing definition of responsiveness is generally complex, deriving both from considerations of subject-matter relevance and from considerations of litigation strategy, and (iii) that the result of the search effort is a set (rather than a ranked list) of documents, and sometimes a quite large set, that is turned over to the requesting party and that the responding party certifies to be an accurate and complete response to the request. This paper describes the design of an ÃÂ¿interactive taskÃÂ¿ for the text retrieval conference's legal track that had the evaluation of the effectiveness of e-discovery applications at the ÃÂ¿responsive reviewÃÂ¿ task as its goal. Notable features of the 2008 interactive task were high-fidelity human-system task modeling, authority control for the definition of ÃÂ¿responsiveness,ÃÂ¿ and relatively deep sampling for estimation of type 1 and type 2 errors (expressed as ÃÂ¿precisionÃÂ¿ and ÃÂ¿recallÃÂ¿). The paper presents a critical assessment of the strengths and weaknesses of the evaluation design from the perspectives of reliability, reusability, and cost-benefit tradeoffs.
Keywords: authorisation; authority control; Automation; civil litigation; CYBERNETICS; Delay; digital evidence retrieval; discovery request; Educational institutions; expert judgment automation; Human computer interaction; Human-machine cooperation and systems; human-system task modeling; information engineering; Information retrieval; interactive task; Law; law administration; legal e-discovery; Legal factors; PROBES; Production; Protocols; search effort; Search methods; text analysis; text retrieval conference legal track; United States; USA Councils; User modeling

Resistin gene variation is associated with systemic inflammation but not plasma adipokine levels, metabolic syndrome or coronary atherosclerosis in nondiabetic Caucasians - Qasim,Atif N; Metkus,Thomas S; Tadesse,Mahlet; Lehrke,Michael; Restine,Stephanie; Wolfe,Megan L; Hannenhalli, Sridhar; Cappola,Thomas; Rader,Daniel J; Reilly,Muredach P (Clinical Endocrinology, 2009)
Objective  Resistin causes insulin resistance and diabetes in mice whereas in humans it is linked to inflammation and atherosclerosis. Few human genetic studies of resistin in inflammation and atherosclerosis have been performed. We hypothesized that the –420C>G putative gain-of-function resistin variant would be associated with inflammatory markers and atherosclerosis but not with metabolic syndrome or adipokines in humans.Design and methods  We examined the association of three resistin polymorphisms, –852A>G, –420C>G and +157C>T, and related haplotypes with plasma resistin, cytokines, C-reactive protein (CRP), adipokines, plasma lipoproteins, metabolic syndrome and coronary artery calcification (CAC) in nondiabetic Caucasians (n = 851). Results  Resistin levels were higher, dose-dependently, with the –420G allele (CC 5·9 ± 2·7 ng/ml, GC 6·5 ± 4·0 ng/ml and GG 7·2 ± 4·8 ng/ml, trend P = 0·04) after age and gender adjustment [fold higher for GC + GG vs. CC; 1·07 (1·00–1·15), P < 0·05)]. The –852A>G single nucleotide polymorphism (SNP) was associated with higher soluble tumour necrosis factor-receptor 2 (sol-TNFR2) levels in fully adjusted models [1·06 (95% CI 1·01–1·11), P = 0·01)]. The estimated resistin haplotype (GGT) was associated with sol-TNFR2 (P = 0·04) and the AGT haplotype was related to CRP (P = 0·04) in the fully adjusted models. Resistin SNPs and haplotypes were not associated with body mass index (BMI), fasting glucose, insulin resistance, metabolic syndrome, adipokines or CAC scores. Conclusions  Despite modest associations with plasma resistin and inflammatory biomarkers, resistin 5′ variants were not associated with metabolic parameters or coronary calcification. This suggests that resistin is an inflammatory cytokine in humans but has little influence on adiposity, metabolic syndrome or atherosclerosis.

RNA Colony Blot Hybridization Method for Enumeration of Culturable Vibrio Cholerae and Vibrio Mimicus Bacteria - Grim,Christopher J.; Zo,Young-Gun; Hasan,Nur A.; Ali,Afsar; Chowdhury,Wasimul B.; Islam,Atiqul; Rashid,Mohammed H.; Alam,Munirul; Morris,J. Glenn; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
A species-specific RNA colony blot hybridization protocol was developed for enumeration of culturable Vibrio cholerae and Vibrio mimicus bacteria in environmental water samples. Bacterial colonies on selective or nonselective plates were lysed by sodium dodecyl sulfate, and the lysates were immobilized on nylon membranes. A fluorescently labeled oligonucleotide probe targeting a phylogenetic signature sequence of 16S rRNA of V. cholerae and V. mimicus was hybridized to rRNA molecules immobilized on the nylon colony lift blots. The protocol produced strong positive signals for all colonies of the 15 diverse V. cholerae-V. mimicus strains tested, indicating 100% sensitivity of the probe for the targeted species. For visible colonies of 10 nontarget species, the specificity of the probe was calculated to be 90% because of a weak positive signal produced by Grimontia (Vibrio) hollisae, a marine bacterium. When both the sensitivity and specificity of the assay were evaluated using lake water samples amended with a bioluminescent V. cholerae strain, no false-negative or false-positive results were found, indicating 100% sensitivity and specificity for culturable bacterial populations in freshwater samples when G. hollisae was not present. When the protocol was applied to laboratory microcosms containing V. cholerae attached to live copepods, copepods were found to carry approximately 10,000 to 50,000 CFU of V. cholerae per copepod. The protocol was also used to analyze pond water samples collected in an area of cholera endemicity in Bangladesh over a 9-month period. Water samples collected from six ponds demonstrated a peak in abundance of total culturable V. cholerae bacteria 1 to 2 months prior to observed increases in pathogenic V. cholerae and in clinical cases recorded by the area health clinic. The method provides a highly specific and sensitive tool for monitoring the dynamics of V. cholerae in the environment. The RNA blot hybridization protocol can also be applied to detection of other gram-negative bacteria for taxon-specific enumeration.

The ruby intermediate language - Furr,Michael; An,Jong-hoon (David); Foster, Jeffrey S.; Hicks, Michael W. (SIGPLAN Not., 2009)
Ruby is a popular, dynamic scripting language that aims to "feel natural to programmers" and give users the "freedom to choose" among many different ways of doing the same thing. While this arguably makes programming in Ruby easier, it makes it hard to build analysis and transformation tools that operate on Ruby source code. In this paper, we present the Ruby Intermediate Language (RIL), a Ruby front-end and intermediate representation that addresses these. RIL includes an extensible GLR parser for Ruby, and an automatic translation into an easy-to-analyze intermediate form. This translation eliminates redundant language constructs, unravels the often subtle ordering among side effecting operations, and makes implicit interpreter operations explicit. We also describe several additional useful features of RIL, such as a dynamic instrumentation library for profiling source code and a dataflow analysis engine. We demonstrate the usefulness of RIL by presenting a static and dynamic analysis to eliminate null pointer errors in Ruby programs. We hope that RIL's features will enable others to more easily build analysis tools for Ruby, and that our design will inspire the of similar frameworks for other dynamic languages.
Keywords: intermediate language; profile guided anlaysis; ril; ruby

Safe and timely updates to multi-threaded programs - Neamtiu,Iulian; Hicks, Michael W. (SIGPLAN Not., 2009)
Many dynamic updating systems have been developed that enable a program to be patched while it runs, to fix bugs or add new features. This paper explores techniques for supporting dynamic updates to multi-threaded programs, focusing on the problem of applying an update in a timely fashion while still producing correct behavior. Past work has shown that this tension of safety versus timeliness can be balanced for single-threaded programs. For multi-threaded programs, the task is more difficult because myriad thread interactions complicate understanding the possible program states to which a patch could be applied. Our approach allows the programmer to specify a few program points (e.g., one per thread) at which a patch may be applied, which simplifies reasoning about safety. To improve timeliness, a combination of static analysis and run-time support automatically expands these few points to many more that produce behavior equivalent to the originals. Experiments with thirteen realistic updates to three multi-threaded servers show that we can safely perform a dynamic update within milliseconds when more straightforward alternatives would delay some updates indefinitely.
Keywords: dynamic software updating; multi-threading; update safety; update timeliness

Scene it or not? incremental multiple kernel learning for object detection - Kembhavi,A.; Siddiquie,B.; Miezianko,R.; McCloskey,S.; Davis, Larry S.; Schwartz, W.R.; Harwood,D.; Gupta,A.; Farrell,R.; Luo,Y.; others (Proceedings of the International Conference on Computer Vision, 2009)

Scheduling to minimize staleness and stretch in real-time data warehouses - Bateni,M. H; Golab,L.; Hajiaghayi, Mohammad T.; Karloff,H. (Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, 2009)

Serogroup, Virulence, and Genetic Traits of Vibrio Parahaemolyticus in the Estuarine Ecosystem of Bangladesh - Alam,Munirul; Chowdhury,Wasimul B.; Bhuiyan,N. A.; Islam,Atiqul; Hasan,Nur A.; Nair,G. Balakrish; Watanabe,H.; Siddique,A. K.; Huq,Anwar; Sack,R. Bradley; Akhter,M. Z.; Grim,Christopher J.; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
Forty-two strains of Vibrio parahaemolyticus were isolated from Bay of Bengal estuaries and, with two clinical strains, analyzed for virulence, phenotypic, and molecular traits. Serological analysis indicated O8, O3, O1, and K21 to be the major O and K serogroups, respectively, and O8:K21, O1:KUT, and O3:KUT to be predominant. The K antigen(s) was untypeable, and pandemic serogroup O3:K6 was not detected. The presence of genes toxR and tlh were confirmed by PCR in all but two strains, which also lacked toxR. A total of 18 (41%) strains possessed the virulence gene encoding thermostable direct hemolysin (TDH), and one had the TDH-related hemolysin (trh) gene, but not tdh. Ten (23%) strains exhibited Kanagawa phenomenon that surrogates virulence, of which six, including the two clinical strains, possessed tdh. Of the 18 tdh-positive strains, 17 (94%), including the two clinical strains, had the seromarker O8:K21, one was O9:KUT, and the single trh-positive strain was O1:KUT. None had the group-specific or ORF8 pandemic marker gene. DNA fingerprinting employing pulsed-field gel electrophoresis (PFGE) of SfiI-digested DNA and cluster analysis showed divergence among the strains. Dendrograms constructed using PFGE (SfiI) images from a soft database, including those of pandemic and nonpandemic strains of diverse geographic origin, however, showed that local strains formed a cluster, i.e., “clonal cluster,” as did pandemic strains of diverse origin. The demonstrated prevalence of tdh-positive and diarrheagenic serogroup O8:K21 strains in coastal villages of Bangladesh indicates a significant human health risk for inhabitants.

A set of tools for Representing, Decomposing and Visualizing non manifold Cellular Complexes - De Floriani, Leila; Panozzo,D.; Hui,A. (Department of Computer Science and Information Science, University of Genoa, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an eﬀective support to modeling, analyzing and understanding non-manifold shapes. We describe a new data structure for non-manifold simplicial complex that we used in our decomposition software and we provide a complete description of all functionalities of the library we developed.

Shearlet-Based Deconvolution - Patel, Vishal M.; Easley,G. R; Healy,D. M (IEEE Transactions on Image Processing, 2009)
In this paper, a new type of deconvolution algorithm is proposed that is based on estimating the image from a shearlet decomposition. Shearlets provide a multidirectional and multiscale decomposition that has been mathematically shown to represent distributed discontinuities such as edges better than traditional wavelets. Constructions such as curvelets and contourlets share similar properties, yet their implementations are significantly different from that of shearlets. Taking advantage of unique properties of a new M-channel implementation of the shearlet transform, we develop an algorithm that allows for the approximation inversion operator to be controlled on a multiscale and multidirectional basis. A key improvement over closely related approaches such as ForWaRD is the automatic determination of the threshold values for the noise shrinkage for each scale and direction without explicit knowledge of the noise variance using a generalized cross validation (GCV). Various tests show that this method can perform significantly better than many competitive deconvolution algorithms.
Keywords: approximation inversion operator; contourlets; curvelets; Deconvolution; distributed discontinuities; generalized cross validation; image restoration; M-channel implementation; shearlet-based deconvolution; shearlets; Wavelet transforms; wavelets

Static type inference for Ruby - Furr,Michael; An,Jong-hoon (David); Foster, Jeffrey S.; Hicks, Michael W. (Proceedings of the 2009 ACM symposium on Applied Computing, 2009)
Many general-purpose, object-oriented scripting languages are dynamically typed, which provides flexibility but leaves the programmer without the benefits of static typing, including early error detection and the documentation provided by type annotations. This paper describes Diamondback Ruby (DRuby), a tool that blends Ruby's dynamic type system with a static typing discipline. DRuby provides a type language that is rich enough to precisely type Ruby code we have encountered, without unneeded complexity. When possible, DRuby infers static types to discover type errors in Ruby programs. When necessary, the programmer can provide DRuby with annotations that assign static types to dynamic code. These annotations are checked at run time, isolating type errors to unverified code. We applied DRuby to a suite of benchmarks and found several bugs that would cause run-time type errors. DRuby also reported a number of warnings that reveal questionable programming practices in the benchmarks. We believe that DRuby takes a major step toward bringing the benefits of combined static and dynamic typing to Ruby and other object-oriented languages.
Keywords: Contracts; dynamic typing; ruby; Type inference

Structure of the S5a:K48-Linked Diubiquitin Complex and Its Interactions with Rpn13 - Zhang,Naixia; Wang,Qinghua; Ehlinger,Aaron; Randles,Leah; Lary,Jeffrey W.; Kang,Yang; Haririnia,Aydin; Storaska,Andrew J.; Cole,James L.; Fushman, David; Walters,Kylie J. (Molecular Cell, 2009)
SummaryDegradation by the proteasome typically requires substrate ubiquitination. Two ubiquitin receptors exist in the proteasome, S5a/Rpn10 and Rpn13. Whereas Rpn13 has only one ubiquitin-binding surface, S5a binds ubiquitin with two independent ubiquitin-interacting motifs (UIMs). Here, we use nuclear magnetic resonance (NMR) and analytical ultracentrifugation to define at atomic level resolution how S5a binds K48-linked diubiquitin, in which K48 of one ubiquitin subunit (the “proximal” one) is covalently bonded to G76 of the other (the “distal” subunit). We demonstrate that S5a's UIMs bind the two subunits simultaneously with a preference for UIM2 binding to the proximal subunit while UIM1 binds to the distal one. In addition, NMR experiments reveal that Rpn13 and S5a bind K48-linked diubiquitin simultaneously with subunit specificity, and a model structure of S5a and Rpn13 bound to K48-linked polyubiquitin is provided. Altogether, our data demonstrate that S5a is highly adaptive and cooperative toward binding ubiquitin chains.
Keywords: Proteins

A survey of snake-inspired robot designs - Hopkins,James K.; Spranklin,Brent W.; Gupta, Satyandra K. (Bioinspiration & Biomimetics, 2009)
Body undulation used by snakes and the physical architecture of a snake body may offer significant benefits over typical legged or wheeled locomotion designs in certain types of scenarios. A large number of research groups have developed snake-inspired robots to exploit these benefits. The purpose of this review is to report different types of snake-inspired robot designs and categorize them based on their main characteristics. For each category, we discuss their relative advantages and disadvantages. This review will assist in familiarizing a newcomer to the field with the existing designs and their distinguishing features. We hope that by studying existing robots, future designers will be able to create new designs by adopting features from successful robots. The review also summarizes the design challenges associated with the further advancement of the field and deploying snake-inspired robots in practice.

Symbolic-to-statistical hybridization: extending generation-heavy machine translation - Habash,Nizar; Dorr, Bonnie J; Monz,Christof (Machine Translation, 2009)
The last few years have witnessed an increasing interest in hybridizing surface-based statistical approaches and rule-based symbolic approaches to machine translation (MT). Much of that work is focused on extending statistical MT systems with symbolic knowledge and components. In the brand of hybridization discussed here, we go in the opposite direction: adding statistical bilingual components to a symbolic system. Our base system is Generation-heavy machine translation (GHMT), a primarily symbolic asymmetrical approach that addresses the issue of Interlingual MT resource poverty in source-poor/target-rich language pairs by exploiting symbolic and statistical target-language resources. GHMT’s statistical components are limited to target-language models, which arguably makes it a simple form of a hybrid system . We extend the hybrid nature of GHMT by adding statistical bilingual components. We also describe the details of retargeting it to Arabic–English MT. The morphological richness of Arabic brings several challenges to the hybridization task. We conduct an extensive evaluation of multiple system variants. Our evaluation shows that this new variant of GHMT—a primarily symbolic system extended with monolingual and bilingual statistical components—has a higher degree of grammaticality than a phrase-based statistical MT system, where grammaticality is measured in terms of correct verb-argument realization and long-distance dependency translation.

Target Tracking Based on Nonparametric Clustering and Multi-Scale Images - Shao-fa,J.Z.L.; Hong-li,J.X.Z. (JSCUT (Natural Science Edition), 2009)
In order to track a target in space and scale in a complex background,a target tracking algorithm based on the nonparametric clustering and multi-scale images is presented.In this algorithm,first,a modified nonparame-tric color-clustering method is employed to adaptively partition the color space of a tracked object,and the Gaussian function is used to model the spatial information of each bin of the color histogram.Next,the Bhattacharyya coefficient is adopted to derive a function describing the similarity between the target model and the target candidate.Then,a coarse-to-fine approach of multi-scale images is employed to implement the spatial location of the tracked object.Finally,the derived automatic bandwidth selection method of kernel function is applied to obtain the scale of the tracked object.Experimental results show that the proposed algorithm outperforms the classical mean shift tracker.

A Testing Based Empirical Study of Dynamic Software Update Safety Restrictions - Hayden,Christopher M; Hardisty,Eric A.; Hicks, Michael W.; Foster, Jeffrey S. (Technical Reports of the Computer Science Department, 2009)
Recent years have seen significant advances in dynamic softwareupdating (DSU) systems, which allow programs to be patched on the fly. Most DSU systems employ automatic safety checks to avoid applying a patch if doing so may lead to incorrect behavior. This paper presents what we believe is the first comprehensive empirical evaluation of the two most significant DSU safety checks: activeness safety (AS), which disallows patches that modify functions on the stack, and con-freeness safety (CFS), which allows modifications to active functions, but only when doing so will be type safe. To measure the checks' effectiveness, we tested them against three years of updates to Open-SSH and vsftpd. We performed this testing using a novel DSU testing methodology that systematically applies updates throughout the execution of a test suite. After testing updates to both applications in this way, we tracked how often the safety checks allow updates and which updates result in test failures. We found that updating without safety checks produced many failures, and that both AS and CFS dramatically reduced, but did not fully eliminate, these failures. CFS yielded more failures than AS, but AS was more restrictive than CFS, disallowing far more successful updates. Our results suggest that neither AS nor CFS is likely suitable for general-purpose DSU on its own. Indeed, we found that selecting update points manually could avoid all failures while still permitting sufficient updates. Our results present a challenge and important insights for future work: to discover safe and sufficient update points fully automatically.

Tests to the left of me, types to the right: how not to get stuck in the middle of a ruby execution - Furr,Michael; An,Jong-hoon (David); Foster, Jeffrey S.; Hicks, Michael W. (Proceedings for the 1st workshop on Script to Program Evolution, 2009)
Ruby is a popular dynamic scripting language that permits terse, expressive code, but provides no static checks to detect errors before running the program. To address this, we have developed Diamond-back Ruby (DRuby), a tool that blends the benefits of static and dynamic typing. This paper briefly describes the main features of DRuby, which we will present in a tool demonstration. The presentation will concentrate on the development of a small, statically typed Ruby program, illustrating how DRuby might be used in practice. The audience will learn about some of the practical design decisions that went into DRuby, and how to use it to develop a type-safe Ruby program.

A theory of typed coercions and its applications - Swamy,Nikhil; Hicks, Michael W.; Bierman,Gavin M. (Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, 2009)
A number of important program rewriting scenarios can be recast as type-directed coercion insertion. These range from more theoretical applications such as coercive subtyping and supporting overloading in type theories, to more practical applications such as integrating static and dynamically typed code using gradual typing, and inlining code to enforce security policies such as access control and provenance tracking. In this paper we give a general theory of type-directed coercion insertion. We specifically explore the inherent tradeoff between expressiveness and ambiguity--the more powerful the strategy for generating coercions, the greater the possibility of several, semantically distinct rewritings for a given program. We consider increasingly powerful coercion generation strategies, work out example applications supported by the increased power (including those mentioned above), and identify the inherent ambiguity problems of each setting, along with various techniques to tame the ambiguities.
Keywords: coercion insertion; gradual typing; nonambiguity; provenance; type-directed translation

Three genomes from the phylum Acidobacteria provide insight into the lifestyles of these microorganisms in soils. - Ward, Naomi L; Challacombe, Jean F; Janssen, Peter H; Henrissat, Bernard; Coutinho, Pedro M; Wu, Martin; Xie, Gary; Haft, Daniel H; Sait, Michelle; Badger, Jonathan; Barabote, Ravi D; Bradley, Brent; et al. (Appl Environ Microbiol, 2009)
The complete genomes of three strains from the phylum Acidobacteria were compared. Phylogenetic analysis placed them as a unique phylum. They share genomic traits with members of the Proteobacteria, the Cyanobacteria, and the Fungi. The three strains appear to be versatile heterotrophs. Genomic and culture traits indicate the use of carbon sources that span simple sugars to more complex substrates such as hemicellulose, cellulose, and chitin. The genomes encode low-specificity major facilitator superfamily transporters and high-affinity ABC transporters for sugars, suggesting that they are best suited to low-nutrient conditions. They appear capable of nitrate and nitrite reduction but not N(2) fixation or denitrification. The genomes contained numerous genes that encode siderophore receptors, but no evidence of siderophore production was found, suggesting that they may obtain iron via interaction with other microorganisms. The presence of cellulose synthesis genes and a large class of novel high-molecular-weight excreted proteins suggests potential traits for desiccation resistance, biofilm formation, and/or contribution to soil structure. Polyketide synthase and macrolide glycosylation genes suggest the production of novel antimicrobial compounds. Genes that encode a variety of novel proteins were also identified. The abundance of acidobacteria in soils worldwide and the breadth of potential carbon use by the sequenced strains suggest significant and previously unrecognized contributions to the terrestrial carbon cycle. Combining our genomic evidence with available culture traits, we postulate that cells of these isolates are long-lived, divide slowly, exhibit slow metabolic rates under low-nutrient conditions, and are well equipped to tolerate fluctuations in soil hydration.
Keywords: Anti-Bacterial Agents; bacteria; Biological Transport; Carbohydrate Metabolism; Cyanobacteria; DNA, Bacterial; Fungi; Genome, Bacterial; Macrolides; Molecular Sequence Data; Nitrogen; Phylogeny; Proteobacteria; Sequence Analysis, DNA; sequence homology; Soil Microbiology

Toward reconstructing the evolution of advanced moths and butterflies (Lepidoptera: Ditrysia): an initial molecular study - Regier,J. C; Zwick,A.; Cummings, Michael P.; Kawahara,A. Y; Cho,S.; Weller,S.; Roe,A.; Baixeras,J.; Brown,J. W; Parr,C.; Davis,DR; Epstein,M; et al. (BMC Evol Biol, 2009)
BACKGROUND: In the mega-diverse insect order Lepidoptera (butterflies and moths; 165,000 described species), deeper relationships are little understood within the clade Ditrysia, to which 98% of the species belong. To begin addressing this problem, we tested the ability of five protein-coding nuclear genes (6.7 kb total), and character subsets therein, to resolve relationships among 123 species representing 27 (of 33) superfamilies and 55 (of 100) families of Ditrysia under maximum likelihood analysis. RESULTS: Our trees show broad concordance with previous morphological hypotheses of ditrysian phylogeny, although most relationships among superfamilies are weakly supported. There are also notable surprises, such as a consistently closer relationship of Pyraloidea than of butterflies to most Macrolepidoptera. Monophyly is significantly rejected by one or more character sets for the putative clades Macrolepidoptera as currently defined (P < 0.05) and Macrolepidoptera excluding Noctuoidea and Bombycoidea sensu lato (P < or = 0.005), and nearly so for the superfamily Drepanoidea as currently defined (P < 0.08). Superfamilies are typically recovered or nearly so, but usually without strong support. Relationships within superfamilies and families, however, are often robustly resolved. We provide some of the first strong molecular evidence on deeper splits within Pyraloidea, Tortricoidea, Geometroidea, Noctuoidea and others.Separate analyses of mostly synonymous versus non-synonymous character sets revealed notable differences (though not strong conflict), including a marked influence of compositional heterogeneity on apparent signal in the third codon position (nt3). As available model partitioning methods cannot correct for this variation, we assessed overall phylogeny resolution through separate examination of trees from each character set. Exploration of "tree space" with GARLI, using grid computing, showed that hundreds of searches are typically needed to find the best-feasible phylogeny estimate for these data. CONCLUSION: Our results (a) corroborate the broad outlines of the current working phylogenetic hypothesis for Ditrysia, (b) demonstrate that some prominent features of that hypothesis, including the position of the butterflies, need revision, and (c) resolve the majority of family and subfamily relationships within superfamilies as thus far sampled. Much further gene and taxon sampling will be needed, however, to strongly resolve individual deeper nodes.

Towards an Internet Connectivity Market - Feamster, Nick; Hassan,U.; Sundaresan,S.; Valancius,V.; Johari,R.; Vazirani,V. (Georgia Institute of Technology, 2009)
Today’s Internet achieves end-to-end connectivity through bilateral contracts between neighboring networks; unfortunately, this “one size fits all” connectivity results in less efficient paths, unsold capacity and unmet demand, and sometimes catastrophic market failures that result in global disconnectivity. This paper presents the design and evaluation of MINT, a Market for Internet Transit. MINT is a connectivity market and corresponding set of protocols that allows ISPs to offer path segments on an open market. Edge networks bid for end-to-end paths, and a mediator matches bids for paths to collections of path segments that form end-to-end paths. MINT can be deployed using protocols that are present in today’s routers, and it operates in parallel with the existing routing infrastructure and connectivity market. We present MINT’s market model and protocol design; evaluate how MINT improves efficiency, the utility of edge networks, and the profits of transit networks; and how MINT can operate at Internet scale.

Triaging Checklists: a Substitute for a PhD in Static Analysis - Phang,K.Y.; Foster, Jeffrey S.; Hicks, Michael W.; Sazawal,V. (Evaluation and Usability of Programming Languages and Tools (PLATEAU) PLATEAU 2009, 2009)
Static analysis tools have achieved great success in recentyears in automating the process of detecting defects in soft- ware. However, these sophisticated tools have yet to gain widespread adoption, since many of these tools remain too difficult to understand and use. In previous work, we dis- covered that even with an effective code visualization tool, users still found it hard to determine if warnings reported by these tools were true errors or false warnings. The fun- damental problem users face is to understand enough of the underlying algorithm to determine if a warning is caused by imprecision in the algorithm, a challenge that even experts with PhDs may take a while to achieve. In our current work, we propose to use triaging checklists to provide users with systematic guidance to identify false warnings by taking into account specific sources of imprecision in the particular tool. Additionally, we plan to provide checklist assistants, which is a library of simple analyses designed to aid users in an- swering checklist questions.

UbiGreen: investigating a mobile tool for tracking and supporting green transportation habits - Jon Froehlich; Dillahunt,Tawanna; Klasnja,Predrag; Mankoff,Jennifer; Consolvo,Sunny; Harrison,Beverly; Landay,James A. (Proceedings of the 27th international conference on Human factors in computing systems, 2009)
Keywords: ambient displays; mobile phones; sensing; Sustainability; transportation; ubicomp

Using citations to generate surveys of scientific paradigms - Mohammad,Saif; Dorr, Bonnie J; Egan,Melissa; Hassan,Ahmed; Muthukrishan,Pradeep; Qazvinian,Vahed; Radev,Dragomir; Zajic, David (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)
The number of research publications in various disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of technical material. In this paper we present the first steps in producing an automatically generated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization techniques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the framework of multi-document survey creation, citation texts can play a crucial role.

Using formal specifications to support testing - Hierons,Robert M.; Krause,Paul; Lüttgen,Gerald; Simons,Anthony J. H.; Vilkomir,Sergiy; Woodward,Martin R.; Zedan,Hussein; Bogdanov,Kirill; Bowen,Jonathan P.; Cleaveland, Rance; Derrick,John; Dick,Jeremy; et al. (ACM Computing Surveys, 2009)

Verified enforcement of stateful information release policies - Swamy,Nikhil; Hicks, Michael W. (SIGPLAN Not., 2009)
Many organizations specify information release policies to describe the terms under which sensitive information may be released to other organizations. This paper presents a new approach for ensuring that security-critical software correctly enforces its information release policy. Our approach has two parts. First, an information release policy is specified as a security automaton written in a new language called AIR. Second, we enforce an AIR policy by translating it into an API for programs written in lAIR, a core formalism for a functional programming language. lAIR uses a novel combination of dependent, affine, and singleton types to ensure that the API is used correctly. As a consequence we can certify that programs written in lAIR meet the requirements of the original AIR policy specification.
Keywords: affine types; certified evaluation; declassification; dependent types; singleton types; state modifying policies

Video-based Lane Detection using Boosting Principles - Gopalan,R.; Hong, T.; Shneier, M.; Chellapa, Rama (Snowbird, 2009)
Autonomous navigation of road vehicles is a challenging problem that has widespread applications in intelligent systems, and robotics. An integral componentof such a system is to understand how the road is structured. Detection of road lane markings assumes importance in this regard, and this problem has been approached with different visual input- based inference algorithms ([1], [2]), besides other sensing modalities such as the GPS sensor and the internal vehicle- state sensors. But the challenge still remains when there is considerable amount of shadows on the road, variations in outdoor lighting conditions of the scene (transition from day to night), among others. To address such issues, we propose a machine learning approach based on Real Adaboost [3], and train linear classifiers for both the appearance and edge cues of the training examplars. Additionally, we incorporate prior knowledge about the relative importance of the training samples by computing their weights using kernel discriminant analysis [4], before learning the classification function through boosting. The regions identified as lane markings are then analyzed for gradient direction consistency before making the final detection decision. We illustrate the effectiveness of our algorithm on challenging daylight and night- time road scenarios.

Visual Tracking by Continuous Density Propagation in Sequential Bayesian Filtering Framework - Han,Bohyung; Zhu,Ying; Comaniciu, D.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009)
Particle filtering is frequently used for visual tracking problems since it provides a general framework for estimating and propagating probability density functions for nonlinear and non-Gaussian dynamic systems. However, this algorithm is based on a Monte Carlo approach and the cost of sampling and measurement is a problematic issue, especially for high-dimensional problems. We describe an alternative to the classical particle filter in which the underlying density function has an analytic representation for better approximation and effective propagation. The techniques of density interpolation and density approximation are introduced to represent the likelihood and the posterior densities with Gaussian mixtures, where all relevant parameters are automatically determined. The proposed analytic approach is shown to perform more efficiently in sampling in high-dimensional space. We apply the algorithm to real-time tracking problems and demonstrate its performance on real video sequences as well as synthetic examples.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Computer-Assisted; Pattern Recognition; Computer-Assisted; Subtraction Technique; Monte Carlo approach; continuous density propagation; density approximation; density interpolation; nonGaussian dynamic systems; nonlinear dynamic systems; particle filtering; probability density functions; sequential Bayesian filtering framework; video sequences

Access to recorded interviews - Jong,Franciska De; Oard, Douglas; Heeren,Willemijn; Ordelman,Roeland (Journal on Computing and Cultural Heritage, 2008)

Activity sensing in the wild: a field trial of ubifit garden - Consolvo,S.; McDonald,D.W.; Toscos,T.; Chen,M.Y.; Jon Froehlich; Harrison,B.; Klasnja,P.; LaMarca,A.; LeGrand,L.; Libby,R.; others (Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)

Analysis of Computer Security Incident Data Using Time Series Models - Condon,E.; He,A.; Michel Cukier (2008)
Organizations face increasing challenges in addressing and preventing computer and network security incidents. There are financial consequences from security incidents. These include lost time and resources used during recovery, possible theft of personal and/or proprietary information, and reputational damage that may negatively impact stock prices or reduce consumer confidence in a company. Being able to understand and predict trends in computer and network security incidents can aid an organization with resource allocation for prevention of such incidents, as well as evaluation of mitigation strategies. We look at using time series models with a large set of security incident data. We examine appropriateness of the data for modeling and consider needed transformations. Parameter search and model selection criteria are discussed. Then, forecasts from time series models are compared to forecasts from Non-Homogeneous Poisson Process (NHPP) software reliability growth (SRG) models.
Keywords: Computer networks; computer security incident data; NETWORK SECURITY; resource allocation; security of data; telecommunication security; time series; time series model

The ASC-Alliance Projects: A Case Study of Large-Scale Parallel Scientific Code Development - Hochstein, L.; Basili, Victor R. (Computer, 2008)
Computational scientists face many challenges when developing software that runs on large-scale parallel machines. However, software-engineering researchers haven't studied their software development processes in much detail. To better understand the nature of software development in this context, the authors examined five large-scale computational science software projects operated at the five ASC-Alliance centers.
Keywords: ASC-Alliance; code; development; large-scale; development; parallel; engineering; machines; software; Parallel; projects; computational; scale; Science; scientific; scientists; large; software; systems; parallel

Biofilms in water, its role and impact in human disease transmission - Huq,Anwar; Whitehouse,Chris A.; Grim,Christopher J.; Alam,Munirul; Rita R Colwell (Current Opinion in Biotechnology, 2008)
Understanding the mechanism of biofilm formation is the first step in determining its function and, thereby, its impact and role in the environment. Extensive studies accomplished during the past few years have elucidated the genetics and biochemistry of biofilm formation. Cell-to-cell communication, that is, quorum sensing, is a key factor in the initiation of biofilm. Occurrence of viable but nonculturable bacteria, including Vibrio cholerae in biofilms has been reported and most likely such cells were overlooked previously because appropriate methods of detection were not employed. For this reason discovery and investigation of this important bacterial ecological niche in the environment were impeded.

CiCUTS: Combining System Execution Modeling Tools with Continuous Integration Environments - Hill,James H.; Schmidt,Douglas C.; Porter, Adam; Slaby,John M. (Engineering of Computer-Based Systems, IEEE International Conference on the, 2008)
System execution modeling (SEM) tools provide an effective means to evaluate the quality of service (QoS) of enterprise distributed real-time and embedded (DRE) systems. SEM tools facilitate testing and resolving performance issues throughout the entire development life-cycle, rather than waiting until final system integration. SEM tools have not historically focused on effective testing. New techniques are therefore needed to help bridge the gap between the early integration capabilities of SEM tools and testing so developers can focus on resolving strategic integration and performance issues, as opposed to wrestling with tedious and error-prone low-level testing concerns. This paper provides two contributions to research on using SEM tools to address enterprise DRE system integration challenges. First, we evaluate several approaches for combining continuous integration environments with SEM tools and describe CiCUTS, which combines the CUTS SEM tool with the CruiseControl .NET continuous integration environment. Second, we present a case study that shows how CiCUTS helps reduce the time and effort required to manage and execute integration tests that evaluate QoS metrics for a representative DRE system from the domain of shipboard computing. The results of our case study show that CiCUTS helps developers and testers ensure the performance of an example enterprise DRE system is within its QoS specifications throughout development, instead of waiting until system integration time to evaluate QoS.
Keywords: continuous integration; integration testing; serialized phasing; system execution modeling

On the Comparison of Network Attack Datasets: An Empirical Analysis - Berthier,R.; Korman,D.; Michel Cukier; Hiltunen,M.; Vesonder,G.; Sheleheda,D. (2008)
Network malicious activity can be collected and reported by various sources using different attack detection solutions. The granularity of these solutions provides either very detailed information (intrusion detection systems, honeypots) or high-level trends (CAIDA, SANS). The problem for network security operators is often to select the sources of information to better protect their network. How much information from these sources is redundant and how much is unique? The goal of this paper is to show empirically that while some global attack events can be correlated across various sensors, the majority of incoming malicious activity has local specificities. This study presents a comparative analysis of four different attack datasets offering three different levels of granularity: 1) two high interaction honeynets deployed at two different locations (i.e., a corporate and an academic environment); 2) ATLAS which is a distributed network telescope from Arbor; and 3) Internet Protecttrade which is a global alerting service from AT amp;T.
Keywords: ATLAS; distributed network telescope; Internet; intrusion detection systems; network attack datasets; network malicious activity; network security operators; security of data

Computational Analysis of Constraints on Noncoding Regions, Coding Regions and Gene Expression in Relation to Plasmodium Phenotypic Diversity - Essien,Kobby; Hannenhalli, Sridhar; Stoeckert,Christian J. (PLoS ONEPLoS ONE, 2008)
Malaria-causing Plasmodium species exhibit marked differences including host choice and preference for invading particular cell types. The genetic bases of phenotypic differences between parasites can be understood, in part, by investigating constraints on gene expression and genic sequences, both coding and regulatory.We investigated the evolutionary constraints on sequence and expression of parasitic genes by applying comparative genomics approaches to 6 Plasmodium genomes and 2 genome-wide expression studies. We found that the coding regions of Plasmodium transcription factor and sexual development genes are relatively less constrained, as are those of genes encoding CCCH zinc fingers and invasion proteins, which all play important roles in these parasites. Transcription factors and genes with stage-restricted expression have conserved upstream regions and so do several gene classes critical to the parasite's lifestyle, namely, ion transport, invasion, chromatin assembly and CCCH zinc fingers. Additionally, a cross-species comparison of expression patterns revealed that Plasmodium-specific genes exhibit significant expression divergence. Overall, constraints on Plasmodium's protein coding regions confirm observations from other eukaryotes in that transcription factors are under relatively lower constraint. Proteins relevant to the parasite's unique lifestyle also have lower constraint on their coding regions. Greater conservation between Plasmodium species in terms of promoter motifs suggests tight regulatory control of lifestyle genes. However, an interspecies divergence in expression patterns of these genes suggests that either expression is controlled via genomic or epigenomic features not encoded in the proximal promoter sequence, or alternatively, the combinatorial interactions between motifs confer species-specific expression patterns.

Computing word-pair antonymy - Mohammad,Saif; Dorr, Bonnie J; Hirst,Graeme (Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008)
Knowing the degree of antonymy between words has widespread applications in natural language processing. Manually-created lexicons have limited coverage and do not include most semantically contrasting word pairs. We present a new automatic and empirical measure of antonymy that combines corpus statistics with the structure of a published thesaurus. The approach is evaluated on a set of closest-opposite questions, obtaining a precision of over 80%. Along the way, we discuss what humans consider antonymous and how antonymy manifests itself in utterances.

Contextual effects for version-consistent dynamic software updating and safe concurrent programming - Neamtiu,Iulian; Hicks, Michael W.; Foster, Jeffrey S.; Pratikakis,Polyvios (Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2008)
This paper presents a generalization of standard effect systems that we call contextual effects. A traditional effect system computes the effect of an expression e. Our system additionally computes the effects of the computational context in which e occurs. More specifically, we computethe effect of the computation that has already occurred(the prior effect) and the effect of the computation yet to take place (the future effect). Contextual effects are useful when the past or future computation of the program is relevant at various program points. We present two substantial examples. First, we show how prior and future effects can be used to enforce transactional version consistency(TVC), a novel correctness property for dynamic software updates. TV Censures that programmer-designated transactional code blocks appear to execute entirely at the same code version, even if a dynamic update occurs in the middle of the block. Second, we show how future effects can be used in the analysis of multi-threaded programs to find thread-shared locations. This is an essential step in applications such as data race detection.
Keywords: computation effects; contextual effects; data race detection; dynamic software updating; type and effect systems; version consistency

Covariability of Vibrio Cholerae Microdiversity and Environmental Parameters - Zo,Young-Gun; Chokesajjawatee,Nipa; Arakawa,Eiji; Watanabe,Haruo; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2008)
Fine-scale diversity of natural bacterial assemblages has been attributed to neutral radiation because correspondence between bacterial phylogenetic signals in the natural environment and environmental parameters had not been detected. Evidence that such correspondence occurs is provided for Vibrio cholerae, establishing a critical role for environmental parameters in bacterial diversity.

Delegating Capabilities in Predicate Encryption Systems - Elaine Shi; Waters,Brent (Automata, Languages and Programming, 2008)
In predicate encryption systems, given a capability, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden. We consider the role of delegation in such predicate encryption systems. Suppose Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing the decryption of a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation, and give an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite order bilinear groups.
Keywords: Computer science

Directing javascript with arrows (functional pearl) - Khoo,Y.P.; Hicks, Michael W.; Foster, Jeffrey S.; Sazawal,V. (Technical Reports of the Computer Science Department, 2008)
JavaScript, being a single-threaded language, makes extensive use of event-driven programming to enable responsive web applications. However, standard approaches to sequencing events are messy, and often lead to code that is difficult to understand and maintain. We have found that arrows, a generalization of monads, are an elegant solution to this problem. Arrows allow us to easily write asynchronous programs in small, modular units of code, and flexibly compose them in many different ways, while nicely abstracting the details of asynchronous program composition. In particular, we show how to use arrows to construct a variety of state machines, such as autoscrollers and drag-and-drop handlers.

The draft genome of the transgenic tropical fruit tree papaya (Carica papaya Linnaeus) - Ming,R.; Hou,S.; Feng,Y.; Yu,Q.; Dionne-Laporte,A.; Saw,J.H.; Senin,P.; Wang,W.; Ly,B.V.; Lewis,K.L.T.; others (Nature, 2008)
Papaya, a fruit crop cultivated in tropical and subtropical regions, is known for its nutritional benefits and medicinal applications. Here we report a 3 draft genome sequence of 'SunUp' papaya, the first commercial virus-resistant transgenic fruit tree to be sequenced. The papaya genome is three times the size of the Arabidopsis genome, but contains fewer genes, including significantly fewer disease-resistance gene analogues. Comparison of the five sequenced genomes suggests a minimal angiosperm gene set of 13,311. A lack of recent genome duplication, atypical of other angiosperm genomes sequenced so far, may account for the smaller papaya gene number in most functional groups. Nonetheless, striking amplifications in gene number within particular functional groups suggest roles in the evolution of tree-like habit, deposition and remobilization of starch reserves, attraction of seed dispersal agents, and adaptation to tropical daylengths. Transgenesis at three locations is closely associated with chloroplast insertions into the nuclear genome, and with topoisomerase I recognition sites. Papaya offers numerous advantages as a system for fruit-tree functional genomics, and this draft genome sequence provides the foundation for revealing the basis of Carica's distinguishing morpho-physiological, medicinal and nutritional properties.

Dynamic Rebinding for Marshalling and Update, Via Redex-Time and Destruct-Time Reduction - Sewell,Peter; Stoyle,Gareth; Hicks, Michael W.; Bierman,Gavin; Wansbrough,Keith (Journal of Functional Programming, 2008)
Most programming languages adopt static binding, but for distributed programming an exclusive reliance on static binding is too restrictive: dynamic binding is required in various guises, for example, when a marshalled value is received from the network, containing identifiers that must be rebound to local resources. Typically, it is provided only by ad hoc mechanisms that lack clean semantics. In this paper, we adopt a foundational approach, developing core dynamic rebinding mechanisms as extensions to the simply typed call-by-value λ calculus. To do so, we must first explore refinements of the call-by-value reduction strategy that delay instantiation, to ensure computations make use of the most recent versions of rebound definitions. We introduce redex-time and destruct-time strategies. The latter forms the basis for a λmarsh calculus that supports dynamic rebinding of marshalled values, while remaining as far as possible statically typed. We sketch an extension of λmarsh with concurrency and communication, giving examples showing how wrappers for encapsulating untrusted code can be expressed. Finally, we show that a high-level semantics for dynamic updating can also be based on the destruct-time strategy, defining a λupdate calculus with simple primitives to provide type-safe updating of running code. We show how the ideas of this simple calculus extend to more real-world, module-level dynamic updating in the style of Erlang. We thereby establish primitives and a common semantic foundation for a variety of real-world dynamic rebinding requirements.

A Dynamic Reputation Service for Spotting Spammers - Ramachandran,A.; Hao,S.; Khandelwal,H.; Feamster, Nick; Vempala,S. (School of Computer Science, Georgia Tech, 2008)
This paper presents the design, implementation, evalu-ation, and initial deployment of SpamSpotter, the first open, large-scale, real-time reputation system for filtering spam. Existing blacklists (e.g., SpamHaus) have trouble keeping pace with spammers’ increasing ability to send spam from “fresh” IP addresses, and filters based purely on content are easily evadable. In contrast, SpamSpotter dynamically classifies email senders in real time based on their global sending behavior, rather than based on ephemeral features such as an IP address or the content of the message. In implementing SpamSpotter, we address significant challenges involving both dynamism (i.e., de- termining when to “retrain” our dynamic classification algorithms) and scale (i.e., maintaining fast, accurate per- formance in the face of tremendous email message vol- ume). We have evaluated the performance and accuracy of SpamSpotter using traces from a large email-hosting provider and a spam appliance vendor that receives 300 million messages a day. Our evaluation shows that SpamSpotter is scalable, fast, and accurate. SpamSpotter is also operational today: it will currently answer queries from existing spam filtering software (e.g., SpamAssas- sin) with only minor configuration changes.

Effective Visualization of File System Access-Control - Heitzmann, Alexander; Palazzi, Bernardo; Charalampos Papamanthou; Tamassia, Roberto (Visualization for Computer Security, 2008)
In this paper, we present a visual representation of access control permissions in a standard hierarchical file system. Our visualization of file permissions leverages treemaps, a popular graphical representation of hierarchical data. In particular, we present a visualization of access control for the NTFS file system that can help a non-expert user understand and manipulate file system permissions in a simple and effective way. While our examples are based on NTFS, our approach can be used for many other hierarchical file systems as well.
Keywords: Computer Communication Networks; Computer Imaging, Vision, Pattern Recognition and Graphics; data mining and knowledge discovery; Data Structures, Cryptology and Information Theory; Visualization

Efficient Integrity Checking of Untrusted Network Storage - Heitzmann, Alexander; Palazzi, Bernardo; Charalampos Papamanthou; Tamassia, Roberto (StorageSS '08 Proceedings of the 4th ACM International Workshop on Storage Security and Survivability, 2008)
Outsourced storage has become more and more practical in recent years. Users can now store large amounts of data in multiple servers at a relatively low price. An important issue for outsourced storage systems is to design an efficient scheme to assure users that their data stored at remote servers has not been tampered with. This paper presents a general method and a practical prototype application for verifying the integrity of files in an untrusted network storage service. The verification process is managed by an application running in a trusted environment (typically on the client) that stores just one cryptographic hash value of constant size, corresponding to the "digest" of an authenticated data structure. The proposed integrity verification service can work with any storage service since it is transparent to the storage technology used. Experimental results show that our integrity verification method is efficient and practical for network storage systems.
Keywords: authenticated data structures; data integrity; Security; untrusted outsourced storage

An Environment for Conducting Families of Software Engineering Experiments - Hochstein, Lorin; Nakamura,Taiga; Shull, Forrest; Zazworka, Nico; Basili, Victor R.; Zelkowitz, Marvin V (Software Development, 2008)
The classroom is a valuable resource for conducting software engineering experiments. However, coordinating a family of experiments in classroom environments presents a number of challenges to researchers. Understanding how to run such experiments, developing procedures to collect accurate data, and collecting data that is consistent across multiple studies are major problems. This paper describes an environment, the Experiment Manager that simplifies the process of collecting, managing, and sanitizing data from classroom experiments, while minimizing disruption to natural subject behavior. We have successfully used this environment to study the impact of parallel programming languages in the high‐performance computing domain on programmer productivity at multiple universities across the United States.

Eukaryotic Transcription Factor Binding Sites—modeling and Integrative Search Methods - Hannenhalli, Sridhar (BioinformaticsBioinformatics, 2008)
A comprehensive knowledge of transcription factor binding sites (TFBS) is important for a mechanistic understanding of transcriptional regulation as well as for inferring gene regulatory networks. Because the DNA motif recognized by a transcription factor is typically short and degenerate, computational approaches for identifying binding sites based only on the sequence motif inevitably suffer from high error rates. Current state-of-the-art techniques for improving computational identification of binding sites can be broadly categorized into two classes: (1) approaches that aim to improve binding motif models by extracting maximal sequence information from experimentally determined binding sites and (2) approaches that supplement binding motif models with additional genomic or other attributes (such as evolutionary conservation). In this review we will discuss recent attempts to improve computational identification of TFBS through these two types of approaches and conclude with thoughts on future development.Contact: sridharh@pcbi.upenn.edu

Fable: A Language for Enforcing User-defined Security Policies - Swamy,N.; Corcoran,B.J.; Hicks, Michael W. (IEEE Symposium on Security and Privacy, 2008. SP 2008, 2008)
This paper presents FABLE, a core formalism for a programming language in which programmers may specify security policies and reason that these policies are properly enforced. In FABLE, security policies can be expressed by associating security labels with the data or actions they protect. Programmers define the semantics of labels in a separate part of the program called the enforcement policy. FABLE prevents a policy from being circumvented by allowing labeled terms to be manipulated only within the enforcement policy; application code must treat labeled values abstractly. Together, these features facilitate straightforward proofs that programs implementing a particular policy achieve their high-level security goals. FABLE is flexible enough to implement a wide variety of security policies, including access control, information flow, provenance, and security automata. We have implemented FABLE as part of the LINKS web programming language; we call the resulting language SELlNKS. We report on our experience using SELlNKS to build two substantial applications, a wiki and an on-line store, equipped with a combination of access control and provenance policies. To our knowledge, no existing framework enables the enforcement of such a wide variety of security policies with an equally high level of assurance.
Keywords: Access control; Automata; Collaborative work; Communication system security; Computer languages; computer security; Data security; enforcement policy; FABLE; Government; high-level security goals; information flow; Information security; Language-based security; programming languages; Programming profession; provenance; security automata; security labels; security of data; user-defined security policies; verified enforcement; Web programming language

Finding Corrupted Computers Using Imperfect Intrusion Prevention System Event Data - Chrun,Danielle; Michel Cukier; Sneeringer,Gerry (Computer Safety, Reliability, and Security, 2008)
With the increase of attacks on the Internet, a primary concern for organizations is how to protect their network. The objectives of a security team are 1) to prevent external attackers from launching successful attacks against organization computers that could become compromised, 2) to ensure that organization computers are not vulnerable (e.g., fully patched) so that in either case the organization computers do not start launching attacks. The security team can monitor and block malicious activity by using devices such as intrusion prevention systems. However, in large organizations, such monitoring devices could record a high number of events. The contributions of this paper are 1) to introduce a method that ranks potentially corrupted computers based on imperfect intrusion prevention system event data, and 2) to evaluate the method based on empirical data collected at a large organization of about 40,000 computers. The evaluation is based on the judgment of a security expert of which computers were indeed corrupted. On the one hand, we studied how many computers classified as of high concern or of concern were indeed corrupted (i.e., true positives). On the other hand, we analyzed how many computers classified as of lower concern were in fact corrupted (i.e., false negatives).
Keywords: Computer science

Flow Algorithms for Parallel Query Optimization - Deshpande, Amol; Hellerstein,L. (IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, 2008)
We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.
Keywords: Casting; computational complexity; Cost function; Databases; Delay; distributed environment; Educational institutions; flow maximization algorithm; Interleaved codes; interoperator parallelism; minimisation; multiway join query response time minimization problem; parallel database; Parallel databases; parallel query optimization; Partitioning algorithms; pipeline processing; pipelined parallelism; polynomial-time algorithm; query planning problem; Query processing; Web service; Web services

Formalizing Soundness of Contextual Effects - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W.; Neamtiu,Iulian (Theorem Proving in Higher Order LogicsTheorem Proving in Higher Order Logics, 2008)
A contextual effect system generalizes standard type and effect systems: where a standard effect system computes the effect of an expression e , a contextual effect system additionally computes the prior and future effect of e , which characterize the behavior of computation prior to and following, respectively, the evaluation of e . This paper describes the formalization and proof of soundness of contextual effects, which we mechanized using the Coq proof assistant. Contextual effect soundness is an unusual property because the prior and future effect of a term e depends not on e itself (or its evaluation), but rather on the evaluation of the context in which e appears. Therefore, to state and prove soundness we must “match up” a subterm in the original typing derivation with the possibly-many evaluations of that subterm during the evaluation of the program, in a way that is robust under substitution. We do this using a novel typed operational semantics. We conjecture that our approach could prove useful for reasoning about other properties of derivations that rely on the context in which that derivation appears.

A Framework for Software Engineering Experimental Replications - Mendonca,M.G.; Maldonado,J.C.; de Oliveira,M.C.F.; Carver, J.; Fabbri,C.P.F.; Shull, F.; Travassos,G.H.; Hohn,E.N.; Basili, Victor R. (Engineering of Complex Computer Systems, 2008. ICECCS 2008. 13th IEEE International Conference on, 2008)
Experimental replications are very important to the advancement of empirical software engineering. Replications are one of the key mechanisms to confirm previous experimental findings. They are also used to transfer experimental knowledge, to train people, and to expand a base of experimental evidence. Unfortunately, experimental replications are difficult endeavors. It is not easy to transfer experimental know-how and experimental findings. Based on our experience, this paper discusses this problem and proposes a Framework for Improving the Replication of Experiments (FIRE). The FIRE addresses knowledge sharing issues both at the intra-group (internal replications) and inter-group (external replications) levels. It encourages coordination of replications in order to facilitate knowledge transfer for lower cost, higher quality replications and more generalizable results.
Keywords: engineering; engineering; evidence; experimental; experimental; Experiments; experimental; for; Framework; Improving; knowledge; of; replication; replication; software; sharing; software; the; transfer; knowledge

Functional Diversification of Paralogous Transcription Factors via Divergence in DNA Binding Site Motif and in Expression - Singh,Larry N.; Hannenhalli, Sridhar (PLoS ONEPLoS ONE, 2008)
Gene duplication is a major driver of evolutionary innovation as it allows for an organism to elaborate its existing biological functions via specialization or diversification of initially redundant gene paralogs. Gene function can diversify in several ways. Transcription factor gene paralogs in particular, can diversify either by changes in their tissue-specific expression pattern or by changes in the DNA binding site motif recognized by their protein product, which in turn alters their gene targets. The relationship between these two modes of functional diversification of transcription factor paralogs has not been previously investigated, and is essential for understanding adaptive evolution of transcription factor gene families.Based on a large set of human paralogous transcription factor pairs, we show that when the DNA binding site motifs of transcription factor paralogs are similar, the expressions of the genes that encode the paralogs have diverged, so in general, at most one of the paralogs is highly expressed in a tissue. Moreover, paralogs with diverged DNA binding site motifs tend to be diverged in their function. Conversely, two paralogs that are highly expressed in a tissue tend to have dissimilar DNA binding site motifs. We have also found that in general, within a paralogous family, tissue-specific decrease in gene expression is more frequent than what is expected by chance. While previous investigations of paralogous gene diversification have only considered coding sequence divergence, by explicitly quantifying divergence in DNA binding site motif, our work presents a new paradigm for investigating functional diversification. Consistent with evolutionary expectation, our quantitative analysis suggests that paralogous transcription factors have survived extinction in part, either through diversification of their DNA binding site motifs or through alterations in their tissue-specific expression levels.

Genome-Wide Analysis of Natural Selection on Human Cis-Elements - Sethupathy,Praveen; Giang,Hoa; Plotkin,Joshua B.; Hannenhalli, Sridhar (PLoS ONEPLoS ONE, 2008)
It has been speculated that the polymorphisms in the non-coding portion of the human genome underlie much of the phenotypic variability among humans and between humans and other primates. If so, these genomic regions may be undergoing rapid evolutionary change, due in part to natural selection. However, the non-coding region is a heterogeneous mix of functional and non-functional regions. Furthermore, the functional regions are comprised of a variety of different types of elements, each under potentially different selection regimes.Using the HapMap and Perlegen polymorphism data that map to a stringent set of putative binding sites in human proximal promoters, we apply the Derived Allele Frequency distribution test of neutrality to provide evidence that many human-specific and primate-specific binding sites are likely evolving under positive selection. We also discuss inherent limitations of publicly available human SNP datasets that complicate the inference of selection pressures. Finally, we show that the genes whose proximal binding sites contain high frequency derived alleles are enriched for positive regulation of protein metabolism and developmental processes. Thus our genome-scale investigation provides evidence for positive selection on putative transcription factor binding sites in human proximal promoters.

Guest Editors' Introduction to the Special Section on Algorithms in Bioinformatics - Giancarlo,Raffaele; Hannenhalli, Sridhar (IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008)
Keywords: Abstracts; Algorithm design and analysis; Bioinformatics; Biological system modeling; biology computing; Computational Biology; Computational modeling; Computer science; Genomics; sequences

Hardware monitors for dynamic page migration - Tikir, Mustafa M.; Hollingsworth, Jeffrey K (Journal of Parallel and Distributed Computing, 2008)
In this paper, we first introduce a profile-driven online page migration scheme and investigate its impact on the performance of multithreaded applications. We use centralized lightweight, inexpensive plug-in hardware monitors to profile the memory access behavior of an application, and then migrate pages to memory local to the most frequently accessing processor. We also investigate the use of several other potential sources of data gathered from hardware monitors and compare their effectiveness to using data from centralized hardware monitors. In particular, we investigate the effectiveness of using cache miss profiles, Translation Lookaside Buffer (TLB) miss profiles and the content of the on-chip TLBs using the valid bit information. Moreover, we also introduce a modest hardware feature, called Address Translation Counters (ATC), and compare its effectiveness with other sources of hardware profiles.Using the Dyninst runtime instrumentation combined with hardware monitors, we were able to add page migration capabilities to a Sun Fire 6800 server without having to modify the operating system kernel, or to re-compile application programs. Our dynamic page migration scheme reduced the total number of non-local memory accesses of applications by up to 90% and improved the execution times up to 16%. We also conducted a simulation based study and demonstrated that cache miss profiles gathered from on-chip CPU monitors, which are typically available in current microprocessors, can be effectively used to guide dynamic page migrations in applications.
Keywords: Address translation counters; cc-NUMA systems; Dynamic page migration; Full system simulation; Hardware performance monitors; High performance computing; Multiprocessor systems; OpenMP applications; Runtime optimization

Identification of Form Features in Non-Manifold Shapes Through a Decomposition Approach - De Floriani, Leila; Hui,Annie; Giannini,Franca (ASME Conference Proceedings, 2008)
In Computer-Aided Design (CAD), the idealization process reduces the complexity of the model of a solid object, thus resulting in a simplified representation which captures only the essential elements of its shape. Form features extraction is a relevant issue in order to recover semantic information from an idealized object model, since such information is typically lost during the idealization process. An idealized model is usually composed of non-manifold parts, whose topology carries significant structural information about the object shape. To this aim, we define form features for non-manifold object by extending the taxonomy of form features provided by STEP [19]. We describe an approach for the identification of features, which interact with non-manifold singularities in the object, based on a decomposition of a non-manifold object into nearly manifold components and on the properties of the graph representing such decomposition.

Implicit Flows: Can’t Live with ‘Em, Can’t Live without ‘Em - King,Dave; Hicks,Boniface; Hicks, Michael W.; Jaeger,Trent (Information Systems SecurityInformation Systems Security, 2008)
Verifying that programs trusted to enforce security actually do so is a practical concern for programmers and administrators. However, there is a disconnect between the kinds of tools that have been successfully applied to real software systems (such as taint mode in Perl and Ruby), and information-flow compilers that enforce a variant of the stronger security property of noninterference. Tools that have been successfully used to find security violations have focused on explicit flows of information, where high-security information is directly leaked to output. Analysis tools that enforce noninterference also prevent implicit flows of information, where high-security information can be inferred from a program’s flow of control. However, these tools have seen little use in practice, despite the stronger guarantees that they provide. To better understand why, this paper experimentally investigates the explicit and implicit flows identified by the standard algorithm for establishing noninterference. When applied to implementations of authentication and cryptographic functions, the standard algorithm discovers many real implicit flows of information, but also reports an extremely high number of false alarms, most of which are due to conservative handling of unchecked exceptions (e.g., null pointer exceptions). After a careful analysis of all sources of true and false alarms, due to both implicit and explicit flows, the paper concludes with some ideas to improve the false alarm rate, toward making stronger security analysis more practical.

Kernel integral images: A framework for fast non-uniform filtering - Hussein,M.; Porikli, F.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Integral images are commonly used in computer vision and computer graphics applications. Evaluation of box filters via integral images can be performed in constant time, regardless of the filter size. Although Heckbert (1986) extended the integral image approach for more complex filters, its usage has been very limited, in practice. In this paper, we present an extension to integral images that allows for application of a wide class of non-uniform filters. Our approach is superior to Heckbertpsilas in terms of precision requirements and suitability for parallelization. We explain the theoretical basis of the approach and instantiate two concrete examples: filtering with bilinear interpolation, and filtering with approximated Gaussian weighting. Our experiments show the significant speedups we achieve, and the higher accuracy of our approach compared to Heckbertpsilas.
Keywords: approximated; equations; interpolation; filtering; bilinear; filtering; kernel; Gaussian; graphics; computer; images; approximation; integral; interpolation; computer; nonuniform; processing; integral; theory; filtering; theory; image; vision; fast; weighting

Maternal depletion of CTCF reveals multiple functions during oocyte and preimplantation embryo development - Wan,Le-Ben; Pan,Hua; Hannenhalli, Sridhar; Cheng,Yong; Ma,Jun; Fedoriw,Andrew; Lobanenkov,Victor; Latham,Keith E.; Schultz,Richard M.; Bartolomei,Marisa S. (Development, 2008)
CTCF is a multifunctional nuclear factor involved in epigenetic regulation. Despite recent advances that include the systematic discovery of CTCF-binding sites throughout the mammalian genome, the in vivo roles of CTCF in adult tissues and during embryonic development are largely unknown. Using transgenic RNAi, we depleted maternal stores of CTCF from growing mouse oocytes, and identified hundreds of misregulated genes. Moreover, our analysis suggests that CTCF predominantly activates or derepresses transcription in oocytes. CTCF depletion causes meiotic defects in the egg, and mitotic defects in the embryo that are accompanied by defects in zygotic gene expression, and culminate in apoptosis. Maternal pronuclear transfer and CTCF mRNA microinjection experiments indicate that CTCF is a mammalian maternal effect gene, and that persistent transcriptional defects rather than persistent chromosomal defects perturb early embryonic development. This is the first study detailing a global and essential role for CTCF in mouse oocytes and preimplantation embryos.

Model Based Design Verification: A Monitor Based Approach - Ackermann,Chris; Ray,Arnab; Cleaveland, Rance; Heit,Jürgen; Martin,Christopher; Shelton,Charles (SAE International, 2008)
This paper assesses the utility of an automated functional verification methodology in the design of a body electronics application. The use of design models as detailed specifications for software is gaining steady acceptance in the automotive industry because of the advantages it offers in terms of rapid system prototyping and automatic code generation. This paper argues that such modeling effort can also be used to provide support for design verification, so that errors may be pinpointed before they find their way into code, when they become much harder and more expensive to isolate, diagnose and repair.

Modular Information Hiding and Type-Safe Linking for C - Srivastava,S.; Hicks, Michael W.; Foster, Jeffrey S.; Jenkins,P. (IEEE Transactions on Software Engineering, 2008)
This paper presents CMod, a novel tool that provides a sound module system for C. CMod works by enforcing four rules that are based on principles of modular reasoning and on current programming practice. CMod's rules flesh out the convention that .h header files are module interfaces and .c source files are module implementations. Although this convention is well-known, existing explanations of it are incomplete, omitting important subtleties needed for soundness. In contrast, we have proven formally that CMod's rules enforce both information hiding and type-safe linking. To use CMod, the programmer develops and builds their software as usual, redirecting the compiler and linker to CMod's wrappers. We evaluated CMod by applying it to 30 open source programs, totaling more than one million LoC. Violations to CMod's rules revealed more than a thousand information hiding errors, dozens of typing errors, and hundreds of cases that, although not currently bugs, make programming mistakes more likely as the code evolves. At the same time, programs generally adhere to the assumptions underlying CMod's rules, and so we could fix rule violations with a modest effort. We conclude that CMod can effectively support modular programming in C: it soundly enforces type-safe linking and information-hiding while being largely compatible with existing practice.
Keywords: C language; CMOD; Code design; Coding Tools and Techniques; compiler; data encapsulation; Information hiding; modular information hiding; modular reasoning; modules; object-oriented programming; open source programs; packages; program compilers; public domain software; reliability; software reusability; type-safe linking

Mpeg recompression detection based on block artifacts - Luo,W.; Wu,M.; Huang,J. (Proc. of SPIE Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents, 2008)
With sophisticated video editing technologies, it is becoming increasingly easy to tamper digital video withoutleaving visual clues. One of the common tampering operations on video is to remove some frames and then re-encode the resulting video. In this paper, we propose a new method for detecting this type of tampering by exploring the temporal patterns of the block artifacts in video sequences. We show that MPEG compression introduces different block artifacts into various types of frames and that the strength of the block artifacts as a function over time has a regular pattern for a given group of pictures (GOP) structure. When some frames are removed from an MPEG video file and the file is then recompressed, the block artifacts introduced by the previous compression would remain and affect the average of block artifact strength of the recompressed one in such a way that depends on the number of deleted frames and the type of GOP used previously. We propose a feature curve to reveal the compression history of an MPEG video file with a given GOP structure, and use it as evidence to detect tampering. Experimental results evaluated on common video benchmark clips demonstrate the effectiveness of the proposed method.

Mutations in the Hydrophobic Core of Ubiquitin Differentially Affect Its Recognition by Receptor Proteins - Haririnia,Aydin; Verma,Rati; Purohit,Nisha; Twarog,Michael Z.; Deshaies,Raymond J.; Bolon,Dan; Fushman, David (Journal of Molecular Biology, 2008)
Ubiquitin (Ub) is one of the most highly conserved signaling proteins in eukaryotes. In carrying out its myriad functions, Ub conjugated to substrate proteins interacts with dozens of receptor proteins that link the Ub signal to various biological outcomes. Here we report mutations in conserved residues of Ub's hydrophobic core that have surprisingly potent and specific effects on molecular recognition. Mutant Ubs bind tightly to the Ub-associated domain of the receptor proteins Rad23 and hHR23A but fail to bind the Ub-interacting motif present in the receptors Rpn10 and S5a. Moreover, chains assembled on target substrates with mutant Ubs are unable to support substrate degradation by the proteasome in vitro or sustain viability of yeast cells. The mutations have relatively little effect on Ub's overall structure but reduce its rigidity and cause a slight displacement of the C-terminal β-sheet, thereby compromising association with Ub-interacting motif but not with Ub-associated domains. These studies emphasize an unexpected role for Ub's core in molecular recognition and suggest that the diversity of protein–protein interactions in which Ub engages placed enormous constraints on its evolvability.
Keywords: hydrophobic core mutation; molecular recognition; proteasomal degradation; ubiquitin; ubiquitin receptors

Name translation in statistical machine translation: Learning when to transliterate - Hermjakob,U.; Knight,K.; Daumé, Hal (Proceedings of ACL-08: HLT, 2008)

A new multiresolution generalized directional filter bank design and application in image enhancement - Patel, Vishal M.; Easley,G. R; Healy,D. M (15th IEEE International Conference on Image Processing, 2008. ICIP 2008, 2008)
In this paper, we present an image enhancement technique based on a new multiscale generalized directional filter bank design. The design presented is a shift-invariant overcomplete representation, which is well suited to extracting geometric features such as edges. Special cases of this design method can be made to reduce to different and improved implementations of the shearlet and the contourlet transforms, which are known to represent certain classes of images optimally. Use of this new filter bank design has proven itself competitive in image restoration for noisy images and is well suited for distinguishing noise from weak edges. Experimental results show that our unique image enhancement technique out-performs wavelet and contourlet based enhancement methods.
Keywords: Algorithm design and analysis; Approximation error; Channel bank filters; contourlet transform; Design methodology; Discrete transforms; Feature extraction; Filter bank; Frequency; geometric feature extraction; Image Enhancement; IMAGE PROCESSING; image resolution; image restoration; Multidimensional digital filters; Multidimensional systems; multiresolution generalized directional filter bank design; shearlet transform; shift-invariant overcomplete representation; transforms; Wavelet transforms

New records of phytoplankton for Bangladesh. 2. Cryptophyceae and Synurophyceae - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Botany, 2008)
This study presents two species of Rhodomonas, four species of Chroomonas, six species of Cryptomonas and Cryptochrysis minor, Cyanomonas coeruleus, Chrysodidymus synuroideus and Mallomonas akrokomos. These species have been reported from some ponds of Mathbaria in Pirojpur and Bakerganj of Barisal district in Bangladesh.

New records of phytoplankton for Bangladesh. 5. Euglena, Euglenocapsa - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2008)
This study presents 20 taxa of the genus Euglena and one species of the rare euglenoid genus Euglenocapsa. All these taxa are reported for the first time from some pond ecosystems of Mathbaria in Pirojpur and Bakerganj of Barisal districts of Bangladesh.

New records of phytoplankton for Bangladesh. 7. Phacus spp. - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Botany, 2008)
Thirteen species of Phacus hitherto not reported from Bangladesh have been described and illustrated. Freshwater ponds at southern districts of Pirojpur and Barisal revealed these presence of the species.

New records of phytoplankton for Bangladesh. 8. Trachelomonas Ehr. (Euglenophyceae) - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Botany, 2008)
Investigation of pelagic plankton communities from some freshwater ponds of Pirojpur and Barisal districts revealed the presence of 17 species under the genus Trachelomonas Ehr. for the first time in Bangladesh.

Occurrence and Expression of Luminescence in Vibrio Cholerae - Grim,Christopher J.; Taviani,Elisa; Alam,Munirul; Huq,Anwar; Sack,R. Bradley; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2008)
Several species of the genus Vibrio, including Vibrio cholerae, are bioluminescent or contain bioluminescent strains. Previous studies have reported that only 10% of V. cholerae strains are luminescent. Analysis of 224 isolates of non-O1/non-O139 V. cholerae collected from Chesapeake Bay, MD, revealed that 52% (116/224) were luminescent when an improved assay method was employed and 58% (130/224) of isolates harbored the luxA gene. In contrast, 334 non-O1/non-O139 V. cholerae strains isolated from two rural provinces in Bangladesh yielded only 21 (6.3%) luminescent and 35 (10.5%) luxA+ isolates. An additional 270 clinical and environmental isolates of V. cholerae serogroups O1 and O139 were tested, and none were luminescent or harbored luxA. These results indicate that bioluminescence may be a trait specific for non-O1/non-O139 V. cholerae strains that frequently occur in certain environments. Luminescence expression patterns of V. cholerae were also investigated, and isolates could be grouped based on expression level. Several strains with defective expression of the lux operon, including natural K variants, were identified.

Optimal Cryptographic Hardness of Learning Monotone Functions - Dana Dachman-Soled; Lee, Homin K.; Malkin, Tal; Servedio, Rocco A.; Wan, Andrew; Wee, Hoeteck (Automata, Languages and Programming, 2008)
A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n‾‾√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS ’98). Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn; this result is close to optimal in terms of the circuit size parameter by known positive results as well (Servedio, Information and Computation ’04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS ’04).
Keywords: Data structures; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; Numeric Computing; Software Engineering/Programming and Operating Systems; Theory of computation

Path projection for user-centered static analysis tools - Khoo,Yit Phang; Foster, Jeffrey S.; Hicks, Michael W.; Sazawal,Vibha (Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2008)
The research and industrial communities have made great strides in developing sophisticated defect detection tools based on static analysis. To date most of the work in this area has focused on developing novel static analysis algorithms, but has neglected study of other aspects of static analysis tools, particularly user interfaces. In this work, we present a novel user interface toolkit called Path Projection that helps users visualize, navigate, and understand program paths, a common component of many tools' error reports. We performed a controlled user study to measure the benefit of Path Projection in triaging error reports from Locksmith, a data race detection tool for C. We found that Path Projection improved participants' time to complete this task without affecting accuracy, while participants felt Path Projection was useful and strongly preferred it to a more standard viewer.

A pilot study to compare programming effort for two parallel programming models - Hochstein, Lorin; Basili, Victor R.; Vishkin, Uzi; Gilbert,John (Journal of Systems and Software, 2008)
ContextWriting software for the current generation of parallel systems requires significant programmer effort, and the community is seeking alternatives that reduce effort while still achieving good performance. Objective Measure the effect of parallel programming models (message-passing vs. PRAM-like) on programmer effort. Design, setting, and subjects One group of subjects implemented sparse-matrix dense-vector multiplication using message-passing (MPI), and a second group solved the same problem using a PRAM-like model (XMTC). The subjects were students in two graduate-level classes: one class was taught MPI and the other was taught XMTC. Main outcome measures Development time, program correctness. Results Mean XMTC development time was 4.8 h less than mean MPI development time (95% confidence interval, 2.0–7.7), a 46% reduction. XMTC programs were more likely to be correct, but the difference in correctness rates was not statistically significant (p = .16). Conclusions XMTC solutions for this particular problem required less effort than MPI equivalents, but further studies are necessary which examine different types of problems and different levels of programmer experience.
Keywords: effort; empirical study; Message-passing; MPI; parallel programming; PRAM; XMT

Practical issues with using network tomography for fault diagnosis - Huang,Yiyi; Feamster, Nick; Teixeira,Renata (SIGCOMM Comput. Commun. Rev., 2008)
This paper investigates the practical issues in applying network tomography to monitor failures. We outline an approach for selecting paths to monitor, detecting and confirming the existence of a failure, correlating multiple independent observations into a single failure event, and applying existing binary networking tomography algorithms to identify failures. We evaluate the ability of network tomography algorithms to correctly detect and identify failures in a controlled environment on the VINI testbed.
Keywords: Environment; Fault detection; network tomography

The Randomized Coloring Procedure with Symmetry-Breaking - Pemmaraju,Sriram; Srinivasan, Aravind (Automata, Languages and ProgrammingAutomata, Languages and Programming, 2008)
A basic randomized coloring procedure has been used in probabilistic proofs to obtain remarkably strong results on graph coloring. These results include the asymptotic version of the List Coloring Conjecture due to Kahn, the extensions of Brooks’ Theorem to sparse graphs due to Kim and Johansson, and Luby’s fast parallel and distributed algorithms for graph coloring. The most challenging aspect of a typical probabilistic proof is showing adequate concentration bounds for key random variables. In this paper, we present a simple symmetry-breaking augmentation to the randomized coloring procedure that works well in conjunction with Azuma’s Martingale Inequality to easily yield the requisite concentration bounds. We use this approach to obtain a number of results in two areas: frugal coloring and weighted equitable coloring . A β-frugal coloring of a graph G is a proper vertex-coloring of G in which no color appears more than β times in any neighborhood. Let G = ( V , E ) be a vertex-weighted graph with weight function w : V →[0, 1] and let W = ∑ v ∈ V w ( v ). A weighted equitable coloring of G is a proper k -coloring such that the total weight of every color class is “large”, i.e., “not much smaller” than W / k ; this notion is useful in obtaining tail bounds for sums of dependent random variables.

Readability of scanned books in digital libraries - Quinn,A.J.; Hu,C.; Arisaka,T.; Rose,A.; Bederson, Benjamin B. (Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)

Reciprocity between the cerebellum and the cerebral cortex: Nonlinear dynamics in microscopic modules for generating voluntary motor commands - Wang,Jun; Dam,Gregory; Yildirim,Sule; Rand, William; Wilensky,Uri; Houk,James C. (Complexity, 2008)
The cerebellum and basal ganglia are reciprocally connected with the cerebral cortex, forming many loops that function as distributed processing modules. Here we present a detailed model of one microscopic loop between the motor cortex and the cerebellum, and we show how small arrays of these microscopic loops (CB modules) can be used to generate biologically plausible motor commands for controlling movement. A fundamental feature of CB modules is the presence of positive feedback loops between the cerebellar nucleus and the motor cortex. We use nonlinear dynamics to model one microscopic loop and to investigate its bistable properties. Simulations demonstrate an ability to program a motor command well in advance of command generation and an ability to vary command duration. However, control of command intensity is minimal, which could interfere with the control of movement velocity. To assess these hypotheses, we use a minimal nonlinear model of the neuromuscular (NM) system that translates motor commands into actual movements. Simulations of the combined CB-NM modular model indicate that movement duration is readily controlled, whereas velocity is poorly controlled. We then explore how an array of eight CB-NM modules can be used to control the direction and endpoint of a planar movement. In actuality, thousands of such microscopic loops function together as an array of adjustable pattern generators for programming and regulating the composite motor commands that control limb movements. We discuss the biological plausibility and limitations of the model. We also discuss ways in which an agent-based representation can take advantage of the modularity in order to model this complex system. © 2008 Wiley Periodicals, Inc. Complexity, 2008
Keywords: agent‐based modeling; cerebellum; equilibrium point control; motor command; motor cortex; Movement; neural network; nonlinear dynamics

Resolving arthropod phylogeny: exploring phylogenetic signal within 41 kb of protein-coding nuclear gene sequence - Regier,J. C; Shultz,J. W; Ganley,A. R.D; Hussey,A.; Shi,D.; Ball,B.; Zwick,A.; Stajich,J. E; Cummings, Michael P.; Martin,J. W; Cunningham,CW (Syst Biol, 2008)
This study attempts to resolve relationships among and within the four basal arthropod lineages (Pancrustacea, Myriapoda, Euchelicerata, Pycnogonida) and to assess the widespread expectation that remaining phylogenetic problems will yield to increasing amounts of sequence data. Sixty-eight regions of 62 protein-coding nuclear genes (approximately 41 kilobases (kb)/taxon) were sequenced for 12 taxonomically diverse arthropod taxa and a tardigrade outgroup. Parsimony, likelihood, and Bayesian analyses of total nucleotide data generally strongly supported the monophyly of each of the basal lineages represented by more than one species. Other relationships within the Arthropoda were also supported, with support levels depending on method of analysis and inclusion/exclusion of synonymous changes. Removing third codon positions, where the assumption of base compositional homogeneity was rejected, altered the results. Removing the final class of synonymous mutations–first codon positions encoding leucine and arginine, which were also compositionally heterogeneous–yielded a data set that was consistent with a hypothesis of base compositional homogeneity. Furthermore, under such a data-exclusion regime, all 68 gene regions individually were consistent with base compositional homogeneity. Restricting likelihood analyses to nonsynonymous change recovered trees with strong support for the basal lineages but not for other groups that were variably supported with more inclusive data sets. In a further effort to increase phylogenetic signal, three types of data exploration were undertaken. (1) Individual genes were ranked by their average rate of nonsynonymous change, and three rate categories were assigned–fast, intermediate, and slow. Then, bootstrap analysis of each gene was performed separately to see which taxonomic groups received strong support. Five taxonomic groups were strongly supported independently by two or more genes, and these genes mostly belonged to the slow or intermediate categories, whereas groups supported only by a single gene region tended to be from genes of the fast category, arguing that fast genes provide a less consistent signal. (2) A sensitivity analysis was performed in which increasing numbers of genes were excluded, beginning with the fastest. The number of strongly supported nodes increased up to a point and then decreased slightly. Recovery of Hexapoda required removal of fast genes. Support for Mandibulata (Pancrustacea + Myriapoda) also increased, at times to "strong" levels, with removal of the fastest genes. (3) Concordance selection was evaluated by clustering genes according to their ability to recover Pancrustacea, Euchelicerata, or Myriapoda and analyzing the three clusters separately. All clusters of genes recovered the three concordance clades but were at times inconsistent in the relationships recovered among and within these clades, a result that indicates that the a priori concordance criteria may bias phylogenetic signal in unexpected ways. In a further attempt to increase support of taxonomic relationships, sequence data from 49 additional taxa for three slow genes (i.e., EF-1 alpha, EF-2, and Pol II) were combined with the various 13-taxon data sets. The 62-taxon analyses supported the results of the 13-taxon analyses and provided increased support for additional pancrustacean clades found in an earlier analysis including only EF-1 alpha, EF-2, and Pol II.

Searching Electronic Health Records for Temporal Patterns in Patient Histories: A Case Study with Microsoft Amalga - Plaisant, Catherine; Lam,Stanley; Shneiderman, Ben; Smith,Mark S.; Roseman,David; Marchand,Greg; Gillam,Michael; Feied,Craig; Handler,Jonathan; Rappaport,Hank (AMIA Annual Symposium ProceedingsAMIA Annu Symp Proc, 2008)
As electronic health records (EHR) become more widespread, they enable clinicians and researchers to pose complex queries that can benefit immediate patient care and deepen understanding of medical treatment and outcomes. However, current query tools make complex temporal queries difficult to pose, and physicians have to rely on computer professionals to specify the queries for them. This paper describes our efforts to develop a novel query tool implemented in a large operational system at the Washington Hospital Center (Microsoft Amalga, formerly known as Azyxxi). We describe our design of the interface to specify temporal patterns and the visual presentation of results, and report on a pilot user study looking for adverse reactions following radiology studies using contrast.

Seasonal Cholera from Multiple Small Outbreaks, Rural Bangladesh - Stine,O. Colin; Alam,Munirul; Tang,Li; Nair,G. Balakrish; Siddique,A. Kasem; Faruque,Shah M.; Huq,Anwar; Rita R Colwell; Sack,R. Bradley; Morris,J. Glenn (Emerging Infectious DiseasesEmerg Infect Dis, 2008)
Clinical and environmental Vibrio cholerae organisms collected from February 2004 through April 2005 were systematically isolated from 2 rural Bangladeshi locales. Their genetic relatedness was evaluated at 5 loci that contained a variable number of tandem repeats (VNTR). The observed minimal overlap in VNTR patterns between the 2 communities was consistent with sequential, small outbreaks from local sources.

Sequence diversity and evolution of multigene families in Trypanosoma cruzi - Cerqueira,Gustavo C.; Bartholomeu,Daniella C.; DaRocha,Wanderson D.; Hou,Lihua; Freitas-Silva,Danielle M.; Machado,Carlos Renato; El‐Sayed, Najib M.; Teixeira,Santuza M.R. (Molecular and Biochemical Parasitology, 2008)
Several copies of genes belonging to three multigene families present in the genome of Trypanosoma cruzi were sequenced and comparatively analyzed across six different strains of the parasite belonging to the T. cruzi I lineage (Colombiana, Silvio X10 and Dm28c), the T. cruzi II lineage (Esmeraldo and JG) and a hybrid strain (CL Brener). For all three gene families analyzed, our results support the division in T. cruzi I and II lineages. Furthermore, in agreement with its hybrid nature, sequences derived from the CL Brener clone clustered together with T. cruzi II sequences as well as with a third group of sequences. Paralogous sequences encoding Amastin, an amastigote surface glycoprotein and TcAG48, an antigenic RNA binding protein, which are clustered in the parasite genome, present higher intragenomic variability in T. cruzi II and CL Brener strains, when compared to T. cruzi I strains. Paralogous sequences derived from the TcADC gene family, which encode various isoforms of adenylyl cyclases and are dispersed throughout the T. cruzi genome, exhibit similar degree of variability in all strains, except in the CL Brener strain, in which the sequences were more divergent. Several factors including mutation rates and gene conversion mechanisms, acting differently within the T. cruzi population, may contribute to create such distinct levels of sequence diversity in multigene families that are clustered in the T. cruzi genome.
Keywords: Amastin; Gene conversion; Genetic diversity; Multigene families; Trypanosoma cruzi

Sequential Kernel Density Approximation and Its Application to Real-Time Visual Tracking - Han,Bohyung; Comaniciu, D.; Zhu,Ying; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2008)
Visual features are commonly modeled with probability density functions in computer vision problems, but current methods such as a mixture of Gaussians and kernel density estimation suffer from either the lack of flexibility by fixing or limiting the number of Gaussian components in the mixture or large memory requirement by maintaining a nonparametric representation of the density. These problems are aggravated in real-time computer vision applications since density functions are required to be updated as new data becomes available. We present a novel kernel density approximation technique based on the mean-shift mode finding algorithm and describe an efficient method to sequentially propagate the density modes over time. Although the proposed density representation is memory efficient, which is typical for mixture densities, it inherits the flexibility of nonparametric methods by allowing the number of components to be variable. The accuracy and compactness of the sequential kernel density approximation technique is illustrated by both simulations and experiments. Sequential kernel density approximation is applied to online target appearance modeling for visual tracking, and its performance is demonstrated on a variety of videos.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Statistical Distributions; Subtraction Technique; Computer-Assisted; Models; Gaussian estimation; kernel density estimation; mean-shift mode finding algorithm; online target appearance modeling; probability density function; real-time computer vision application; real-time visual tracking; sequential kernel density approximation; visual f; Statistical; Motion; Pattern Recognition

Sex and Age Dimorphism of Myocardial Gene Expression in Nonischemic Human Heart Failure - Fermin,David R.; Barac,Ana; Lee,Sangjin; Polster,Sean P.; Hannenhalli, Sridhar; Bergemann,Tracy L.; Grindle,Suzanne; Dyke,David B.; Pagani,Francis; Miller,Leslie W.; Tan,Sarah; dos Remedios,Cris; et al. (Circulation: Cardiovascular Genetics, 2008)
Background— We report the first comprehensive analysis of gene expression differences by sex and age in left ventricular samples from 102 patients with dilated cardiomyopathy.Methods and Results— Gene expression data (HG-U133A gene chip, Affymetrix) were analyzed from 30 females and 72 males from 3 separate centers. More than 1800 genes displayed sexual dimorphism in the heart (adjusted P value <0.05). A significant number of these genes were highly represented in gene ontology pathways involved in ion transport and G-protein-coupled receptor signaling. Localization of these genes revealed enrichment on both the sex chromosomes as well as chromosomes 3, 4, and 14. The second goal of this study was to determine the effect of age on gene expression. Within the female cohort, >140 genes were differentially expressed in the <55 years age group compared with the >55 years age group. These genes were highly represented in gene ontology pathways involved in DNA damage. In contrast, zero genes in the male cohort <55 years met statistical significance when compared with the >55 years age group.Conclusions— Gene expression in dilated cardiomyopathy displayed evidence of sexual dimorphism similar to other somatic tissues and age dimorphism within the female cohort.

System-Level Optimization Model for a Snake-Inspired Robot Based on a Rectilinear Gait - Hopkins,James K.; Spranklin,Brent W.; Gupta, Satyandra K. (ASME, 2008)
Physical parameters of modules and gait parameters affect the overall snake-inspired robot performance. Hence the system-level optimization model has to concurrently optimize the module parameters and the gait. The equations of motion associated with the rectilinear gait are quite complex due to the changing topology of the rectilinear gait. Embedding these equations in the system-level optimization model leads to a computationally challenging formulation. This paper presents a system-level optimization model that utilizes a hierarchical optimization approach and meta-models of the pre-computed optimal gaits to reduce the complexity of the optimization model. This approach enabled us to use an experimentally validated physics-based model of the rectilinear gait and yet at the same time enabled us to create a system-level optimization model with a manageable complexity. A detailed case study is presented to show the importance of concurrently optimizing the module parameters and the gait using our model to obtain the optimal performance for a given mission.

Test case generator for GUITAR - Hackner,Daniel R.; Memon, Atif M. (Companion of the 30th international conference on Software engineering, 2008)
As GUIs become more popular, the need for GUI testing tools becomes greater. Many current GUI test generation techniques require proprietary tools and can be hard to use to their fullest potential. This paper outlines a new test case generation strategy, which enables testers to automatically produce cases in a widely used format. We hope that this strategy will encourage more complete GUI testing.
Keywords: code coverage; event-flow; Graphical user interfaces; gui ripping; integration tree; jfcunit; junit; Test Case Generation

A Tutorial of the Poisson Random Field Model in Population Genetics - Sethupathy,Praveen; Hannenhalli, Sridhar (Advances in Bioinformatics, 2008)
Population genetics is the study of allele frequency changes driven by various evolutionary forces such as mutation, natural selection, and random genetic drift. Although natural selection is widely recognized as a bona-fide phenomenon, the extent to which it drives evolution continues to remain unclear and controversial. Various qualitative techniques, or so-called “tests of neutrality”, have been introduced to detect signatures of natural selection. A decade and a half ago, Stanley Sawyer and Daniel Hartl provided a mathematical framework, referred to as the Poisson random field (PRF), with which to determine quantitatively the intensity of selection on a particular gene or genomic region. The recent availability of large-scale genetic polymorphism data has sparked widespread interest in genome-wide investigations of natural selection. To that end, the original PRF model is of particular interest for geneticists and evolutionary genomicists. In this article, we will provide a tutorial of the mathematical derivation of the original Sawyer and Hartl PRF model.

UMD_VDT, an Integration of Detection and Tracking Methods for Multiple Human Tracking - Tran,S.; Lin,Z.; Harwood,D.; Davis, Larry S. (Multimodal Technologies for Perception of Humans, 2008)
This paper presents a cooperative body part labeling and tracking algorithm for locating body parts in a videoimage sequence. The body part labeling procedure is used to initialize the tracking procedure and to prevent tracking from getting lost; and the tracking procedure is used to analyze frames that cannot be handled reliably by the labeling procedure. This results in an automatic and robust body part tracking system. Unlike previous work that always start tracking from the first frame which may be difficult to analyze, our tracking procedure starts with some key frames in which body parts can be located reliably. Key frames are selected based on a labeling confidence measure which evaluates the similarity between the human model and the image features. The labeled body parts are tracked in-between frames based on such cues as shape, color, and location interpolated between key frames iteratively. The proposed algorithm has been applied to analyze NASA videotapes in which crew members present challenging postures of bending, twisting, and rotating in a space station. The experimental results demonstrate the effectiveness of the proposed algorithm.