The Herpes Simplex Virus Type 1 Cleavage/Packaging Protein,UL32, Is Involved in Efficient Localization of Capsids to Replication Compartments

Six genes, including UL32, have been implicated in the cleavage and packaging of herpesvirus DNA into preassembled capsids. We have isolated a UL32 insertion mutant which is capable of near-wild-type levels of viral DNA synthesis; however, the mutant virus is unable to cleave and package viral DNA, consistent with the phenotype of a previously isolated temperature-sensitive herpes simplex virus type 1 mutant, tsN20 (P. A. Schaffer, G. M. Aron, N. Biswal, and M. Benyesh-Melnick, Virology 52:57–71, 1973). A polyclonal antibody which recognizes UL32 was previously used by Chang et al. (Y. E. Chang, A. P. Poon, and B. Roizman, J. Virol. 70:3938–3946, 1996) to demonstrate that UL32 accumulates predominantly in the cytoplasm of infected cells. In this report, a functional epitope-tagged version of UL32 showed that while UL32 is predominantly cytoplasmic, some nuclear staining which colocalizes with the major DNA binding protein (ICP8, UL29) in replication compartments can be detected. We have also used a monoclonal antibody (5C) specific for the hexon form of major capsid protein VP5 to study the distribution of capsids during infection. In cells infected with wild-type KOS (6 and 8 h postinfection), 5C staining patterns indicate that capsids are present in nuclei within replication compartments. These results suggest that cleavage and packaging occur in replication compartments at least at 6 and 8 h postinfection. Cells infected with the UL32 mutant exhibit a hexon staining pattern which is more diffusely distributed throughout the nucleus and which is not restricted to replication compartments. We propose that UL32 may play a role in “bringing” preassembled capsids to the sites of DNA packaging and that the failure to localize to replication compartments may explain the cleavage/packaging defect exhibited by this mutant. These results suggest that the UL32 protein is required at a step distinct from those at which other cleavage and packaging proteins are required and may be involved in the correct localization of capsids within infected cells.During infection of cells with herpes simplex virus type 1 (HSV-1), the large concatemeric products of DNA replication are cleaved to unit length and packaged into preassembled capsids. Capsids are icosahedral structures composed of 150 hexons and 12 pentons. Three types of capsids (A, B, and C) can be isolated from infected cells by velocity centrifugation (20). C capsids contain the viral DNA genome; B capsids contain the scaffolding protein; and A capsids contain neither DNA nor the scaffolding protein. Pulse chase experiments with another alphaherpesvirus, equine herpesvirus 1, indicate that at least some B capsids can package DNA and mature into infectious virions, while A capsids cannot (46). By analogy with the bacteriophages, these results suggest that B capsids represent procapsids which are intermediates in the packaging process. However, a new intermediate in the assembly process has recently been identified (41, 62). These newly identified capsid forms observed in in vitro assembly extracts have the same protein content as B capsids but are more spherical; these capsids are unstable and adopt the more angular form characteristic of B capsids after prolonged incubation in vitro. These results suggest that the unstable spherical forms may represent the true procapsid intermediate (41, 62).In many bacteriophages, the procapsid contains at least three essential components: an icosahedrally arranged protein shell, an internal scaffold, and a dodecameric ring called the portal vertex through or around which the phage DNA is taken up (8, 11, 18). For HSV-1, the outer shell is composed of four proteins: the major capsid protein, VP5; a small protein bound to hexons, VP26; and a triplex structure made up of heterotrimers of VP19C and VP23 (reviewed in reference 56). VP24, VP21, and VP22a are found in the interior of the capsid and are encoded by overlapping genes UL26 and UL26.5; VP21 and VP22a are present in B but not A or C capsids and are considered to make up the internal scaffold (reviewed in reference 56). Although bacteriophages contain a portal vertex, no such structure has been observed in HSV-1 capsids. Whether the herpesviruses have a unique portal vertex through which viral DNA is taken up is unclear; it is possible that this type of unique vertex is only needed in viruses which have a tail. Capsids indistinguishable from those isolated from HSV-1-infected cells have been observed in extracts from insect cells infected with recombinant baculoviruses bearing HSV-1 capsid genes (42, 60). Therefore, it is clear that these proteins are sufficient for capsid assembly in vitro; however, it is not known whether capsids formed in vitro are competent for DNA uptake. It is possible that minor components of capsids play important roles in genome encapsidation.In addition to the capsid proteins, at least six genes are essential for the encapsidation of viral DNA: the UL6, UL15, UL25, UL28, UL32, and UL33 genes. Temperature-sensitive (ts) strains with mutations in these genes have similar phenotypes, in that viral DNA can be replicated but not cleaved and packaged (1, 2, 4, 6, 48, 51, 54, 55, 66). Strains with null mutations in the UL6, UL15, UL25, UL28, and UL33 genes have been isolated and characterized, thereby confirming the roles of these genes in cleavage and packaging (5, 27, 37, 45, 59, 68). Despite the identification of these required genes, the mechanism by which viral DNA is cleaved and packaged is not understood, nor has the role of any of the gene products been determined. The UL6 and UL25 proteins have been detected in A, B, and C capsids as well as in virions (3, 28, 37, 44); however, the precise role of these two proteins in capsids remains to be determined.A ts UL32 mutant, tsN20, defective in cleavage and packaging, has been reported previously (51). Because mutants with lesions resulting in temperature sensitivity are often prone to problems associated with incomplete penetrance at the nonpermissive temperature, we isolated a UL32 insertion mutant, hr64. Characterization of hr64 confirms that UL32 is essential for cleavage and packaging. Previous studies demonstrated that UL32 localizes to the cytoplasm of infected cells (13). We have used a functional epitope-tagged version of UL32 to confirm that in infected cells, this protein is mainly cytoplasmic, although some nuclear staining was observed.HSV-1 DNA replication occurs in globular nuclear domains termed “replication compartments” initially identified by ICP8 (UL29) staining patterns in an immunofluorescence assay (49). All seven replication proteins have now been localized within replication compartments (10, 24, 29–31, 43) as has regulatory protein ICP4 (26, 50). Ward et al. have recently reported that at late times after infection (18 h), capsids accumulate in the nucleus in regions distinct from replication compartments (64). These authors suggest that these regions represent assembly stations in which DNA is packaged. We report herein, however, that at 6 and 8 h postinfection, capsids colocalize with ICP8 in replication compartments. This suggests that at these early times, cleavage and packaging occur within replication compartments. Furthermore, we report that in cells infected with the UL32 mutant virus, capsids are distributed throughout the nucleus, accumulating in regions outside the replication compartments. This suggests that UL32 may play a role in the efficient localization of capsids in infected cells.     

Resistance of Human Cytomegalovirus to Benzimidazole Ribonucleosides Maps to Two Open Reading Frames: UL89 and UL56

2,5,6-Trichloro-1-β-d-ribofuranosyl benzimidazole (TCRB) is a potent and selective inhibitor of human cytomegalovirus (HCMV) replication. TCRB acts via a novel mechanism involving inhibition of viral DNA processing and packaging. Resistance to the 2-bromo analog (BDCRB) has been mapped to the UL89 open reading frame (ORF), and this gene product was proposed as the viral target of the benzimidazole nucleosides. In this study, we report the independent isolation of virus that is 20- to 30-fold resistant to TCRB (isolate C4) and the characterization of the virus. The six ORFs known to be essential for viral DNA cleavage and packaging (UL51, UL52, UL56, UL77, UL89, and UL104) were sequenced from wild-type HCMV, strain Towne, and from isolate C4. Mutations were identified in UL89 (D344E) and in UL56 (Q204R). The mutation in UL89 was identical to that previously reported for virus resistant to BDCRB, but the mutation in UL56 is novel. Marker transfer analysis demonstrated that each of these mutations individually caused ∼10-fold resistance to the benzimidazoles and that the combination of both mutations caused ∼30-fold resistance. The rate and extent of replication of the mutants was the same as for wild-type virus, but the viruses were less sensitive to inhibition of DNA cleavage by TCRB. Mapping of resistance to UL56 supports and extends recent work showing that UL56 codes for a packaging motif binding protein which also has specific nuclease activity (E. Bogner et al., J. Virol. 72:2259–2264, 1998). Resistance which maps to two different genes suggests that their putative proteins interact and/or that either or both have a benzimidazole ribonucleoside binding site. The results also suggest that the gene products of UL89 and UL56 may be antiviral drug targets.Human cytomegalovirus (HCMV) can cause significant morbidity and mortality in immunocompromised populations (3). It is a common opportunistic disease in patients with AIDS and is often a factor in their death (38). HCMV infection has been implicated in increased risk of organ rejection following heart (28) and kidney transplants (8) and in restenosis of diseased arteries following angioplasty (41, 63). It is also a leading cause of birth defects (16).Current therapies for HCMV infection include ganciclovir (GCV) (22), cidofovir (30), and foscarnet (20). Each of these drugs has several limitations to its use: none are orally bioavailable, all have dose-limiting toxicity, and resistance has developed to each (26). Because all three of these drugs inhibit viral replication through an interaction with the virally encoded DNA polymerase (25, 31, 37), the possibility of cross-resistance exists. Thus, additional drugs with unique mechanisms of action are needed for the treatment of HCMV infections.In 1995, we reported that 2-bromo-5,6-dichloro-1-(β-d-ribofuranosyl)benzimidazole (BDCRB; Fig. ​Fig.1)1) and the 2-chloro analog [2,5,6-trichloro-1-(β-d-ribofuranosyl)benzimidazole TCRB] are potent and selective inhibitors of HCMV replication (55). These compounds have a novel mechanism of action, which unlike the current therapies for HCMV infection, does not involve inhibition of DNA synthesis. The benzimidazole ribonucleosides prevent the cleavage of high-molecular-weight viral DNA concatemers to monomeric genomic lengths (57). Resistance to BDCRB has been mapped to the HCMV UL89 open reading frame (ORF), which, by analogy to gene gp17 from bacteriophage T4, may be a terminase (23, 57). Consequently, we have proposed that the benzimidazole ribonucleosides inhibit the product of this gene and that the UL89 gene product is involved in the viral DNA concatemer cleavage process (57). Open in a separate windowFIG. 1Structure of benzimidazole ribonucleosides. TCRB, R = Cl; BDCRB, R = Br.HCMV replication proceeds in a manner which is conserved among herpesviruses. The virally encoded DNA polymerase produces large, complex head-to-tail concatemers (10, 29, 33) which must be cleaved into genomic-length pieces before insertion into preformed capsids (59). With herpes simplex virus type 1 (HSV-1), temperature-sensitive mutants which are unable to cleave and package the concatemeric DNA have been derived (1, 2, 4, 45, 49, 50, 61). By this process, six HSV-1 genes have been found to be involved in concatemer cleavage and packaging. They are UL6, UL15, UL25, UL28, UL32, and UL33. In addition, recent studies in Homa’s laboratory have established that the product of UL25 is required for viral DNA encapsidation but not cleavage (39). Homologs of these genes exist in HCMV and are UL104, UL89, UL77, UL56, UL52, and UL51, respectively (18).In our continuing investigation of the mode of action of benzimidazole nucleosides, we report herein the independent isolation of HCMV strains resistant to TCRB, characterization of these strains, and identification of the mutations responsible for the development of resistance. The results demonstrate that the mechanism of action of the benzimidazole ribonucleosides is more complex than previously proposed and that a second gene product implicated in DNA cleavage and packaging is involved.     

Immunization with a Single Major Histocompatibility Complex Class I-Restricted Cytotoxic T-Lymphocyte Recognition Epitope of Herpes Simplex Virus Type 2 Confers Protective Immunity

We have evaluated the potential of conferring protective immunity to herpes simplex virus type 2 (HSV-2) by selectively inducing an HSV-specific CD8⁺ cytotoxic T-lymphocyte (CTL) response directed against a single major histocompatibility complex class I-restricted CTL recognition epitope. We generated a recombinant vaccinia virus (rVV-ES-gB498-505) which expresses the H-2K^b-restricted, HSV-1/2-cross-reactive CTL recognition epitope, HSV glycoprotein B residues 498 to 505 (SSIEFARL) (gB498-505), fused to the adenovirus type 5 E3/19K endoplasmic reticulum insertion sequence (ES). Mucosal immunization of C57BL/6 mice with this recombinant vaccinia virus induced both a primary CTL response in the draining lymph nodes and a splenic memory CTL response directed against HSV gB498-505. To determine the ability of the gB498-505-specific memory CTL response to provide protection from HSV infection, immunized mice were challenged with a lethal dose of HSV-2 strain 186 by the intranasal (i.n.) route. Development of the gB498-505-specific CTL response conferred resistance in 60 to 75% of mice challenged with a lethal dose of HSV-2 and significantly reduced the levels of infectious virus in the brains and trigeminal ganglia of challenged mice. Finally, i.n. immunization of C57BL/6 mice with either a recombinant influenza virus or a recombinant vaccinia virus expressing HSV gB498-505 without the ES was also demonstrated to induce an HSV-specific CTL response and provide protection from HSV infection. This finding confirms that the induction of an HSV-specific CTL response directed against a single epitope is sufficient for conferring protective immunity to HSV. Our findings support the role of CD8⁺ T cells in the control of HSV infection of the central nervous system and suggest the potential importance of eliciting HSV-specific mucosal CD8⁺ CTL in HSV vaccine design.

Both humoral and cell-mediated components of the immune response are involved in controlling herpes simplex virus (HSV) infection (51, 61). Studies of humans and of mice have implicated a role for both CD8⁺ (6, 25, 32, 33, 47, 65–67) and CD4⁺ (27, 37–39, 52, 53) T-lymphocyte subsets in mediating protection against HSV infection. For example, CD8⁺ T cells have been shown to be important in limiting replication of HSV in the footpad (6) and colonization of the spinal dorsal root ganglia (6, 66). In contrast, other studies using a zosteriform model of infection have primarily indicated a role for CD4⁺ T cells in the clearance of HSV (37–39). Both CD4⁺ and CD8⁺ (56, 72, 74–76) HSV-specific T lymphocytes have been detected in humans seropositive for HSV. However, the contribution of each subset in the control of HSV infection has not been clearly defined. This illustrates the controversy regarding the relative roles of each subset in the resolution of HSV infection.To address the role of the CD8⁺ T-cell subset in providing acquired immunity to HSV infection, we examined the protection afforded by HSV-specific, CD8⁺ cytotoxic T lymphocytes (CTL) directed to a single CTL recognition epitope. In previous studies by others, immunization with single CTL epitopes has been effective in controlling viral pathogens including lymphocytic choriomeningitis virus (14, 54, 62, 73), murine cytomegalovirus (15), influenza virus (55), and Sendai virus (28). Although HSV-encoded CTL recognition epitopes have been identified by their ability to serve as targets for HSV-specific CTL (3, 8, 24, 64), the ability of CTL directed to these individual epitopes to confer protection against HSV infection has not been determined. We have designed two separate vaccination strategies which permit the exclusive induction of a single HSV epitope-specific, CD8⁺ T-lymphocyte response and have evaluated the ability of this response to confer protective immunity to HSV infection.Hanke et al. (24) broadly identified an immunodominant, H-2K^b-restricted epitope within HSV glycoprotein B (gB). The minimal amino acid sequence of this epitope, gB498-505 (SSIEFARL), was demonstrated by Bonneau et al. (8), using synthetic peptides and an epitope-specific CTL clone. The amino acid sequence, SSIEFARL, is identical in both HSV type 1 (HSV-1) (gB498-505) and HSV-2 (gB496-503) (11). CTL specific for gB498-505 are readily induced by immunization with synthetic peptide (8), a cell line expressing gB498-505 in the context of simian virus 40 (SV40) T antigen (5), and a recombinant viral vector expressing this epitope in the context of a cellular protein (19). In the present study, two recombinant vaccinia viruses (rVV-ES-gB498-505 and rVV-gB498-505) and a recombinant influenza virus (WSN/NA/gB) were generated to express a single HSV-encoded epitope, HSV-1 gB498-505, and were characterized for the ability to induce a potent, HSV-specific CTL response upon mucosal immunization. To determine the protection afforded by immunization with each of the individual recombinant viruses, we used a lethal model of HSV-2 encephalitis. Our findings suggest that the induction of a CTL response directed against a single HSV-specific CTL recognition epitope is sufficient to confer significant protective immunity to HSV infection.     

An Important Role for Major Histocompatibility Complex Class I-Restricted T Cells,and a Limited Role for Gamma Interferon,in Protection of Mice against Lethal Herpes Simplex Virus Infection

Herpes simplex virus (HSV) inhibits major histocompatibility complex (MHC) class I expression in infected cells and does so much more efficiently in human cells than in murine cells. Given this difference, if MHC class I-restricted T cells do not play an important role in protection of mice from HSV, an important role for these cells in humans would be unlikely. However, the contribution of MHC class I-restricted T cells to the control of HSV infection in mice remains unclear. Further, the mechanisms by which these cells may act to control infection, particularly in the nervous system, are not well understood, though a role for gamma interferon (IFN-γ) has been proposed. To address the roles of MHC class I and of IFN-γ, C57BL/6 mice deficient in MHC class I expression (β2 microglobulin knockout [β2KO] mice), in IFN-γ expression (IFN-γKO mice), or in both (IFN-γKO/β2KO mice) were infected with HSV by footpad inoculation. β2KO mice were markedly compromised in their ability to control infection, as indicated by increased lethality and higher concentrations of virus in the feet and spinal ganglia. In contrast, IFN-γ appeared to play at most a limited role in viral clearance. The results suggest that MHC class I-restricted T cells play an important role in protection of mice against neuroinvasive HSV infection and do so largely by mechanisms other than the production of IFN-γ.

Two gene products of herpes simplex virus (HSV) block presentation of viral proteins by class I major histocompatibility complex (MHC) molecules: the viral host shutoff protein (vhs), which is present in the viral particle, and the immediate-early protein ICP47 (1, 14, 41, 42). Through the sequential action of these proteins, antigen presentation by MHC class I is inhibited early in the viral replication cycle. ICP47 binds to human transporter associated with antigen-processing proteins (TAP), thereby inhibiting peptide loading on MHC class I and recognition by HSV-specific, MHC class I-restricted, CD8⁺ T cells (1, 14, 42, 43). This effect is greatest in nonhematopoietic cells in which the abundance of MHC class I and TAP are lower than in antigen-presenting cells (41). As a consequence, HSV is more likely to impair recognition of infected target cells in the tissues than to block the generation of antigen-specific CD8⁺ T cells. Consistent with this, recent studies indicate that HSV antigen-specific CD8⁺ cytotoxic-T-lymphocyte (CTL) precursors can be readily detected in the blood and cutaneous lesions of HSV-infected individuals (16, 31, 32). However, NK cells and HSV antigen-specific CD4⁺ T cells are detected earlier than antigen-specific CD8⁺ T cells in lesions of humans with recurrent HSV-2 disease (16). This finding has led to the proposal that gamma interferon (IFN-γ) produced by infiltrating NK and CD4⁺ T cells overrides the inhibitory effects of HSV on TAP function and MHC class I expression (22, 41), thereby allowing the eradication of virus by CD8⁺ T cells, whose numbers increase in lesions around the time of viral clearance (16, 31). In patients with AIDS, a lower frequency in the blood of HSV antigen-specific CD8⁺ CTL precursors is associated with more frequent and severe recurrences of genital disease (32). These correlative data suggest that CD8⁺ T cells may play an important role in the clearance of HSV in humans, at least from mucocutaneous lesions.ICP47 inhibits murine TAP poorly (1, 42), which may explain the greater ease with which anti-HSV CD8⁺ CTLs have been detected in mice than in humans (3, 8, 28, 34, 35). Despite the weak interaction of ICP47 with murine TAP, results of a recent study (12) suggested that ICP47 impairs CD8⁺ T-cell-dependent viral clearance from the nervous system: CD8⁺ T cells protected susceptible BALB/c or A/J mice from lethal, nervous system infection with an HSV mutant lacking ICP47 but did not appear to protect against infection with wild-type HSV or to contribute to clearance of either virus from the eye. These findings are consistent with data suggesting that CD8⁺ T cells limit persistence of HSV in the spinal ganglia and decrease spread to the central nervous system (35, 36). However, other studies have concluded that CD4⁺ T cells but not CD8⁺ T cells play the critical role in viral clearance and protection from lethal primary infection with wild-type HSV (20, 23, 24) or that either CD4⁺ or CD8⁺ T cells are sufficient for protection (26, 37). Since the effects of ICP47 are likely to be greater in humans than in mice, if MHC class I-restricted CD8⁺ T cells do not play an important role in protection of mice from lethal, neuroinvasive infection due to wild-type HSV, an important role in humans would be unlikely.The mechanisms by which T cells may limit the spread of infection in the nervous system are not clearly understood. Studies by Simmons and colleagues suggested that CD8⁺ T cells may lyse infected Schwann cells or satellite cells but that they probably do not lyse infected neurons (31, 32). They and others have proposed that CD8⁺ T cells protect neurons through the production of cytokines, in particular IFN-γ (35, 36). IFN-γ contributes to the clearance of HSV from mucocutaneous sites (4, 24, 25, 37, 44). However, the role of IFN-γ in protection from lethal, neuroinvasive infection is uncertain and may vary with the strain of mice, method used to inhibit IFN-γ function, and route of inoculation (4, 5, 24, 37, 44). IFN-γ is produced in the ganglia of mice with acute or latent HSV infection (5, 13, 19). Both CD4⁺ and CD8⁺ T cells (and NK cells) produce IFN-γ, but CD4⁺ T cells appear to be the predominant source of IFN-γ following intravaginal infection with HSV (24, 25). Thus, it is possible that the disparity in results regarding the relative importance of CD4⁺ and CD8⁺ T cells in protection from lethal, neuroinvasive HSV infection reflects their redundant roles in production of this cytokine or that IFN-γ and CD8⁺ T cells contribute independently to control of infection in the nervous system.To address in parallel the contributions of MHC class I-restricted T cells and of IFN-γ to protection of mice from HSV, MHC class I and CD8⁺ T-cell-deficient β2 microglobulin knockout (β2KO) mice, IFN-γ knockout (IFN-γKO) mice, and mice deficient in both MHC class I and IFN-γ expression (IFN-γKO/β2KO) were studied. The results indicated that loss of MHC class I expression in β2KO mice substantially increased their susceptibility to HSV, whereas the loss of IFN-γ expression had a much more limited effect. These findings indicate that MHC class I-restricted T cells play an important role in protection against neuroinvasive HSV infection in mice and that they do so largely by mechanisms other than the production of IFN-γ. Though MHC class I expression is more severely impaired in β2KO mice than in human cells infected with wild-type HSV, these findings support the notion that inhibition of MHC class I expression is an important factor in the virulence of this virus.     

Analysis of Free Energy Signals Arising from Nucleotide Hybridization Between rRNA and mRNA Sequences during Translation in Eubacteria

A decoding algorithm is tested that mechanistically models the progressive alignments that arise as the mRNA moves past the rRNA tail during translation elongation. Each of these alignments provides an opportunity for hybridization between the single-stranded, -terminal nucleotides of the 16S rRNA and the spatially accessible window of mRNA sequence, from which a free energy value can be calculated. Using this algorithm we show that a periodic, energetic pattern of frequency 1/3 is revealed. This periodic signal exists in the majority of coding regions of eubacterial genes, but not in the non-coding regions encoding the 16S and 23S rRNAs. Signal analysis reveals that the population of coding regions of each bacterial species has a mean phase that is correlated in a statistically significant way with species () content. These results suggest that the periodic signal could function as a synchronization signal for the maintenance of reading frame and that codon usage provides a mechanism for manipulation of signal phase.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]     

Splitting the BLOSUM Score into Numbers of Biological Significance

Mathematical tools developed in the context of Shannon information theory were used to analyze the meaning of the BLOSUM score, which was split into three components termed as the BLOSUM spectrum (or BLOSpectrum). These relate respectively to the sequence convergence (the stochastic similarity of the two protein sequences), to the background frequency divergence (typicality of the amino acid probability distribution in each sequence), and to the target frequency divergence (compliance of the amino acid variations between the two sequences to the protein model implicit in the BLOCKS database). This treatment sharpens the protein sequence comparison, providing a rationale for the biological significance of the obtained score, and helps to identify weakly related sequences. Moreover, the BLOSpectrum can guide the choice of the most appropriate scoring matrix, tailoring it to the evolutionary divergence associated with the two sequences, or indicate if a compositionally adjusted matrix could perform better.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]     

Algorithms for Finding Small Attractors in Boolean Networks

A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in time for , which is much faster than the naive time algorithm, where is the number of genes and is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]