Search

Efficient translation mediated by the 5′ untranslated region (5′ UTR) is essential for the robust efficacy of mRNA vaccines. However, the N1-methyl-pseudouridine (m1Ψ) modification of mRNA can impact the translation efficiency of the 5′ UTR. We discovered that the optimal 5′ UTR for m1Ψ-modified mRNA (m1Ψ–5′ UTR) differs significantly from its unmodified counterpart, highlighting the need for a specialized tool for designing m1Ψ–5′ UTRs rather than directly utilizing high-expression endogenous gene 5′ UTRs. In response, we developed a novel machine learning-based tool, Smart5UTR, which employs a deep generative model to identify superior m1Ψ–5′ UTRs in silico. The tailored loss function and network architecture enable Smart5UTR to overcome limitations inherent in existing models. As a result, Smart5UTR can successfully design superior 5′ UTRs, greatly benefiting mRNA vaccine development. Notably, Smart5UTR-designed superior 5′ UTRs significantly enhanced antibody titers induced by COVID-19 mRNA vaccines against the Delta and Omicron variants of SARS-CoV-2, surpassing the performance of vaccines using high-expression endogenous gene 5′ UTRs.

Abstract There is a deficiency in population-based studies investigating the impact of HPV infection on vaginal microenvironment, which influences the risk of persistent HPV infection. This prospective study aimed to unravel the dynamics of vaginal microbiota (VM) and vaginal metabolome in reaction to the changed state of HPV infection. Our results propose that the vaginal metabolome may be a superior indicator to VM when assessing the impact of altered HPV state on the vaginal microenvironment.

Numerous studies have shown that immune checkpoint inhibitor (ICI) immunotherapy has great potential as a cancer treatment, leading to significant clinical improvements in numerous cases. However, it benefits a minority of patients, underscoring the importance of discovering reliable biomarkers that can be used to screen for potential beneficiaries and ultimately reduce the risk of overtreatment. Our comprehensive review focuses on the latest advancements in predictive biomarkers for ICI therapy, particularly emphasizing those that enhance the efficacy of programmed cell death protein 1 (PD-1)/programmed cell death-ligand 1 (PD-L1) inhibitors and cytotoxic T-lymphocyte antigen-4 (CTLA-4) inhibitors immunotherapies. We explore biomarkers derived from various sources, including tumor cells, the tumor immune microenvironment (TIME), body fluids, gut microbes, and metabolites. Among them, tumor cells-derived biomarkers include tumor mutational burden (TMB) biomarker, tumor neoantigen burden (TNB) biomarker, microsatellite instability (MSI) biomarker, PD-L1 expression biomarker, mutated gene biomarkers in pathways, and epigenetic biomarkers. TIME-derived biomarkers include immune landscape of TIME biomarkers, inhibitory checkpoints biomarkers, and immune repertoire biomarkers. We also discuss various techniques used to detect and assess these biomarkers, detailing their respective datasets, strengths, weaknesses, and evaluative metrics. Furthermore, we present a comprehensive review of computer models for predicting the response to ICI therapy. The computer models include knowledge-based mechanistic models and data-based machine learning (ML) models. Among the knowledge-based mechanistic models are pharmacokinetic/pharmacodynamic (PK/PD) models, partial differential equation (PDE) models, signal networks-based models, quantitative systems pharmacology (QSP) models, and agent-based models (ABMs). ML models include linear regression models, logistic regression models, support vector machine (SVM)/random forest/extra trees/k-nearest neighbors (KNN) models, artificial neural network (ANN) and deep learning models. Additionally, there are hybrid models of systems biology and ML. We summarized the details of these models, outlining the datasets they utilize, their evaluation methods/metrics, and their respective strengths and limitations. By summarizing the major advances in the research on predictive biomarkers and computer models for the therapeutic effect and clinical utility of tumor ICI, we aim to assist researchers in choosing appropriate biomarkers or computer models for research exploration and help clinicians conduct precision medicine by selecting the best biomarkers.

Abstract Breakage-fusion-bridge (BFB) is a complex rearrangement that leads to tumor malignancy. Existing models for detecting BFBs rely on the ideal BFB hypothesis, ruling out the possibility of BFBs entangled with other structural variations, that is, complex BFBs. We propose an algorithm Ambigram to identify complex BFB and reconstruct the rearranged structure of the local genome during the cancer subclone evolution process. Ambigram handles data from short, linked, long, and single-cell sequences, and optical mapping technologies. Ambigram successfully deciphers the gold- or silver-standard complex BFBs against the state-of-the-art in multiple cancers. Ambigram dissects the intratumor heterogeneity of complex BFB events with single-cell reads from melanoma and gastric cancer. Furthermore, applying Ambigram to liver and cervical cancer data suggests that the BFB mechanism may mediate oncovirus integrations. BFB also exists in noncancer genomics. Investigating the complete human genome reference with Ambigram suggests that the BFB mechanism may be involved in two genome reorganizations of Homo Sapiens during evolution. Moreover, Ambigram discovers the signals of recurrent foldback inversions and complex BFBs in whole genome data from the 1000 genome project, and congenital heart diseases, respectively.

Given the shortage of cytologists, women in low-resource regions had inequitable access to cervical cytology which plays an pivotal role in cervical cancer screening. Emerging studies indicated the potential of AI-assisted system in promoting the implementation of cytology in resource-limited settings. However, there is a deficiency in evaluating the aid of AI in the improvement of cytologists’ work efficiency. This study aimed to evaluate the feasibility of AI in excluding cytology-negative slides and improve the efficiency of slide interpretation. Well-annotated slides were included to develop the classification model that was applied to classify slides in the validation group. Nearly 70% of validation slides were reported as negative by the AI system, and none of these slides were diagnosed as high-grade lesions by expert cytologists. With the aid of AI system, the average of interpretation time for each slide decreased from 3 minutes to 30 seconds. These findings suggested the potential of AI-assisted system in accelerating slide interpretation in the large-scale cervical cancer screening.

Summary: We describe a protocol to integrate genome variation data from different datasets and explore the population structure and migration history of human populations. This protocol provides semi-automated scripts to perform and visualize the effect of variant filtering strategy on eliminating batch effects, principal component analysis, ancestry component analysis, historical population effective size inference, and migration and isolation analysis based on independent biallelic SNPs, genotype likelihoods, and haplotypes. The protocol can be adapted to variation data from other sources.For complete details on the use and execution of this protocol, please refer to Zhang et al. (2022).1 : Publisher’s note: Undertaking any experimental protocol requires adherence to local institutional guidelines for laboratory safety and ethics.

SARS-CoV-2 is a single-stranded RNA betacoronavirus with a high mutation rate. The rapidly emerging SARS-CoV-2 variants could increase transmissibility and diminish vaccine protection. However, whether coinfection with multiple SARS-CoV-2 variants exists remains controversial. This study collected 12,986 and 4,113 SARS-CoV-2 genomes from the GISAID database on May 11, 2020 (GISAID20May11), and Apr 1, 2021 (GISAID21Apr1), respectively. With single-nucleotide variant (SNV) and network clique analyses, we constructed single-nucleotide polymorphism (SNP) coexistence networks and discovered maximal SNP cliques of sizes 16 and 34 in the GISAID20May11 and GISAID21Apr1 datasets, respectively. Simulating the transmission routes and SNV accumulations, we discovered a linear relationship between the size of the maximal clique and the number of coinfected variants. We deduced that the COVID-19 cases in GISAID20May11 and GISAID21Apr1 were coinfections with 3.20 and 3.42 variants on average, respectively. Additionally, we performed Nanopore sequencing on 42 COVID-19 patients and discovered recurrent heterozygous SNPs in twenty of the patients, including loci 8,782 and 28,144, which were crucial for SARS-CoV-2 lineage divergence. In conclusion, our findings reported SARS-CoV-2 variants coinfection in COVID-19 patients and demonstrated the increasing number of coinfected variants.

Abstract Background Copy number variation is crucial in deciphering the mechanism and cure of complex disorders and cancers. The recent advancement of scDNA sequencing technology sheds light upon addressing intratumor heterogeneity, detecting rare subclones, and reconstructing tumor evolution lineages at single-cell resolution. Nevertheless, the current circular binary segmentation based approach proves to fail to efficiently and effectively identify copy number shifts on some exceptional trails. Results Here, we propose SCYN, a CNV segmentation method powered with dynamic programming. SCYN resolves the precise segmentation on in silico dataset. Then we verified SCYN manifested accurate copy number inferring on triple negative breast cancer scDNA data, with array comparative genomic hybridization results of purified bulk samples as ground truth validation. We tested SCYN on two datasets of the newly emerged 10x Genomics CNV solution. SCYN successfully recognizes gastric cancer cells from 1% and 10% spike-ins 10x datasets. Moreover, SCYN is about 150 times faster than state of the art tool when dealing with the datasets of approximately 2000 cells. Conclusions SCYN robustly and efficiently detects segmentations and infers copy number profiles on single cell DNA sequencing data. It serves to reveal the tumor intra-heterogeneity. The source code of SCYN can be accessed in https://github.com/xikanfeng2/SCYN .

Abstract Topologically associating domains (TADs) are the organizational units of chromosome structures. TADs can contain TADs, thus forming a hierarchy. TAD hierarchies can be inferred from Hi-C data through coding trees. However, the current method for computing coding trees is not optimal. In this paper, we propose optimal algorithms for this computation. In comparison with seven state-of-art methods using two public datasets, from GM12878 and IMR90 cells, SuperTAD shows a significant enrichment of structural proteins around detected boundaries and histone modifications within TADs and displays a high consistency between various resolutions of identical Hi-C matrices.

Abstract Background Horizontal Gene Transfer (HGT) refers to the sharing of genetic materials between distant species that are not in a parent-offspring relationship. The HGT insertion sites are important to understand the HGT mechanisms. Recent studies in main agents of HGT, such as transposon and plasmid, demonstrate that insertion sites usually hold specific sequence features. This motivates us to find a method to infer HGT insertion sites according to sequence features. Results In this paper, we propose a deep residual network, DeepHGT, to recognize HGT insertion sites. To train DeepHGT, we extracted about 1.55 million sequence segments as training instances from 262 metagenomic samples, where the ratio between positive instances and negative instances is about 1:1. These segments are randomly partitioned into three subsets: 80% of them as the training set, 10% as the validation set, and the remaining 10% as the test set. The training loss of DeepHGT is 0.4163 and the validation loss is 0.423. On the test set, DeepHGT has achieved the area under curve (AUC) value of 0.8782. Furthermore, in order to further evaluate the generalization of DeepHGT, we constructed an independent test set containing 689,312 sequence segments from another 147 gut metagenomic samples. DeepHGT has achieved the AUC value of 0.8428, which approaches the previous test AUC value. As a comparison, the gradient boosting classifier model implemented in PyFeat achieve an AUC value of 0.694 and 0.686 on the above two test sets, respectively. Furthermore, DeepHGT could learn discriminant sequence features; for example, DeepHGT has learned a sequence pattern of palindromic subsequences as a significantly (P-value=0.0182) local feature. Hence, DeepHGT is a reliable model to recognize the HGT insertion site. Conclusion DeepHGT is the first deep learning model that can accurately recognize HGT insertion sites on genomes according to the sequence pattern.

Abstract Background The human microbiota are complex systems with important roles in our physiological activities and diseases. Sequencing the microbial genomes in the microbiota can help in our interpretation of their activities. The vast majority of the microbes in the microbiota cannot be isolated for individual sequencing. Current metagenomics practices use short-read sequencing to simultaneously sequence a mixture of microbial genomes. However, these results are in ambiguity during genome assembly, leading to unsatisfactory microbial genome completeness and contig continuity. Linked-read sequencing is able to remove some of these ambiguities by attaching the same barcode to the reads from a long DNA fragment (10–100 kb), thus improving metagenome assembly. However, it is not clear how the choices for several parameters in the use of linked-read sequencing affect the assembly quality. Results We first examined the effects of read depth (C) on metagenome assembly from linked-reads in simulated data and a mock community. The results showed that C positively correlated with the length of assembled sequences but had little effect on their qualities. The latter observation was corroborated by tests using real data from the human gut microbiome, where C demonstrated minor impact on the sequence quality as well as on the proportion of bins annotated as draft genomes. On the other hand, metagenome assembly quality was susceptible to read depth per fragment (C R ) and DNA fragment physical depth (C F ). For the same C, deeper C R resulted in more draft genomes while deeper C F improved the quality of the draft genomes. We also found that average fragment length (μ FL ) had marginal effect on assemblies, while fragments per partition (N F/P ) impacted the off-target reads involved in local assembly, namely, lower N F/P values would lead to better assemblies by reducing the ambiguities of the off-target reads. In general, the use of linked-reads improved the assembly for contig N50 when compared to Illumina short-reads, but not when compared to PacBio CCS (circular consensus sequencing) long-reads. Conclusions We investigated the influence of linked-read sequencing parameters on metagenome assembly comprehensively. While the quality of genome assembly from linked-reads cannot rival that from PacBio CCS long-reads, the case for using linked-read sequencing remains persuasive due to its low cost and high base-quality. Our study revealed that the probable best practice in using linked-reads for metagenome assembly was to merge the linked-reads from multiple libraries, where each had sufficient C R but a smaller amount of input DNA. Video Abstract

Abstract Background Single-cell RNA-sequencing (scRNA-seq) is becoming indispensable in the study of cell-specific transcriptomes. However, in scRNA-seq techniques, only a small fraction of the genes are captured due to “dropout” events. These dropout events require intensive treatment when analyzing scRNA-seq data. For example, imputation tools have been proposed to estimate dropout events and de-noise data. The performance of these imputation tools are often evaluated, or fine-tuned, using various clustering criteria based on ground-truth cell subgroup labels. This limits their effectiveness in the cases where we lack cell subgroup knowledge. We consider an alternative strategy which requires the imputation to follow a “self-consistency” principle; that is, the imputation process is to refine its results until there is no internal inconsistency or dropouts from the data. Results We propose the use of “self-consistency” as a main criteria in performing imputation. To demonstrate this principle we devised I-Impute, a “self-consistent” method, to impute scRNA-seq data. I-Impute optimizes continuous similarities and dropout probabilities, in iterative refinements until a self-consistent imputation is reached. On the in silico data sets, I-Impute exhibited the highest Pearson correlations for different dropout rates consistently compared with the state-of-art methods SAVER and scImpute. Furthermore, we collected three wetlab datasets, mouse bladder cells dataset, embryonic stem cells dataset, and aortic leukocyte cells dataset, to evaluate the tools. I-Impute exhibited feasible cell subpopulation discovery efficacy on all the three datasets. It achieves the highest clustering accuracy compared with SAVER and scImpute. Conclusions A strategy based on “self-consistency”, captured through our method, I-Impute, gave imputation results better than the state-of-the-art tools. Source code of I-Impute can be accessed at https://github.com/xikanfeng2/I-Impute .

Travel entail change in geography and diet, both of which are known as determinant factors in shaping the human gut microbiome. Additionally, altered gut microbiome modulates immunity, bringing about health implications in humans. To explore the effects of the mid-term travel on the gut microbiome, we generated 16S rRNA gene and metagenomic sequencing data from longitudinal samples collected over six months. We monitored dynamic trajectories of the gut microbiome variation of a Chinese volunteer team (VT) in their whole journey to Trinidad and Tobago (TAT). We found gut microbiome resilience that VT’s gut microbial compositions gradually transformed to the local TAT’s enterotypes during their six-month stay in TAT, and then reverted to their original enterotypes after VT’s return to Beijing in one month. Moreover, we identified driven species in this bi-directional plasticity that could play a role in immunity modulation, as exemplified by Bacteroides dorei that attenuated atherosclerotic lesion formation and effectively suppressed proinflammatory immune response. Another driven species P. copri could play a crucial role in rheumatoid arthritis pathogenesis, a chronic autoimmune disease. Carbohydrate-active enzymes are often implicated in immune and host-pathogen interactions, of which glycoside hydrolases were found decreased but glycosyltransferases and carbohydrate esterases increased during the travel; these functions were then restored after VT’ returning to Beijing. Furthermore, we discovered these microbial changes and restoration were mediated by VT people’s dietary changes. These findings indicate that half-year travel leads to change in enterotype and functional patterns, exerting effects on human health. Microbial intervention by dietary guidance in half-year travel would be conducive to immunity modulation for maintaining health.

Abstract Background Horizontal Gene Transfer (HGT) is the process of transferring genetic materials between species. Through sharing genetic materials, microorganisms in the human microbiota form a network. The network can provide insights into understanding the microbiota. Here, we constructed the HGT networks from the gut microbiota sequencing data and performed network analysis to characterize the HGT networks of gut microbiota. Results We constructed the HGT network and perform the network analysis to two typical gut microbiota datasets, a 283-sample dataset of Mother-to-Child and a 148-sample dataset of longitudinal inflammatory bowel disease (IBD) metagenome. The results indicated that (1) the HGT networks are scale-free. (2) The networks expand their complexities, sizes, and edge numbers, accompanying the early stage of lives; and microbiota established in children shared high similarity as their mother (p-value = 0.0138), supporting the transmission of microbiota from mother to child. (3) Groups harbor group-specific network edges, and network communities, which can potentially serve as biomarkers. For instances, IBD patient group harbors highly abundant communities of Proteobacteria (p-value = 0.0194) and Actinobacteria (p-value = 0.0316); children host highly abundant communities of Proteobacteria (p-value = 2.8785 $$e^{-5}$$ e - 5 ) and Actinobacteria (p-value = 0.0015), and the mothers host highly abundant communities of Firmicutes (p-value = 8.0091 $$e^{-7}$$ e - 7 ). IBD patient networks contain more HGT edges in pathogenic genus, including Mycobacterium, Sutterella, and Pseudomonas. Children’s networks contain more edges from Bifidobacterium and Escherichia. Conclusion Hence, we proposed the HGT network constructions from the gut microbiota sequencing data. The HGT networks capture the host state and the response of microbiota to the environmental and host changes, and they are essential to understand the human microbiota.

Periodontitis and peri-implantitis are common biofilm-mediated infectious diseases affecting teeth and dental implants and have been considered to be initiated with microbial dysbiosis. To further understand the essence of oral microbiome dysbiosis in terms of bacterial interactions, community structure, and microbial stability, we analyzed 64 plaque samples from 34 participants with teeth or implants under different health conditions using metagenomic sequencing. After taxonomical annotation, we computed the inter-species correlations, analyzed the bacterial community structure, and calculated the microbial stability in supra- and subgingival plaques from hosts with different health conditions. The results showed that when inflammation arose, the subgingival communities became less connective and competitive with fewer hub species. In contrast, the supragingival communities tended to be more connective and competitive with an increased number of hub species. Besides, periodontitis and peri-implantitis were associated with significantly increased microbial stability in subgingival microbiome. These findings indicated that the periodontal and peri-implant dysbiosis is associated with aberrant alterations in the bacterial correlations, community structures, and local stability. The highly connected hub species, as well as the major contributing species of negative correlations, should also be given more concern in future studies.

Abstract Background With recent advances in high-throughput technologies, matrix factorization techniques are increasingly being utilized for mapping quantitative omics profiling matrix data into low-dimensional embedding space, in the hope of uncovering insights in the underlying biological processes. Nevertheless, current matrix factorization tools fall short in handling noisy data and missing entries, both deficiencies that are often found in real-life data. Results Here, we propose DeepMF, a deep neural network-based factorization model. DeepMF disentangles the association between molecular feature-associated and sample-associated latent matrices, and is tolerant to noisy and missing values. It exhibited feasible cancer subtype discovery efficacy on mRNA, miRNA, and protein profiles of medulloblastoma cancer, leukemia cancer, breast cancer, and small-blue-round-cell cancer, achieving the highest clustering accuracy of 76%, 100%, 92%, and 100% respectively. When analyzing data sets with 70% missing entries, DeepMF gave the best recovery capacity with silhouette values of 0.47, 0.6, 0.28, and 0.44, outperforming other state-of-the-art MF tools on the cancer data sets Medulloblastoma, Leukemia, TCGA BRCA, and SRBCT. Its embedding strength as measured by clustering accuracy is 88%, 100%, 84%, and 96% on these data sets, which improves on the current best methods 76%, 100%, 78%, and 87%. Conclusion DeepMF demonstrated robust denoising, imputation, and embedding ability. It offers insights to uncover the underlying biological processes such as cancer subtype discovery. Our implementation of DeepMF can be found at https://github.com/paprikachan/DeepMF.

Abstract Background Adenosine-to-inosine RNA editing can markedly diversify the transcriptome, leading to a variety of critical molecular and biological processes in mammals. Over the past several years, researchers have developed several new pipelines and software packages to identify RNA editing sites with a focus on downstream statistical analysis and functional interpretation. Results Here, we developed a user-friendly public webserver named MIRIA that integrates statistics and visualization techniques to facilitate the comprehensive analysis of RNA editing sites data identified by the pipelines and software packages. MIRIA is unique in that provides several analytical functions, including RNA editing type statistics, genomic feature annotations, editing level statistics, genome-wide distribution of RNA editing sites, tissue-specific analysis and conservation analysis. We collected high-throughput RNA sequencing (RNA-seq) data from eight tissues across seven species as the experimental data for MIRIA and constructed an example result page. Conclusion MIRIA provides both visualization and analysis of mammal RNA editing data for experimental biologists who are interested in revealing the functions of RNA editing sites. MIRIA is freely available at https://mammal.deepomics.org.

Summary: Every human somatic cell inherits a maternal and a paternal genome, which work together to give rise to cellular phenotypes. However, the allele-specific relationship between gene expression and genome structure through the cell cycle is largely unknown. By integrating haplotype-resolved genome-wide chromosome conformation capture, mature and nascent mRNA, and protein binding data from a B lymphoblastoid cell line, we investigate this relationship both globally and locally. We introduce the maternal and paternal 4D Nucleome, enabling detailed analysis of the mechanisms and dynamics of genome structure and gene function for diploid organisms. Our analyses find significant coordination between allelic expression biases and local genome conformation, and notably absent expression bias in universally essential cell cycle and glycolysis genes. We propose a model in which coordinated biallelic expression reflects prioritized preservation of essential gene sets.

Treatment of ovarian cancer (OC) remains the biggest challenge among gynecological malignancies. Immune checkpoint blockade therapy is promising in many cancers but shows low response rates in OC because of its heterogeneity. Although the biological and molecular heterogeneity of OC has been extensively investigated, heterogeneity of immune microenvironment remains elusive. We have collected the expression profiles of 3071 OC patients from 22 publicly available datasets. CIBERSORT was applied to infer the infiltration fraction of 22 immune cells among 2086 patients with CIBERSORT P

Single-cell RNA-seq studies profile thousands of cells in developmental processes. Current databases for human single-cell expression atlas only provide search and visualize functions for a selected gene in specific cell types or subpopulations. These databases are limited to technical properties or visualization of single-cell RNA-seq data without considering the biological relations of their collected cell groups. Here, we developed a database to investigate single-cell gene expression profiling during different developmental pathways (SCDevDB). In this database, we collected 10 human single-cell RNA-seq datasets, split these datasets into 176 developmental cell groups, and constructed 24 different developmental pathways. SCDevDB allows users to search the expression profiles of the interested genes across different developmental pathways. It also provides lists of differentially expressed genes during each developmental pathway, T-distributed stochastic neighbor embedding maps showing the relationships between developmental stages based on these differentially expressed genes, Gene Ontology, and Kyoto Encyclopedia of Genes and Genomes analysis results of these differentially expressed genes. This database is freely available at https://scdevdb.deepomics.org

Community-acquired pneumonia (CAP) is a worldwide infectious disease caused by bacteria, viruses, or a combination of these infectious agents. Mycoplasma pneumoniae is an atypical pneumonia pathogen that causes high morbidity and mortality in children, and adenovirus can lead to severe pneumonia. However, the etiology of different types of pneumonia is still unclear. In this study, we selected a total of 52 inpatients with M. pneumoniae pneumonia (MPP) (n = 21), adenovirus pneumonia (AVP) (n = 16), or tracheomalacia (n = 15) to serve as a disease control. Bronchoalveolar lavage fluid (BALF) samples that had been obtained for clinical use were analyzed. We compared the differences in microbiota and the expression of 10 inflammatory cytokines in samples between MPP, AVP, and tracheomalacia. We found that the bacterial diversity in MPP was lower than that in AVP and tracheomalacia. Mycoplasma, Streptococcus, and Pseudomonas were predominant in samples of MPP, AVP, and tracheomalacia, respectively. The expression levels of IL-6, IL-8, and IL-10 were significantly higher in inpatients with AVP compared to children hospitalized with tracheomalacia or MPP. The lung microbiota in MPP was remarkably correlated with IL-2, IL-4, IL-5, IL-6, TNF-α, and IL-1α expressions, while this was not found in tracheomalacia and AVP. Microbiota analysis identified a high load of multi-drug resistant Acinetobacter baumannii in the lung microbiota of several inpatients, which might be associated with the long hospitalization length and intra-group differences at the individual level. This study will help to understand the microbial etiology of tracheomalacia, AVP, and MPP and to identify effective therapies for these diseases.

In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of l points in a 3D space, where l is a fixed natural number. Two structural fragments f1 and f2 are equivalent if and only if f1 = f2 x R + Ä under some rotation R and translation Ä . We consider the distance between two structural fragments to be the sum of the squared Euclidean distance between all corresponding points of the structural fragments. Given a set of n structural fragments, we consider the problem of finding k (or fewer) structural fragments g1, g2, ... , gk, so as to minimize the sum of the distances between each of f1, f2, ... , fn to its nearest structural fragment in g1, ... , gk. In this paper we show a polynomial-time approximation scheme (PTAS) for the problem through a simple sampling strategy.