Single-cell sequencing (SCS) enables the study of tumor evolution at the resolution of a single cell. SCS data can be represented as a binary matrix, where the $ij$-th entry indicates whether cell $i$ has mutation $j$. There is a simple characterization of when the data is compatible with a perfect phylogeny based on the absence of a special "conflict" submatrix. In practice, SCS data are noisy, which raises the natural question of the minimum number of entries that must be flipped in the data matrix to make it conflict-free and thus compatible with a perfect phylogeny. Furthermore, the likelihood of a false positive is several orders of magnitude smaller than that of a false negative rate. We consider a variation of the minimum-flip problem parameterized by the number of false positives. Restricting the false positive rate to a small range, often multiple optimal solutions can arise. While previous work has focused on reconstructing a single optimal phylogenetic tree, we are interested in the relations that are present among all optimal solutions; we call such relations essential. In this work, we propose an efficient algorithm based on integer linear programming to determine the essential relation on the cells given an SCS data matrix. We test our tool, ${\sf EssentCell}$, on several data sets and discuss the results found.

Phenotypes are the observable characteristics of an individual organism. Predicting quantitative phenotypes from genomic variation remains challenging when causal signals span both local motifs and distal regulatory context. Building on Frequented Regions (FRs), which represent subsequences conserved across genomes, extracted from a pangenome graph, we compare six modeling strategies on five yeast growth phenotypes: Random Forest (RF) on FR counts, RF on FR sequences, 1D convolutional neural networks on FR sequences, Long Short-Term Memory (LSTM) on FR sequences, a Genome-wide Association Study (GWAS) baseline, and a sequence-based Enformer model trained on raw FR nucleotide windows. Across the five phenotypes, all sequence-based baselines improve upon RF (FR counts) and GWAS, confirming the value of sequence context. Enformer consistently outperforms CNN/LSTM on all five phenotypes and surpasses RF (FR-sequences) on three of five, while remaining competitive on the others. These results indicate that when long-range dependencies contribute to trait variation, transformer-based modeling of raw sequence windows may yield tangible gains over k-mer and local-pattern learners; conversely, for phenotypes dominated by short-range signals, lightweight baselines may remain competitive. These findings suggest that while short-range motif statistics can suffice for certain phenotypes, deep learning architectures that integrate positional context and distal interactions can yield additional gains, particularly when phenotypic variation is linked to dispersed regulatory signals.

Abstract Minimum flow decomposition (MFD) — the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow — is a classical problem in Computer Science, and variants of it are powerful models in a different fields such as Bioinformatics and Transportation. Even on acyclic graphs, the problem is NP-hard, and most practical solutions have been via heuristics or approximations. While there is an extensive body of research on acyclic graphs, currently there is no exact solution on graphs with cycles. In this paper we present the first ILP formulation for three natural variants of the MFD problem in graphs with cycles, asking for a decomposition consisting only of weighted source-to-sink paths or cycles, trails, and walks, respectively. On three datasets of increasing levels of complexity from both Bioinformatics and Transportation, our approaches solve any instance in under 12 minutes. Our implementations are freely available at https://github.com/algbio/MFD-ILP .

Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [Mäkinen et al., TALG 2019] and even linear time [Cáceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new fast pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders of magnitude.

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation X on a directed graph G into weighted source-to-sink paths whose weighted sum equals X . We show that, for acyclic graphs, considering the width of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of width-stable graphs, for which a popular heuristic is a O (log Val ( X ))-approximation ( Val ( X ) being the total flow of X ), and strengthen its worst-case approximation ratio from \(\Omega (\sqrt {m})\) to Ω ( m /log m ) for sparse graphs, where m is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖ X ‖ being the maximum absolute value of X on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖ X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ 2018 ], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

A pangenome represents the entire sequence content and variation of a population. As collections of complete reference quality genomes become more common, so does the prevalence of pangenomes, necessitating the need for scalable computational methods for their analysis. Previously, we developed FindFRs for identifying Frequented Regions in pangenome graphs, where a Frequented Region is a subgraph that is frequently traversed by multiple sequences. In this work, we propose FindFRs3, which is an updated version of FindFRs capable of identifying Frequented Regions with improved runtime and memory efficiency, enabling the analysis of much larger pangenome graphs. In addition, FindFRs3 identifies Frequented Region Variants (the unique subpaths through each region). We demonstrate the utility of these variants by using them as input features for machine learning models that can predict genotype-to-phenotype associations in a large yeast pangenome. Biological insights gained from these variants show that this novel technique allows for a more nuanced and detailed analysis of larger pangenomes.

Microorganisms make up most of the earth’s biomass, and most microbes exist in the form of biofilms, complex communities of microorganisms growing attached to surfaces. Biofilms are directly relevant to a large number of scientific disciplines, and are the subjects of growing multidisciplinary research. As such, there is a pressing requirement for information systems that specialize in biofilm knowledge. Realization of such systems will require a coherent approach to understanding and curating the language used to study biofilms; an ontology of biofilms-related terms offers a foundation for such systems. Here we present an ontology for the study of biofilms (BIFO), a tool that will provide precisely defined terms describing all aspects involved in the biofilms domain. We describe semi-automated methods for the identification of relevant terms from a body of literature, the selection of a set of important terms by domain experts, and the construction of the ontology. A generic approach for BIFO is presented, in which foundational biofilm-related entities and relationships are represented. This ontology reuses terms from other ontologies that provide biofilm knowledge from the Open Biological and Biomedical Ontologies (OBO) foundry.

MOTIVATION: Many important problems in Bioinformatics (e.g. assembly or multiassembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding "safe" partial solutions (e.g. contigs) which are common to all solutions. Previous research on safety has focused on polynomially time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, "minimum flow decomposition" (MFD). We obtain our results by developing a "safety test" for paths based on a general integer linear programming (ILP) formulation. Moreover, we provide implementations with practical optimizations aimed to reduce the total ILP time, the most efficient of these being based on a recursive group-testing procedure. RESULTS: Experimental results on transcriptome datasets show that all safe paths for MFDs correctly recover up to 90% of the full RNA transcripts, which is at least 25% more than previously known safe paths. Moreover, despite the NP-hardness of the problem, we can report all safe paths for 99.8% of the over 27 000 non-trivial graphs of this dataset in only 1.5 h. Our results suggest that, on perfect data, there is less ambiguity than thought in the notoriously hard RNA assembly problem. AVAILABILITY AND IMPLEMENTATION: https://github.com/algbio/mfd-safety.

Flow network decomposition is a natural model for problems where we are given a flow network arising from superimposing a set of weighted paths and would like to recover the underlying data, i.e., decompose the flow into the original paths and their weights. Thus, variations on flow decomposition are often used as subroutines in multiassembly problems such as RNA transcript assembly. In practice, we frequently have access to information beyond flow values in the form of subpaths, and many tools incorporate these heuristically. But despite acknowledging their utility in practice, previous work has not formally addressed the effect of subpath constraints on the accuracy of flow network decomposition approaches. We formalize the flow decomposition with subpath constraints problem, give the first algorithms for it, and study its usefulness for recovering ground truth decompositions. For finding a minimum decomposition, we propose both a heuristic and an FPT algorithm. Experiments on RNA transcript datasets show that for instances with larger solution path sets, the addition of subpath constraints finds 13% more ground truth solutions when minimal decompositions are found exactly, and 30% more ground truth solutions when minimal decompositions are found heuristically.

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation $X$ on a directed graph $G$ into weighted source-to-sink paths whose superposition equals $X$. We show that, for acyclic graphs, considering the \emph{width} of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of \emph{width-stable} graphs, for which a popular heuristic is a \gwsimple-approximation ($|X|$ being the total flow of $X$), and strengthen its worst-case approximation ratio from $Ω(\sqrt{m})$ to $Ω(m / \log m)$ for sparse graphs, where $m$ is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation ($\Vert X \Vert$ being the maximum absolute value of $X$ on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations ($\Vert X \Vert \leq 1$), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ALENEX 2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V, E) is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size k of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose running time is parameterized on k. We obtain two new MPC parameterized algorithms for DAGs running in time O(k2|V| log |V| + |E|) and O(k3|V| + |E|). We also obtain a parallel algorithm running in O(k2|V| + |E|) parallel steps and using O(log |V|) processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we show that we can transform (in O(k2|V|) time) a given MPC into another MPC that uses less than 2|V| distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.

A multi-assembly problem asks to reconstruct multiple genomic sequences from mixed reads sequenced from all of them. Standard formulations of such problems model a solution as a path cover in a directed acyclic graph, namely a set of paths that together cover all vertices of the graph. Since multi-assembly problems admit multiple solutions in practice, we consider an approach commonly used in standard genome assembly: output only partial solutions (contigs, or safe paths), that appear in all path cover solutions. We study constrained path covers, a restriction on the path cover solution that incorporate practical constraints arising in multi-assembly problems. We give efficient algorithms finding all maximal safe paths for constrained path covers. We compute the safe paths of splicing graphs constructed from transcript annotations of different species. Our algorithms run in less than 15 seconds per species and report RNA contigs that are over 99% precise and are up to 8 times longer than unitigs. Moreover, RNA contigs cover over 70% of the transcripts and their coding sequences in most cases. With their increased length to unitigs, high precision, and fast construction time, maximal safe paths can provide a better base set of sequences for transcript assembly programs.

Flow network decomposition is a natural model for problems where we are given a flow network arising from superimposing a set of weighted paths and would like to recover the underlying data, i.e., decompose the flow into the original paths and their weights. Thus, variations on flow decomposition are often used as subroutines in multiassembly problems such as RNA transcript assembly. In practice, we frequently have access to information beyond flow values in the form of subpaths, and many tools incorporate these heuristically. But despite acknowledging their utility in practice, previous work has not formally addressed the effect of subpath constraints on the accuracy of flow network decomposition approaches. We formalize the flow decomposition with subpath constraints problem, give the first algorithms for it, and study its usefulness for recovering ground truth decompositions. For finding a minimum decomposition, we propose both a heuristic and an FPT algorithm. Experiments on RNA transcript datasets show that for instances with larger solution path sets, the addition of subpath constraints finds 13% more ground truth solutions when minimal decompositions are found exactly, and 30% more ground truth solutions when minimal decompositions are found heuristically.

RNA-Seq technology allows for high-throughput, low cost measurement of gene expression. An important step in this process is the assembly of mRNA transcript short reads into full transcripts. The problem can be viewed as a flow decomposition problem in which the objective is to minimize the number of path flows needed to represent a given flow. In this work we relax the edge flow constraints to allow for some uncertainty in their measurement. We formulate this as the Inexact Flow Decomposition problem and propose an algorithmic strategy to solve it. In practice, real biological data has measurement errors and so experimentally-derived edge-weighted splice graphs are often not flows. The proposed method is the first approach to this problem that explicitly controls the error allowed on each edge in these graphs in order to achieve a flow. In an intermediate step, the method solves an exact flow decomposition instance; if a greedy method is used for this step, the overall running time is O(|E|2|V|2+|P|3), where P is the solution found to the flow decomposition instance. Preliminary results on simulated biological data sets show that in many cases the ground truth paths can be recovered at approximately correct abundances, even with noisy input data.

We consider the problem of identifying regions within a pan-genome De Bruijn graph that are traversed by many sequence paths. We define such regions and the subpaths that traverse them as frequented regions (FRs). In this work, we formalize the FR problem and describe an efficient algorithm for finding FRs. Subsequently, we propose some applications of FRs based on machine-learning and pan-genome graph simplification. We demonstrate the effectiveness of these applications using data sets for the organisms Staphylococcus aureus (bacterium) and Saccharomyces cerevisiae (yeast). We corroborate the biological relevance of FRs such as identifying introgressions in yeast that aid in alcohol tolerance, and show that FRs are useful for classification of yeast strains by industrial use and visualizing pan-genomic space.

We propose some novel computational approaches to analyzing historical student transcript data to help improve course sequencing and generate default pathways for students to complete a college degree. Additionally, we examine whether there are “hidden prerequisites” to courses and whether there are courses which, when taken early in a student’s career, may improve their chances of graduation. Our analysis was done on a dataset consisting of all student-course enrollments for a period of 10 years at Montana State University.

In this paper, we study a Virtual Server Provisioning and Selection (VSPS) problem in distributed Data Centers (DCs) with the objective of minimizing the total operational cost while meeting the service response time requirement.We aim to develop general algorithms for the VSPS problem without assuming a particular queueing model for service processing in each DC. First, we present a Mixed Integer Linear Programming (MILP) formulation. Then we present a 3-step optimization framework, under which we develop a polynomial-time ln(N)-approximation algorithm (where N is the number of clients) along with a post-optimization procedure for performance improvement. We also show this problem is NP-hard to approximate and is not possible to obtain a better approximation ratio unless NP has TIME(nO(log log n)) deterministic time algorithms. In addition, we present an effective heuristic algorithm that jointly obtains the VS provisioning and selection solutions. Extensive simulation results are presented to justify effectiveness of the proposed algorithms.

Interactive mobile Internet applications have become increasingly common and necessary to perform everyday tasks such as augmented reality, online gaming, video chat, and cloud-based voice recognition. These applications speed up their communications by connecting users to the closest servers and clustering nearby users together. In replica server selection and client clustering, determination of the closest host quickly and accurately is crucial to interactive application responses and the satisfaction of users' expectations. Researchers commonly use latency as the primary metric of network proximity and have developed various latency approximation tools. However, these tools do not yet offer an attractive balance of measurement accuracy, scalability, and maintainability. In this paper, we propose a new latency estimation system for arbitrary hosts using host-to-CDN latency measurements. Compared to existing latency estimation tools, our technique offers superior coverage of the IP address space and latency estimation accuracy. With improved coverage and accuracy of latency estimation it will become easier to establish low latency connections between hosts in a network, improving the responsiveness of interactive Internet applications.

Uncertainties arise in the actual transmission rates achievable over various channels available on wireless links and in the interference characteristics of those links. In this work, we examine a dynamical learning approach to link scheduling for coping with this uncertainty in multihop cognitive relay networks. We formalize a scheduling with uncertainty problem (SWUP) in which the power received by nodes from a transmitting node may not be known with certainty. The schedule simultaneously should optimize transmissions in the current frame as well as perform measurements to reduce the uncertainty in network parameters. We propose a greedy algorithm to solve the SWUP and demonstrate that it is able to learn network parameters over time in order to improve network efficiency. We also formulate the SWUP as a mixed integer linear program (MILP) in order to assess the optimality of SWUP-Greedy. Extensive numerical simulations demonstrate the effectiveness of our algorithms as compared to non-learning methods.

While extending the lifetime of a wireless sensor network (WSN) with full coverage has been extensively studied, it was found recently that the lifetime of a WSN can be prolonged significantly if partial covers are used instead. In this paper, we formally define the problem of extending the lifetime of a WSN using partial covers. (Throughout this paper, we assume that each point of the given target region is covered at least k times by the input sensors.) We first present a centralized algorithm using an optimal subroutine which computes the densest strip with width 2r, where r is the minimum sensing radius of all sensors. By using a known 1-D algorithm, we can cover the center of the strip with k full covers and the remaining subproblems can be solved recursively to have the eventual k partial covers. We then introduce a distributed algorithm without any assumption on the coordinates and directions of sensors, as long as each sensor knows the presence of other sensors within its sensing region. Finally, we present some experimental results comparing the performance of these algorithms with the previous homological partial cover solution. In all small instances the results generated by our algorithms are significantly better than those generated by the homological method. For two larger instances (a larger domain with n around 1000), the homological method cannot finish while both of our algorithms generate promising results.

Relay Stations (RSs) can be deployed in a wireless network to extend its coverage and improve its capacity. Smart (directional) antennas can enhance the functionalities of RSs by forming the beam only towards intended receiving Subscriber Stations (SSs). In this paper, we study a joint problem of selecting a beam width and direction for the smart antenna at each RS and determining the RS assignment for SSs in each scheduling period. The objective is to maximize a utility function that can lead to a stable and high-throughput system. We define this as the Beam Scheduling and Relay Assignment Problem (BS-RAP). We show that BS-RAP is NP-hard, present a Mixed Integer Linear Programming (MILP) formulation to provide optimal solutions and present two polynomial-time greedy algorithms, one of which is shown to have a constant factor approximation ratio.

In this article, we study distributed relay selection methods assuming a dual-hop Decode-and-Forward (DF) relaying protocol. We assume Uplink (UL) phase in a cellular network where multiple source nodes seek the assistance of candidate relay nodes for message delivery. Due to complexity considerations, we consider that each relay node belongs to the relay set of at most one source node. Through local information exchanges, source nodes and relay nodes can learn the existence of nodes and related Channel State Information (CSI) in their neighborhood. We formalize a relay subset selection problem (RSSP) in which each source node that wishes to transmit determines a ranking of different subsets of relays and the problem is to decide how best to assign relays to source nodes in order to maximize the total transmission capacity of all sources. We first reduce the relay subset selection problem to the well known weighted independent set problem, which is NP-hard. This reduction enables a greedy centralized approximation algorithm. We also present a distributed auctioning algorithm which only requires direct communication between source nodes and those relays that are useful to the source nodes. No communication is required between the relay nodes. Numerical simulations were performed to compare the distributed auction method against the centralized greedy approximation algorithm.

Transparent optical networks must support dynamic traffic demands and end-to-end optical transmission. We present a new physically-aware algorithm based on dynamic programming for routing and wavelength assignment in such networks that considers both linear and nonlinear impairments that accumulated along the transmission path. We show that our algorithm scales well to large networks and typically yields the lowest blocking probability when compared to several existing methods. In addition, it is flexible and can adapt to situations where either linear or nonlinear impairments dominate.

The most straightforward way to reduce network power consumption is to turn off idle links and nodes (switches/routers), which we call the power down approach. In a wired network, especially in a backbone network, many links are actually “bundles” of multiple physical cables and line cards that can be shut down independently. In this paper, we study the following routing problem for green networking in wired networks: Given a set of end-to-end communication sessions, determine how to route data traffic through the network such that total power consumption is minimized by turning off unused cables in bundled links and nodes, subject to the constraint that the traffic demand of each session is satisfied. We present an integer linear programming to provide optimal solutions. We also present two fast and effective heuristic algorithms to solve the problem in polynomial time. It has been shown by simulation results based on the Abilene network and the NSF network that the proposed heuristic algorithms consistently provide close-to-optimal solutions.

Network power consumption can be reduced considerably by adapting link data rates to their offered traffic loads. In this paper, we exploit how to leverage rate adaptation for green networking by studying the following flow allocation problem in wired networks: Given a set of candidate paths for each end-to-end communication session, determine how to allocate flow (data traffic) along these paths such that power consumption is minimized, subject to the constraint that the traffic demand of each session is satisfied. According to recent measurement studies, we consider a discrete step increasing function for link power consumption. We address both the single and multiple communication session cases and formulate them as two optimization problems, namely, the Single-session Flow allocation with Rate Adaptation Problem (SF-RAP), and the Multi-session Flow Allocation with Rate Adaptation Problem (MF-RAP). We first show that both problems are NP-hard and present a Mixed Integer Linear Programming (MILP) formulation for the MF-RAP to provide optimal solutions. Then we present a 2-approximation algorithm for the SF-RAP, and a general flow allocation framework as well as an LP-based heuristic algorithm for the MF-RAP. Simulation results show that the algorithm proposed for the SF-RAP consistently outperforms a shortest path based baseline solution and the algorithms proposed for the MF-RAP provide close-to-optimal solutions.

Relay stations can be deployed between mobile stations and base stations in a single-hop wireless network to extend its coverage and improve its capacity. In this paper, we exploit cooperative diversity, channel diversity and multiuser diversity gains in an OFDMA-based wireless relay network. We study a joint channel and relay assignment problem with the objective of maximizing a well-adopted utility function that can lead to a stable system. This problem turns out to be NP-hard. First, a mixed integer linear programming formulation is presented to provide optimal solutions. We then present three simple greedy algorithms to solve the problem in polynomial time, namely, Greedy-ChannelFirst, Greedy-RelayFirst and Greedy-Joint. We also perform a comprehensive theoretical analysis for the performance of the proposed algorithms. Our analytical results show the Greedy-ChannelFirst algorithm is a constant factor approximation algorithm which always provides a solution whose objective value is guaranteed to be no smaller than the optimal value multiplied by a constant less than 1; however, the other two algorithms do not provide a similar performance guarantee. Extensive simulation results have been presented to show that all three proposed algorithms perform very well on average cases.

Relay Stations (RSs) can be deployed in a wireless network to extend its coverage and improve its capacity. Smart (directional) antennas can enhance the functionalities of RSs by forming one or multiple beams only towards intended receivers. In this paper, we focus on the topology control approach for efficient communications in wireless relay networks with smart antennas. This approach precomputes an antenna pattern for each node such that an efficient network topology can be formed for future communications. The corresponding optimization problem is formally defined as the Beam Selection Problem (BSP). First, we present an Integer Linear Programming (ILP) formulation to provide optimal solutions. Then we present a Linear Programming (LP) rounding-based algorithm for the BSP and show it has a constant factor approximation ratio. We also present a simple and fast greedy algorithm to solve the problem. Extensive simulation results show that the proposed algorithms provide close-to-optimal performance.

Relay stations can be deployed in a wireless network to extend its coverage and improve its capacity. In this paper, we study a scheduling problem in OFDMA-based wireless relay networks with consideration for multi-user diversity, channel diversity and spatial reuse. First, we present a Mixed Integer Linear Programming (MILP) formulation to provide optimum solutions. It has been shown by previous research that performance of a wireless scheduling algorithm is usually related to the interference degree delta, which is the maximum number of links that interfere with a common link but do not interfere with each other. Therefore, we then show that the interference degree delta is at most 4 for any 2-hop relay network and 14 for any general h-hop (h >; 1) relay network. Furthermore, we present a simple greedy algorithm for the scheduling problem and show it has an approximation ratio of 1/(1+δ), which leads to an approximation ratio of 1/5 for the 2-hop case and 1/15} for the general case. In addition, we present three heuristic algorithms, namely, the weighted degree greedy algorithm, the Maximum Weighted Independent Set (MWIS) algorithm and the Linear Programming (LP) rounding algorithm, to solve the scheduling problem. Extensive simulation results have showed that the LP rounding algorithm performs best and always provides close-to-optimum solutions. The performance of the simple greedy algorithm is comparable to that of the other algorithms.

In this paper, we exploit cooperative diversity, channel diversity and multi-user diversity gains in an OFDMA-based wireless relay network by studying a joint channel and relay assignment problem. This problem turns out to be NP-hard. First, a mixed integer linear programming formulation is presented to provide optimal solutions. We then present a constant factor approximation algorithm and two heuristic algorithms to solve this problem in polynomial time. Extensive simulation results have been presented to justify the efficiency of the proposed algorithms.

MIMO links enable concurrent transmissions of multiple independent data streams between a pair of nodes, which can significantly improve network throughput. In this paper, we study the stream control and scheduling problems in multihop wireless networks with MIMO links. We present a constant factor approximation algorithm as well as an efficient heuristic algorithm for stream control. Moreover, we extend the results to incorporate TDMA-based scheduling and present effective heuristic algorithms to solve the joint Stream Control and Scheduling Problem (SCSP), whose efficiency is justified by simulation results.

Nodes in a cognitive radio mesh network may select from a set of available channels to use provided they do not interfere with primary users. This ability can improve overall network performance but introduces the question of how best to use these channels. This paper addresses the following specific problem: given a routing path P, choose which channels each link in P should use and their transmission schedule so as to maximize the end-to-end data flow rate (throughput) supported by the entire path. This problem is relevant to applications such as streaming video or data where a connection may be long lasting and require a high constant throughput. The problem is hard to due the presence of both intraflow and inter-flow interference. We have developed a new constant-factor approximation algorithm for this problem. If certain natural conditions on the path are met, the performance guarantee is ¼ of optimal. It has been shown by simulation results that the end-to-end throughput given by the proposed algorithm is often within 90% or better of optimal.

MIMO links can significantly improve network throughput by supporting multiple concurrent data streams between a pair of nodes and suppressing wireless interference. In this paper, we formally define a new cross-layer optimization problem for MIMO-based multihop wireless networks, which is referred to as the joint stream control and scheduling problem (SCSP). We first present a constant factor approximation algorithm to solve the SCSP. In addition, we present a heuristic algorithm to improve the performance further, which is shown to be efficient in practice by our numerical results.

A recent idea for determining the three-dimensional structure of a protein uses antibody recognition of surface structure and random peptide libraries to map antibody epitope combining sites. Antibodies that bind to the surface of the protein of interest can be used as witnesses to report the structure of the protein as follows: Proteins are composed of linear polypeptide chains that come together in complex spatial folding patterns to create the native protein structures and these folded structures form the binding sites for the antibodies. Short amino acid probe sequences, which bind to the active region of each antibody, can be selected from random sequence peptide libraries. These probe sequences can often be aligned to discontinuous regions of the one-dimensional target sequence of a protein. Such alignments indicate how pieces of the protein sequence must be folded together in space and thus provide valuable long-range constraints for solving the overall 3-D structure. This new approach is applicable to the very large number of proteins that are refractory to current approaches to structure determination and has the advantage of requiring very small amounts of the target protein. The binding site of an antibody is a surface, not just a linear sequence, so the epitope mapping alignment problem is outside the scope of classical string alignment algorithms, such as Smith-Waterman. We formalize the alignment problem that is at the heart of this new approach, prove that the epitope mapping alignment problem is NP-complete, and give some initial results using a branch-and-bound algorithm to map two real-life cases.

This paper studies the long-standing open question of whether optimal alphabetic binary trees can be constructed in $o( n\lg n )$ time. We show that a class of techniques for finding optimal alphabetic trees which includes all current methods yielding $O( n\lg n )$-time algorithms are at least as hard as sorting in whatever model of computation is used. We also give $O( n )$-time algorithms for the case where all the input weights are within a constant factor of one another and when they are exponentially separated.