Partnerships between academic institutions and industry for internships can benefit both parties. Experiential learning may help students prepare for their futures, while employers can help identify potential talent for jobs. Although the student perspective has been well explored, scholarship around employers remains limited. In this experience report, we describe a micro-internship program for (n=95) computing students that combined 7 weeks of university-led upskilling workshops with three weeks of practical experience with (n=18) employers to complete challenge projects in small groups. We elaborate further on the preparation and implementation required, as well as detail our qualitative evaluation of the program from the employer perspective. Situated learning theory (SLT) guided the investigation, which involved gathering feedback from employers through semi-structured interviews. Applying reflexive thematic analysis to employer interviews, we inductively examined: (1) how industry mentors integrated students into professional computing communities of practice (COP), (2) the mechanisms they employed to facilitate students' legitimate peripheral participation, (3) their observations of growth in students' technical and professional skills and identity formation, and (4) reciprocal learning that occurred during the internship period. Six resulting themes were then deductively mapped to SLT sub-constructs to further understand employers' impact during computing internships. Employers facilitated authentic problem solving and real-world learning experiences for students while gaining new perspectives and insights regarding new technology and problem-solving approaches in the process.

Making the transition from academia to industry can be a rite of passage for college graduates. Internships allow students to gain experience in small doses, and help shape their career goals, actions, and decisions. We sought to explore how employers perceived undergraduate computing students' performance and experience in a three-week micro-internship. We applied the boundary crossing (BC) framework and analyzed and interpreted n = 49 quotes extracted from semi-structured interviews with three industry mentors using the methodology of framework analysis. We examined the quotes and categorized them into one of four mechanisms of BC: identification, coordination, reflection, and transformation. The greatest number of BC mechanisms reported was that of coordination at the interpersonal level (33%), where the interns interacted with their mentors to navigate the differences in expectations and tasks that they had already identified. 51% of the BC mechanisms were reported to be at the interpersonal level, while six instances of transformation at the institutional level were also observed in the analysis. Our study's results can help administrators and industry mentors gain insight into how computing students may leverage mentorship to navigate professional dynamics.

In coastal river systems, floods, often during major storms or king tides, severely threaten lives and property. However, hydraulic structures such as dams, gates, pumps, and reservoirs exist in these river systems, and these floods can be mitigated or even prevented by strategically releasing water before extreme weather events. A standard approach used by local water management agencies is the “rule-based” method, which specifies predetermined water prereleases based on historical human experience, but which tends to result in excessive or inadequate water release. Iterative optimization methods that rely on detailed physics-based models for prediction are an alternative approach. Whereas, such methods tend to be computationally intensive, requiring hours or even days to solve the problem optimally. In this paper, we propose a Forecast Informed Deep Learning Architecture, FIDLAR, to achieve rapid and near-optimal flood management with precise water prereleases. FIDLAR seamlessly integrates two neural network modules: one called the Flood Manager, which is responsible for generating water pre-release schedules, and another called the Flood Evaluator, which evaluates those generated schedules. The Evaluator module is pre-trained separately, and its gradient-based feedback is utilized to train the Manager model, ensuring near-optimal water pre-releases. We have conducted experiments with a flood-prone coastal area in South Florida. Results show that FIDLAR is several orders of magnitude faster than currently used physics-based approaches while outperforming baseline methods with improved water pre-release schedules.

Accurate weather forecasting is critical for science and society. However, existing methods have not achieved the combination of high accuracy, low uncertainty, and high computational efficiency simultaneously. On one hand, traditional numerical weather prediction (NWP) models are computationally intensive because of their complexity. On the other hand, most machine learning-based weather prediction (MLWP) approaches offer efficiency and accuracy but remain deterministic, lacking the ability to capture forecast uncertainty. To tackle these challenges, we propose a conditional diffusion model, CoDiCast, to generate global weather prediction, integrating accuracy and uncertainty quantification at a modest computational cost. The key idea behind the prediction task is to generate realistic weather scenarios at a future time point, conditioned on observations from the recent past. Due to the probabilistic nature of diffusion models, they can be properly applied to capture the uncertainty of weather predictions. Therefore, we accomplish uncertainty quantifications by repeatedly sampling from stochastic Gaussian noise for each initial weather state and running the denoising process multiple times. Experimental results demonstrate that CoDiCast outperforms several existing MLWP methods in accuracy, and is faster than NWP models in inference speed. Our model can generate 6-day global weather forecasts, at 6-hour steps and 5.625-degree latitude-longitude resolutions, for over 5 variables, in about 12 minutes on a commodity A100 GPU machine with 80GB memory. The source code is available at https://github.com/JimengShi/CoDiCast.

The expanding applications of technology across sectors, coupled with the rising demand for qualified graduates, necessitate consideration of new ways to increase engagement with the discipline of computing. Towards this goal, we established a week-long program for non-majors to explore computing concepts (e.g., artificial intelligence) and aid in their professional development (e.g., through fostering presentation skills). We also sought to cultivate a community and incorporated peer and industry mentorship. In the experience report that follows, we detail the novel program and its evolution over five iterations across two institutions. We applied the Community of Inquiry framework to contextualize the programmatic design and its evaluation. Surveys collected daily gave insight into the student perspective on the various lessons and activities offered, with feedback from up to n = 141 students in total. Apart from including Likert-scale ratings to quantify preferences for each session, open-ended responses allowed greater understanding around what may have been viewed favorably or what could require further improvements. Based on the findings, we highlight how aspects of the experience may have contributed to the participants' engagement with the content, with others involved in the program, and with respect to learning outcomes. The session details and reflections presented are intended to inform as well as offer inspiration to other educators and administrators who may seek to introduce students from other majors to computing.

Internships can allow computing students to cultivate valuable skills while offering them practical insight into industry. The aim of our study was to gain an understanding of undergraduate computing students' perceptions of a three-week micro-internship (called a ''Sprinternship'') program. We sought to explore their experiences throughout its duration, which included a priori professional and technical development training. We applied the methodology of phenomenography, conducting semi-structured interviews with n = 27 students and taking the developmental approach to the analysis. We noted cognitive, affective, interpersonal, and career-oriented factors often influenced students' views of the experience. In this work, we share the seven categories of description that emerged from the analysis and provide the implications. The findings of this investigation can offer guidance for educators and administrators looking to create similar short-term internship opportunities.

BACKGROUND: While protein-protein docking is fundamental to our understanding of how proteins interact, scoring protein-protein complex conformations is a critical component of successful docking programs. Without accurate and efficient scoring functions to differentiate between native and non-native binding complexes, the accuracy of current docking tools cannot be guaranteed. Although many innovative scoring functions have been proposed, a good scoring function for docking remains elusive. Deep learning models offer alternatives to using explicit empirical or mathematical functions for scoring protein-protein complexes. RESULTS: In this study, we perform a comprehensive survey of the state-of-the-art scoring functions by considering the most popular and highly performant approaches, both classical and deep learning-based, for scoring protein-protein complexes. The methods were also compared based on their runtime as it directly impacts their use in large-scale docking applications. CONCLUSIONS: We evaluate the strengths and weaknesses of classical and deep learning-based approaches across seven public and popular datasets to aid researchers in understanding the progress made in this field.

Extreme events are of great importance since they often represent impactive occurrences. For instance, in terms of climate and weather, extreme events might be major storms, floods, extreme heat or cold waves, and more. However, they are often located at the tail of the data distribution. Consequently, accurately predicting these extreme events is challenging due to their rarity and irregularity. Prior studies have also referred to this as the out-of-distribution (OOD) problem, which occurs when the distribution of the test data is substantially different from that used for training. In this work, we propose two strategies, reweighting and fine-tuning, to tackle the challenge. Reweighting is a strategy used to force machine learning models to focus on extreme events, which is achieved by a weighted loss function that assigns greater penalties to the prediction errors for the extreme samples relative to those on the remainder of the data. Unlike previous intuitive reweighting methods based on simple heuristics of data distribution, we employ meta-learning to dynamically optimize these penalty weights. To further boost the performance on extreme samples, we start from the reweighted models and fine-tune them using only rare extreme samples. Through extensive experiments on multiple data sets, we empirically validate that our meta-learning-based reweighting outperforms existing heuristic ones, and the fine-tuning strategy can further increase the model performance. More importantly, these two strategies are model-agnostic, which can be implemented on any type of neural network for time series forecasting. The open-sourced code is available at https://github.com/JimengShi/ReFine.

The demand for skilled workers in computing continues to outpace the supply of qualified graduates. Despite the need, hiring can be challenging, both for employers seeking prospective employees and for students who may be unsure where to apply, daunted by technical interviews, and/or feeling the effects of imposter phenomena. In this experience report, we describe a program established to reduce some of these hurdles by pairing (n = 63) undergraduate students with (n = 7) companies to offer short-term computing internships, called a Sprinternship. Sprinternships eliminated the hurdle of technical interviews, provided students with training beforehand to offer foundational knowledge, and placed them in teams to work on challenge projects. We describe the details of the program and our investigation of its impact. Social Cognitive Career Theory guided the inquiry as we took a mixed-methods approach to understand the students' experiences and the potential impact on their self-efficacy, outcome expectations, and career goals. Quantitative analysis revealed a statistically significant increase in students' confidence in computing, something echoed in their open-ended responses. Thematic analysis further yielded that Sprinternships were meaningful in two major areas: Goals and Learning Experiences. The program aided in students' self-discovery, made them feel accomplished, and strengthened their industry ambitions. Responses also revealed positive and negative programmatic aspects to consider for future iterations. We hope that our description of the Sprinternships, findings, and recommendations can be useful to other practitioners looking to engage students with practical learning and enhance their graduate employability.

Graph neural networks (GNNs) have demonstrated remarkable success in various real-world applications. However, they often inadvertently inherit and amplify existing societal bias. Most existing approaches for fair GNNs tackle this bias issue by assuming that discrimination solely arises from sensitive attributes such as race or gender, while disregarding the prevalent labeling bias that exists in real-world scenarios. Additionally, prior works attempting to address label bias through counterfactual fairness often fail to consider the veracity of counterfactual samples. This paper aims to bridge these gaps by investigating the identification of authentic counterfactual samples within complex graph structures and proposing strategies for mitigating labeling bias guided by causal analysis. Our proposed learning model, known as Real Fair Counterfactual GNNs (RFCGNN), also goes a step further by considering the learning disparity resulting from imbalanced data distribution across different demographic groups in the graph. Extensive experiments conducted on three real-world datasets and a synthetic dataset demonstrate the effectiveness and practicality of the proposed RFCGNN approach.

The papers in this special section were presented at the 16th International Symposium on Bioinformatics Research and Applications (ISBRA 2020), which was held virtually, on December 1-4, 2020. The ISBRA symposium provides a forum for the exchange of ideas and results among researchers, developers, and practitioners working on all aspects of Bioinformatics and computational biology and their applications.

BACKGROUND: Partial Least-Squares Discriminant Analysis (PLS-DA) is a popular machine learning tool that is gaining increasing attention as a useful feature selector and classifier. In an effort to understand its strengths and weaknesses, we performed a series of experiments with synthetic data and compared its performance to its close relative from which it was initially invented, namely Principal Component Analysis (PCA). RESULTS: We demonstrate that even though PCA ignores the information regarding the class labels of the samples, this unsupervised tool can be remarkably effective as a feature selector. In some cases, it outperforms PLS-DA, which is made aware of the class labels in its input. Our experiments range from looking at the signal-to-noise ratio in the feature selection task, to considering many practical distributions and models encountered when analyzing bioinformatics and clinical data. Other methods were also evaluated. Finally, we analyzed an interesting data set from 396 vaginal microbiome samples where the ground truth for the feature selection was available. All the 3D figures shown in this paper as well as the supplementary ones can be viewed interactively at http://biorg.cs.fiu.edu/plsda CONCLUSIONS: Our results highlighted the strengths and weaknesses of PLS-DA in comparison with PCA for different underlying data models.

MOTIVATION: Bacterial metagenomics profiling for metagenomic whole sequencing (mWGS) usually starts by aligning sequencing reads to a collection of reference genomes. Current profiling tools are designed to work against a small representative collection of genomes, and do not scale very well to larger reference genome collections. However, large reference genome collections are capable of providing a more complete and accurate profile of the bacterial population in a metagenomics dataset. In this paper, we discuss a scalable, efficient and affordable approach to this problem, bringing big data solutions within the reach of laboratories with modest resources. RESULTS: We developed Flint, a metagenomics profiling pipeline that is built on top of the Apache Spark framework, and is designed for fast real-time profiling of metagenomic samples against a large collection of reference genomes. Flint takes advantage of Spark's built-in parallelism and streaming engine architecture to quickly map reads against a large (170 GB) reference collection of 43 552 bacterial genomes from Ensembl. Flint runs on Amazon's Elastic MapReduce service, and is able to profile 1 million Illumina paired-end reads against over 40 K genomes on 64 machines in 67 s-an order of magnitude faster than the state of the art, while using a much larger reference collection. Streaming the sequencing reads allows this approach to sustain mapping rates of 55 million reads per hour, at an hourly cluster cost of $8.00 USD, while avoiding the necessity of storing large quantities of intermediate alignments. AVAILABILITY AND IMPLEMENTATION: Flint is open source software, available under the MIT License (MIT). Source code is available at https://github.com/camilo-v/flint. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Computing centrality is a foundational concept in social networking that involves finding the most "central" or important nodes. In some biological networks defining importance is difficult, which then creates challenges in finding an appropriate centrality algorithm. RESULTS: We instead generalize the results of any k centrality algorithms through our iterative algorithm MATRIA, producing a single ranked and unified set of central nodes. Through tests on three biological networks, we demonstrate evident and balanced correlations with the results of these k algorithms. We also improve its speed through GPU parallelism. CONCLUSIONS: Our results show iteration to be a powerful technique that can eliminate spatial bias among central nodes, increasing the level of agreement between algorithms with various importance definitions. GPU parallelism improves speed and makes iteration a tractable problem for larger networks.

Motivation: Software pipelines have become almost standardized tools for microbiome analysis. Currently many pipelines are available, often sharing some of the same algorithms as stages. This is largely because each pipeline has its own source language and file formats, making it typically more economical to reinvent the wheel than to learn and interface to an existing package. We present Plugin-Based Microbiome Analysis (PluMA), which addresses this problem by providing a lightweight back end that can be infinitely extended using dynamically loaded plugin extensions. These can be written in one of many compiled or scripting languages. With PluMA and its online plugin pool, algorithm designers can easily plug-and-play existing pipeline stages with no knowledge of their underlying implementation, allowing them to efficiently test a new algorithm alongside these stages or combine them in a new and creative way. Results: We demonstrate the usefulness of PluMA through an example pipeline (P-M16S) that expands an obesity study involving gut microbiome samples from the mouse, by integrating multiple plugins using a variety of source languages and file formats, and producing new results. Availability and implementation: Links to github repositories for the PluMA source code and P-M16S, in addition to the plugin pool are available from the Bioinformatics Research Group (BioRG) at: http://biorg.cis.fiu.edu/pluma.

BACKGROUND: The notion of centrality is used to identify "important" nodes in social networks. Importance of nodes is not well-defined, and many different notions exist in the literature. The challenge of defining centrality in meaningful ways when network edges can be positively or negatively weighted has not been adequately addressed in the literature. Existing centrality algorithms also have a second shortcoming, i.e., the list of the most central nodes are often clustered in a specific region of the network and are not well represented across the network. METHODS: We address both by proposing Ablatio Triadum (ATria), an iterative centrality algorithm that uses the concept of "payoffs" from economic theory. RESULTS: We compare our algorithm with other known centrality algorithms and demonstrate how ATria overcomes several of their shortcomings. We demonstrate the applicability of our algorithm to synthetic networks as well as biological networks including bacterial co-occurrence networks, sometimes referred to as microbial social networks. CONCLUSIONS: We show evidence that ATria identifies three different kinds of "important" nodes in microbial social networks with different potential roles in the community.

In order to make multiple copies of a target sequence in the laboratory, the technique of Polymerase Chain Reaction (PCR) requires the design of "primers", which are short fragments of nucleotides complementary to the flanking regions of the target sequence. If the same primer is to amplify multiple closely related target sequences, then it is necessary to make the primers "degenerate", which would allow it to hybridize to target sequences with a limited amount of variability that may have been caused by mutations. However, the PCR technique can only allow a limited amount of degeneracy, and therefore the design of degenerate primers requires the identification of reasonably well-conserved regions in the input sequences. We take an existing algorithm for designing degenerate primers that is based on clustering and parallelize it in a web-accessible software package GPUDePiCt, using a shared memory model and the computing power of Graphics Processing Units (GPUs). We test our implementation on large sets of aligned sequences from the human genome and show a multi-fold speedup for clustering using our hybrid GPU/CPU implementation over a pure CPU approach for these sequences, which consist of more than 7,500 nucleotides. We also demonstrate that this speedup is consistent over larger numbers and longer lengths of aligned sequences.

The snake algorithm has been proposed to solve many remote sensing and computer vision problems such as object segmentation, surface reconstruction, and object tracking. This paper introduces a framework for 3-D building model construction from LIDAR data based on the snake algorithm. It consists of nonterrain object identification, building and tree separation, building topology extraction, and adjustment by the snake algorithm. The challenging task in applying the snake algorithm to building topology adjustment is to find the global minima of energy functions derived for 2-D building topology. The traditional snake algorithm uses dynamic programming for computing the global minima of energy functions which is limited to snake problems with 1-D topology (i.e., a contour) and cannot handle problems with 2-D topology. In this paper, we have extended the dynamic programming method to address the snake problems with a 2-D planar topology using a novel graph reduction technique. Given a planar snake, a set of reduction operations is defined and used to simplify the graph of the planar snake into a set of isolated vertices while retaining the minimal energy of the graph. Another challenging task for 3-D building model reconstruction is how to enforce different kinds of geometric constraints during building topology refinement. This framework proposed two energy functions, deviation and direction energy functions, to enforce multiple geometric constraints on 2-D topology refinement naturally and efficiently. To examine the effectiveness of the framework, the framework has been applied on different data sets to construct 3-D building models from airborne LIDAR data. The results demonstrate that the proposed snake algorithm successfully found the global optima in polynomial time for all of the building topologies and generated satisfactory 3-D models for most of the buildings in the study areas.

We introduce the concept of Avatar problems that deal with situations where each entity has multiple copies or "avatars" and the solutions are constrained to use exactly one of the avatars. The resulting set of problems show a surprising range of hardness characteristics and elicit a variety of algorithmic solutions. Many Multiple geometric avatar problems are considered. In particular, we show how to extend the concept of epsilon-kernels to find approximation algorithms for geometric avatar problems. Results for metric space graph avatar problems are also presented.

The six papers in this special section cover a broad range of bioinformatics topics, ranging from comparative genomics and phylogenetics to population genetics, and from RNA structure prediction to analysis of protein-protein interaction networks.

In this article we present a new approach - weighted consensus clustering to identify the clusters in Protein-protein interaction (PPI) networks where each cluster corresponds to a group of functionally similar proteins. In weighed consensus clustering, different input clustering results weigh differently, i.e., a weight for each input clustering is introduced and the weights are automatically determined by an optimization process. We evaluate our proposed method with standard measures such as modularity, normalized mutual information (NMI) and the Gene Ontology (GO) consortium database and compare the performance of our approach with other consensus clustering methods. Experimental results demonstrate the effectiveness of our proposed approach.

With the unprecedented growth in the size of sequence and structure databases, knowledge-based methods have become increasingly feasible for protein structure prediction. We developed a branch-and-bound method for structlets-based protein structure assembly. We explore the effectiveness of this approach by examining its capability to reconstruct the 3D structure of some proteins with known 3D structures. Although our algorithm involves exhaustive search, our BestFirst implementation of a branch-and bound strategy is able to eliminate around 2/3 of the total search space in order to find the optimal 3D assembly for a protein of interest.

In the post-genomic era, the organization of genes into networks has played an important role in characterizing the functions of individual genes and the interplay between them. It is also vital in understanding complex cellular processes and their dynamics. Despite advances, gene network prediction still remains a challenge. Recently, heterogeneous genomic and proteomic data were integrated to generate a functional network of yeast genes. The Gene Ontology (GO) project has integrated information from multiple data sources to annotate genes to specific biological process. Generating gene networks using GO annotations is a novel and alternative way to efficiently integrate heterogeneous data sources. In this paper, we present a novel approach to automatically generate a functional network of yeast genes using Gene Ontology (GO) annotations. An information theoretic semantic similarity (SS) was calculated between every pair of genes based on the method proposed by Resnik. This SS score was then used to predict linkages between genes, to generate a functional network. An alternative approach has been proposed using a measure called log likelihood score (LLS). The functional networks predicted using the SS and LLS measures were compared. We discussed our experiments on generating reliable functional gene networks and concluded that the functional network generated by SS scores is comparable to or better than those obtained using LLS scores.

Given an arbitrary real constant ε > 0, and a geometric graph G in d -dimensional Euclidean space with n points, O ( n ) edges, and constant dilation, our main result is a data structure that answers (1 + ε)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O ( n log n ) time using O ( n log n ) space. This represents the first data structure that answers (1 + ε)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.

While much research has been done on finding similarities between protein sequences, there has not been the same progress on finding similarities between protein structures. Here we report a new algorithm (SBLAST) which discovers the largest common substructures between two proteins using a triangle-based variant of the geometric hashing of protein structures algorithm. The algorithm selects triples (triangles) of selected Cμ atoms from all proteins in a protein structure database and creates a hash table using a key based on the three inter-atomic distances. Hash table hits from the triangles of a query protein are extended recursively to determine the largest common substructures less than a threshold deviation level (rmsd). Comparisons between a query protein and a preprocessed protein database can be performed in parallel. Because SBLAST does not rely on protein sequence alignment, common substructures can be detected in the absence of sequence conservation. SBLAST has been tested using the ASTRAL subset of the PDB.

In this paper, we have modified a constrained clustering algorithm to perform exploratory analysis on gene expression data using prior knowledge presented in the form of constraints. We have also studied the effectiveness of various constraints sets. To address the problem of automatically generating constraints from biological text literature, we considered two methods (cluster-based and similarity-based). We concluded that incomplete information in the form of constraints set should be generated carefully, in order to outperform the standard clustering algorithm, which works on the data source without any constraints. For sufficiently large constraints sets, the constrained clustering algorithm outperformed the MSC algorithm. The novelty of research presented here is the study of effectiveness of constraints sets and robustness of the constrained clustering algorithm using multiple sources of biological data, and incorporating biomedical text literature into constrained clustering algorithm in form of constraints sets.

The "CyberBridges" pilot project is an innovative model for creating a new generation of scientists and engineers who are capable of fully integrating cyberinfrastructure into the whole educational, professional, and creative process of their respective disciplines. CyberBridges augments graduate student education to include a foundation of understanding in advanced networking and grid infrastructure for high performance computing, and bridges the divide between the information technology community and diverse science and engineering disciplines. We demonstrate the effectiveness of CyberBridges by providing four case studies. Groundwork has begun to extend the outreach of CyberBridges for international research and education collaborations.

Energy-minimizing active contour models (snakes) have been proposed for solving many computer vision problems such as object segmentation, surface reconstruction, and object tracking. Dynamic programming which allows natural enforcement of constraints is an effective method for computing the global minima of energy functions. However, this method is only limited to snake problems with one dimensional (ID) topology (i.e., a contour) and cannot handle problems with two-dimensional (2D) topology. In this paper, we have extended the dynamic programming method to address the snake problems with 2D topology using a novel graph reduction algorithm. Given a 2D snake with first order energy terms, a set of reduction operations are defined and used to simplify the graph of the 2D snake into one single vertex while retaining the minimal energy of the snake. The proposed algorithm has a polynomial-time complexity bound and the optimality of the solution for a reducible 2D snake is guaranteed. However, not all types of 2D snakes can be reduced into one single vertex using the proposed algorithm. The reduction of general planar snakes is an NP-complete problem. The proposed method has been applied to optimize 2D building topology extracted from airborne LIDAR data to examine the effectiveness of the algorithm. The results demonstrate that the proposed approach successfully found the global optima for over 98% of building topology in a polynomial time.

MOTIVATION: Traditional phylogenetic methods assume tree-like evolutionary models and are likely to perform poorly when provided with sequence data from fast-evolving, recombining viruses. Furthermore, these methods assume that all the sequence data are from contemporaneous taxa, which is not valid for serially-sampled data. A more general approach is proposed here, referred to as the Sliding MinPD method, that reconstructs evolutionary networks for serially-sampled sequences in the presence of recombination. RESULTS: Sliding MinPD combines distance-based phylogenetic methods with automated recombination detection based on the best-known sliding window approaches to reconstruct serial evolutionary networks. Its performance was evaluated through comprehensive simulation studies and was also applied to a set of serially-sampled HIV sequences from a single patient. The resulting network organizations reveal unique patterns of viral evolution and may help explain the emergence of disease-associated mutants and drug-resistant strains with implications for patient prognosis and treatment strategies.

In this paper, we study the problems of motif discovery and gene regulation. First, although the sliding window technique based on profiles or consensus sequences is a standard method for discovering motifs in the genomes with prior knowledge of transcription binding sites in orthologous genes from related organisms, it usually has high computational costs. In this paper, we propose an efficient approximation method employing randomized algorithms to identify motifs. The approximation method can be easily combined with the sliding-window technique for efficient and accurate motif discovery. Second, we mine frequent motif combinations and sequential motif patterns to investigate the regulatory relationships between motifs and provide a better understanding of gene expression, regulation, and transcription

UNLABELLED: Serial NetEvolve is a flexible simulation program that generates DNA sequences evolved along a tree or recombinant network. It offers a user-friendly Windows graphical interface and a Windows or Linux simulator with a diverse selection of parameters to control the evolutionary model. Serial NetEvolve is a modification of the Treevolve program with the following additional features: simulation of serially-sampled data, the choice of either a clock-like or a variable rate model of sequence evolution, sampling from the internal nodes and the output of the randomly generated tree or network in our newly proposed NeTwick format. AVAILABILITY: From website http://biorg.cis.fiu.edu/SNE Contacts: [email protected] SUPPLEMENTARY INFORMATION: Manual and examples available from http://biorg.cis.fiu.edu/SNE.

Given a set V of n points in $\IR^d$ and a real constant t>1, we present the first O(nlog n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner on V is a connected graph G = (V,E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all $u,v\in V$, the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight $O(1)\cdot wt(MST)$, and its degree is bounded by a constant.

There are several results available in the literature dealing with efficient construction of t-spanners for a given set S of n points in $\IR^d$. t-spanners are Euclidean graphs in which distances between vertices in G are at most t times the Euclidean distances between them; in other words, distances in G are "stretched" by a factor of at most t. We consider the interesting dual problem: given a Euclidean graph G whose vertex set corresponds to the set S, compute the stretch factor of G, i.e., the maximum ratio between distances in G and the corresponding Euclidean distances. It can trivially be solved by solving the all-pairs-shortest-path problem. However, if an approximation to the stretch factor is sufficient, then we show it can be efficiently computed by making only O(n) approximate shortest path queries in the graph G. We apply this surprising result to obtain efficient algorithms for approximating the stretch factor of Euclidean graphs such as paths, cycles, trees, planar graphs, and general graphs. The main idea behind the algorithm is to use Callahan and Kosaraju's well-separated pair decomposition.

WC study a variety of geometric network optimization prob lcms on a set of points, in which we are given a resource bound, a, on the total length of the network, and our ob jcctivc is to maximize the number of points visited (or the total "value" of points visited), In particular, we resolve the well-publicized open problem on the approximabiity of the rooted "orienteering problem" for the case in which the sites are given as points in the plane and the network required is a cycle.We obtain a 2approximation for this problem, We also obtain approximation algorithms for variants of this problem in which the network required is a tree (S-approximation) or a path Q-approximation).No prior approximation bounds were known for any of these problems,We also obtain improved approximation algorithms for geometric instances of the unrooted orienteering problem, where we obtain a 2-approximation for both the cycle and tree versions of the problem on points in the plane, as well as a G-approximation for the tree version in edge-weighted graphs, E'urther, we study generalizations of the basic orienteering problem, to the case of multiple roots, sites that are polygonnl regions, etc., where we again give the first known approximation results.Our methods are based on some new tools which may be of interest in their own right: ( 1) some new results on m-'Department of Applied Mathematics and Statistics, State Univcrsitv of New York.Stonv Brook.NY 11794-3600: aat~o6smb .ounyob.

Let S be a set of n points in lKd, and k m integer such that 1 5 k 5 n -2.Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path.Our results include (i) an algorithm with running time O(n logdB1 n + kn log log n + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n logn + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with rllnning time O(n logn+&n) that constructs a spanner of degree O(s), whose total edge length is bounded by G(2) times the weight of a miuimum spanning tree of S, and that is resilient to k edge or vertex faults.Here, c is a constant that is independent of n and Ic.

Let G=(V,E) be a n-vertex connected graph with positive edge weights. A subgraph G′ is a t-spanner if for all u,v ∈ V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(nlog2n) time algorithm which, given a set V of n points in k-dimensional space, and any constant t>1, produces a t-spanner of the complete Euclidean graph of V. This algorithm retains the spirit of a recent O(n3logn)-time greedy algorithm which produces t-spanners with a small number of edges and a small total edge weight; we use graph clustering techniques to achieve a more efficient implementation. Our spanners have similar size and weight sparseness as those constructed by the greedy algorithm.

Given a simple polygon, we present an optimal linear-time algorithm that computes the shortest illuminating line segment, if one exists; else it reports that none exists. This solves an intriguing open problem by improving the O(n log n)-time algorithm [Ke87] for computing such a segment. 1

Let V be a set of n points in 3-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any u and v in V, the length of the shortest path from u to v in the spanner is at most ttimes d(u, v). We show that for any t > 1, a greedy algorithm produces a t-spanner with O(n) edges, and total edge weight O(1).wt(MST), where MST is a minimum spanning tree of V.

Let G=(V,E) be an n-vertex connected graph with positive edge weights. A subgraph G′ = (V,E′) is a t-spanner of G if for all u, v ε V,the weighted distance between u and v in G′ is at most t times the weighted distance between u and v in G. We consider the problem of constructing sparse spanners, and the weight, defined as the sum of the edge weights in the spanner. In this paper, we concentrate on constructing spanners of small weight.