Abstract Motivation: Prokaryotic organisms have been identified utilizing the sequence variation of the 16S rRNA gene. Variations steer the design of DNA probes for the detection of taxonomic groups or specific organisms. The long-term goal of our project is to create probe arrays capable of identifying 16S rDNA sequences in unknown samples. This necessitated the authentication, categorization and alignment of the >75 000 publicly available‘ 16S’ sequences. Preferably, the entire process should be computationally administrated so the aligned collection could periodically absorb 16S rDNA sequences from the public records. A complete multiple sequence alignment would provide a foundation for computational probe selection and facilitates microbial taxonomy and phylogeny. Results: Here we report the alignment and similarity clustering of 62 662 16S rDNA sequences and an approach for designing effective probes for each cluster. A novel alignment compression algorithm, NAST (Nearest Alignment Space Termination), was designed to produce the uniform multiple sequence alignment referred to as the prokMSA. From the prokMSA, 9020 Operational Taxonomic Units (OTUs) were found based on transitive sequence similarities. An automated approach to probe design was straightforward using the prokMSA clustered into OTUs. As a test case, multiple probes were computationally picked for each of the 27 OTUs that were identified within the Staphylococcus Group. The probes were incorporated into a customized microarray and were able to correctly categorize Staphylococcus aureus and Bacillus anthracis into their correct OTUs. Although a successful probe picking strategy is outlined, the main focus of creating the prokMSA was to provide a comprehensive, categorized, updateable 16S rDNA collection useful as a foundation for any probe selection algorithm. Availability: http://greengenes.llnl.gov/16S/ Contact: [email protected] Supplementary Information: Complete prokMSA in aligned fasta format: http://greengenes.llnl.gov/16S_cgi/download/update_28Dec02/prokMSA_aligned.fasta.Z Sequences within each Operational Taxonomic Unit: http://greengenes.llnl.gov/16S_cgi/download/update_15Mar02/SeqDescByOTU.txt DNA probe sequences: http://greengenes.llnl.gov/16S_cgi/download/update_15Mar02/15Mar02_StaphGrpPrbs.xls * To whom correspondence should be addressed.

This paper focuses on the Teledesic satellite constellation, which is an attempt to provide high speed, multimedia networking connectivity to any location on the globe. Since the routers (satellites) are in constant motion, this venture is unique and leads to a one-of-a-kind data routing scheme. This concept is still in the design phase, with implementation still a few years away. However, several large companies and capital investors have already committed funds to this venture. Supporters are claiming a full operational capability in roughly 3 years. Our focus in this paper is to develop a routing algorithm for the Teledesic satellite constellation. The algorithm is conceptually developed and implemented using a software simulation. Our results, which indicate this algorithm is a viable solution to the routing problem, and our implementation details are presented below.