bluuebunny/crossref_metadata_2025 huggingface dataset:
Algorithm 650
Authors: Johnson Kenneth C.
Published: July 2002

Two square root algorithms (for integer and floating point data types) are presented, which are
simpler and more efficient than standard procedures. These could be effectively used as the basis of
hardware-based square root generators as well as for software implementations. One possible appli-
cation for an efficient square root routine would be in calculating trigonometric and exponential
functions. (This application may be primarily of academic interest, however, since standard tran-
scendental function generators would generally be more efficient.) Three accompanying MC68000
implementations of the algorithm for 32-bit integer and IEEE single- and double-precision data are
available on the CALGO listing. These programs return rounding status in the condition code register,
and they exhibit the following approximate runtime performance at 8 MHz: 105-134 ps (integer);
180-222 ps (single precision); 558-652 ps (double precision).
An
O
(log(
n
)
4/3
) space algorithm for (
s, t
) connectivity in undirected graphs
Authors: Armoni Roy , Ta-Shma Amnon , Widgerson Avi , Zhou Shiyu
Published: July 2002

We present a deterministic algorithm that computes
st
-connectivity in undirected graphs using
O
(log
4/3
n
) space. This improves the previous
O
(log
3/2
n
) bound of Nisan et al. [1992].
A tutorial on default logics
Authors: Antoniou Grigoris
Published: July 2002

Default logic is one of the most prominent approaches to nonmonotonic reasoning, and allows one to make plausible conjectures when faced with incomplete information about the problem at hand. Default rules prevail in many application domains such as medical and legal reasoning.

Several variants have been developed over the past year, either to overcome some perceived deficiencies of the original presentation, or to realize somewhat different intuitions. This paper provides a tutorial-style introduction to some important approaches of Default Logic. The presentation is based on operational models for these approaches, thus making them easily accessible to a broader audience, and more easily usable in practical applications.
The use of interactive graphics to solve numerical problems
Authors: Smith L. B.
Published: July 2002

With the advent of on-line (time-sharing) computer systems and graphic terminals, we have available a new dimension in numerical problem solving capabilities. Rather than simply use the new power to achieve fast turnaround, we can develop interactive routines which are easy to use and also take advantage of the insight and visual capabilities of the human problem solver. Several on-line systems for general purpose mathematical problem solving have already been implemented as well as some special purpose systems for solving problems in a particular area such as ordinary differential equations. The advantage of restricting the problem area is that the interface with a user can be greatly simplified. In this paper we discuss some of the advantages accrued by such systems and design considerations for interactive routines. Furthermore, an implmentation of an on-line least squares data-fitting program, PEG, is presented with results obtained from empirical data. In conclusion, areas for future work in this field are discussed.
Algorithm 426: Merge sort algorithm [M1]
Authors: Bron C.
Published: July 2002

Sorting by means of a two-way merge has a reputation of requiring a clerically complicated and cumbersome program. This ALGOL 60 procedure demonstrates that, using recursion, an elegant and efficient algorithm can be designed, the correctness of which is easily proved [2]. Sorting
n
objects gives rise to a maximum recursion depth of [log
2
(
n
- 1) + 2]. This procedure is particularly suitable for sorting when it is not desirable to move the
n
objects physically in store and the sorting criterion is not simple. In that case it is reasonable to take the number of compare operations as a measure for the speed of the algorithm. When
n
is an integral power of 2, this number will be comprised between (
n
× log
2
n
)/2 when the objects are sorted to begin with and (
n
× log
2
n
-
n
+ 1) as an upper limit. When
n
is not an integral power of 2, the above formulas are approximate.
A scan conversion algorithm with reduced storage requirements
Authors: Jordan B. W. , Barrett R. C.
Published: July 2002

Most graphics systems using a raster scan output device (CRT or hardcopy) maintain a display file in the XY or random scan format. Scan converters, hardware or software, must be provided to translate the picture description from the XY format to the raster format. Published scan conversion algorithms which are fast will reserve a buffer area large enough to accommodate the entire screen. On the other hand, those which use a small buffer area are slow because they require multiple passes through the XY display file. The scan conversion algorithm described here uses a linked list data structure to process the lines of the drawing in strips corresponding to groups of scan lines. A relatively small primary memory buffer area is used to accumulate the binary image for a group of scan lines. When this portion of the drawing has been plotted, the buffer is reused for the next portion. Because of the list processing procedures used, only a single pass through the XY display file is required when generating the binary image and only a slight increase in execution time over the fully buffered core results. Results show that storage requirements can be reduced by more than 80 percent while causing less than a 10 percent increase in execution time.
Information retrieval on the web
Authors: Kobayashi Mei , Takeda Koichi
Published: July 2002

In this paper we review studies of the growth of the Internet and
technologies that are useful for information search and retrieval on the Web. We present data on the Internet from several different sources, e.g., current as well as projected number of users, hosts, and Web sites. Although numerical figures vary, overall trends cited by the sources are consistent and point to exponential growth in the past and in the coming decade. Hence it is not surprising that about 85% of Internet users surveyed claim using search engines and search services to find specific information. The same surveys show, however, that users are not satisfied with the performance of the current generation of search engines; the slow retrieval speed, communication delays, and poor quality of retrieved results (e.g., noise and broken links) are commonly cited problems. We discuss the development of new techniques targeted to resolve some of the problems associated with Web-based information retrieval and speculate on future trends.
Abstract data types and the development of data structures
Authors: Guttag John
Published: July 2002

Abstract data types can play a significant role in the development of software that is reliable, efficient, and flexible. This paper presents and discusses the application of an algebraic technique for the specification of abstract data types. Among the examples presented is a top-down development of a symbol table for a block structured language; a discussion of the proof of its correctness is given. The paper also contains a brief discussion of the problems involved in constructing algebraic specifications that are both consistent and complete.
Comment on a computing the k shortest paths in a graph
Authors: Lawler Eugene L.
Published: July 2002

In [1] Hardgrave discusses “positional” versus keyword parameter communication with subprograms from the viewpoint of structured programming. In this note an additional argument in favor of the keyword approach is suggested.
Reentrant polygon clipping
Authors: Sutherland Ivan E. , Hodgman Gary W.
Published: July 2002

A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie outside the volume. In two dimensions the algorithms permit clipping against irregular convex windows.

Polygons to be clipped are represented as an ordered sequence of vertices without repetition of first and last, in marked contrast to representation as a collection of edges as was heretofore the common procedure. Output polygons have an identical format, with new vertices introduced in sequence to describe any newly-cut edge or edges. The algorithms easily handle the particularly difficult problem of detecting that a new vertex may be required at a corner of the clipping window.

The algorithms described achieve considerable simplicity by clipping separately against each clipping plane or window boundary. Code capable of clipping the polygon against a single boundary is reentered to clip against subsequent boundaries. Each such reentrant stage of clipping need store only two vertex values and may begin its processing as soon as the first output vertex from the preceeding stage is ready. Because the same code is reentered for clipping against subsequent boundaries, clipping against very complex window shapes is practical.

For perspective applications in three dimensions, a six-plane truncated pyramid is chosen as the clipping volume. The two additional planes parallel to the projection screen serve to limit the range of depth preserved through the projection. A perspective projection method which provides for arbitrary view angles and depth of field in spite of simple fixed clipping planes is described. This method is ideal for subsequent hidden-surface computations.
Use of the concept of transparency in the design of hierarchically structured systems
Authors: Parnas D. L. , Siewiorek D. P.
Published: July 2002

This paper deals with the design of hierarchically structured programming systems. It develops a method for evaluating the cost of requiring programmers to work with an abstraction of a real machine. A number of examples from hardware and software are given as illustrations of the method.
Graph coloring conditions for the existence of solutions to the timetable problem
Authors: Neufeld G. A. , Tartar J.
Published: July 2002

A necessary and sufficient condition is presented for the existence of a solution to the Gotlieb class-teacher timetable problem. Several relationships are established between the class-teacher timetable problem and graphs with preconditions. These preconditions place additional restrictions on the coloration of a graph. The preconditions correspond to the unavailability constraints and preassigned meetings in the class-teacher timetable problem. Using some recent results that convert graphs with preconditions to graphs without them, it is shown that the existence of a coloration of a graph is the required necessary and sufficient condition.
On the interface between computers and data communications systems
Authors: Fraser A. G.
Published: July 2002

Future systems that combine computers, digital terminals, and communications equipment present design optimization problems that require reconsideration of the traditional functional responsibilities of the respective subsystems. Several “standard” interfaces, by means of which computers and digital terminals connect to the communications systems will be required. When specifying these interfaces, consideration must be given to problems of coordination, synchronization, error control, signaling, stream multiplexing, and switch control, in addition to minimizing the technological interdependence of specific subsystem designs. A focus on some of the problems is obtained in a discussion of a detailed specification for a paticular computer-communications system interface.
A theory of discrete patterns and their implementation in SNOBOL4
Authors: Gimpel J. F.
Published: July 2002

The notion of a discrete pattern is formalized and certain properties deduced. A pattern is shown to be a generalization of a formal language. Algorithms for implementing the kinds of patterns in SNOBOL4 are given. The general approach is to create, in-so-far as possible, a bottom-up parse from a top-down specification.
The multistore parser for hierarchical syntactic structures
Authors: von Glasersfeld Ernst , Pisani Pier Paolo
Published: July 2002

A syntactic parser is described for hierarchical concatenation patterns that are presented to the analyzer in the form of linear strings. Particular emphasis is given to the system of “significant addresses” by means of which processing times for large-scale matching procedures can be substantially reduced. The description makes frequent use of examples taken from the fully operational implementation of the parser in an experimental English sentence analyzer.

By structuring an area of the computer's central core storage in such a way that the individual locations of bytes and bits come to represent the data involved in the matching procedure, the shifting of information is reduced to a minimum, and the searching of lists is eliminated altogether. The matches are traced by means of binary masks and the state of single bits determines the operational flow of the procedure. The method could be implemented with any interpretive grammar, provided it can be expressed by the functional classification of the items composing the input hierarchical structures.
PDEL—a language for partial differential equations
Authors: Cárdenas Alfonso F. , Karplus Walter J.
Published: July 2002

Conventional computer methods available to solve continuous system problems characterized by partial differential equations are very time-consuming and cumbersome. A convenient, easy to learn and to use, high level problem oriented language to solve and study partial differential equation problems has been designed; a practical translator for the language has also been designed, and a working version of it has been constructed for a significant portion of the language. This
P
artial
D
ifferential
E
quation
L
anguage, PDEL, is outlined, and the highlights of the translator are briefly summarized.
Algorithm 447: efficient algorithms for graph manipulation
Authors: Hopcroft John , Tarjan Robert
Published: July 2002

Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If
V
is the number of vertices and
E
is the number of edges, each algorithm requires time and space proportional to max (
V, E
) when executed on a random access computer.
Experiments in automatic learning for a multipurpose hueristic program
Authors: Slagle James R. , Farrell Carl D.
Published: July 2002

An automatic learning capability has been developed and implemented for use with the MULTIPLE (
MULTI
purpose
P
rogram that
LE
arns) heuristic tree-searching program, which is presently being applied to resolution theorem-proving in predicate calculus. MULTIPLE's proving program (PP) uses two evaluation functions to guide its search for a proof of whether or not a particular goal is achievable. Thirteen general features of predicate calculus clauses were created for use in the automatic learning of better evaluation functions for PP. A multiple regression program was used to produce optimal coefficients for linear polynomial functions in terms of the features. Also, automatic data-handling routines were written for passing data between the learning program and the proving program, and for analyzing and summarizing results. Data was generally collected for learning (regression analysis) from the experience of PP.

A number of experiments were performed to test the effectiveness and generality of the learning program. Results showed that the learning produced dramatic improvements in the solutions to problems which were in the same domain as those used for collecting learning data. Learning was also shown to generalize successfully to domains other than those used for data collection. Another experiment demonstrated that the learning program could simultaneously improve performance on problems in a specific domain and on problems in a variety of domains. Some variations of the learning program were also tested.
The use of COBOL subroutines in FORTRAN main programs
Authors: Tajiri Kazuo
Published: July 2002

If a problem requires both complicated calculations and edited output printing, then the computing part can be efficiently handled in FORTRAN and the editing part, e.g. punctuation, check protect and floating dollar sign, can be conveniently done in COBOL, in particular by the PICTURE clause. The following programs illustrate the simple technique of combining FORTRAN and COBOL. The main program is written in FORTRAN and the subroutine in COBOL. The programs were run on IBM 7090.
The LACONIQ monitor
Authors: Drew Daniel L.
Published: July 2002

The LACONIQ (Laboratory Computer Online Inquiry) Monitor was developed primarily to support non-numerical applications such as retrieval from very large files by means of a “dialogue” between a system user and a retrieval application.

The monitor was designed so that it could work with a small computer (an IBM System 360/30). Therefore techniques for resource allocation were important. For this reason the use of core storage, computational facilities, and input-output were all scheduled.

An unusual feature of the system is that it is event-driven rather than clock-driven. The program segments called into execution by the remote CRT consoles are invariably run to completion rather than “rolled-out” to be brought back at a later time.
Data compression using static Huffman code-decode tables
Authors: McIntyre David R. , Pechura Michael A.
Published: July 2002

Both static and dynamic Huffman coding techniques are applied to test data consisting of 530 source programs in four different languages. The results indicate that, for small files, a savings of 22-91 percent in compression can be achieved by using the static instead of dynamic techniques.
Algorithm 811: NDA
Authors: Lukšan Ladislav , Vlček Jan
Published: July 2002

We present four basic Fortran subroutines for nondifferentiable optimization with simple bounds and general linear constraints. Subroutine PMIN, intended for minimax optimization, is based on a sequential quadratic programming variable metric algorithm. Subroutines PBUN and PNEW, intended for general nonsmooth problems, are based on bundle-type methods. Subroutine PVAR is based on special nonsmooth variable metric methods. Besides the description of methods and codes, we propose computational experiments which demonstrate the efficiency of this approach.
Managing periodically updated data in relational databases
Authors: Gal Avigdor , Eckstein Jonathan
Published: July 2002

Recent trends in information management involve the periodic transcription of data onto secondary devices in a networked environment, and the proper scheduling of these transcriptions is critical for efficient data management. To assist in the scheduling process, we are interested in modeling
data obsolescence
, that is, the reduction of consistency over time between a relation and its replica. The modeling is based on techniques from the field of stochastic processes, and provides several stochastic models for content evolution in the base relations of a database, taking referential integrity constraints into account. These models are general enough to accommodate most of the common scenarios in databases, including batch insertions and lifespans both with and without memory. As an initial "proof of concept" of the applicability of our approach, we validate the insertion portion of our model framework via experiments with real data feeds. We also discuss a set of transcription protocols that make use of the proposed stochastic model.
On the parallel Risch Algorithm (II)
Authors: Davenport J. H. , Trager B. M.
Published: July 2002

It is proved that, under the usual restrictions, the denominator of the integral of a purely logarithmic function is the expected one, that is, all factors of the denominator of the integrand have their multiplicity decreased by one. Furthermore, it is determined which new logarithms may appear in the integration.
Human-computer interface development: concepts and systems for its management
Authors: Hartson H. Rex , Hix Deborah
Published: July 2002

Human-computer interface management
, from a computer science viewpoint, focuses on the process of developing quality human-computer interfaces, including their representation, design, implementation, execution, evaluation, and maintenance. This survey presents important concepts of interface management: dialogue independence, structural modeling, representation, interactive tools, rapid prototyping, development methodologies, and control structures.
Dialogue independence
is the keystone concept upon which all the other concepts depend. It is a characteristic that separates design of the interface from design of the computational component of an application system so that modifications in either tend not to cause changes in the other. The role of a dialogue developer, whose main purpose is to create quality interfaces, is a direct result of the dialogue independence concept.
Structural models of the human-computer interface
serve as frameworks for understanding the elements of interfaces and for guiding the dialogue developer in their construction.
Representation of the human-computer interface
is accomplished by a variety of notational schemes for describing the interface. Numerous kinds of
interactive tools for human-computer interface development
free the dialogue developer from much of the tedium of "coding" dialogue. The early ability to observe behavior of the interface—and indeed that of the whole application system—provided by
rapid prototyping
increases communication among system designers, implementers, evaluators, and end-users.
Methodologies for interactive system development
consider interface management to be an integral part of the overall development process and give emphasis to evaluation in the development life cycle. Finally, several types of
control structures
govern how sequencing among dialogue and computational components is designed and executed. Numerous systems for human-computer interface management are presented t
o illustrate these concepts.
Further results on the security of partitioned dynamic statistical databases
Authors: McLeish Mary
Published: July 2002

Partitioning is a highly secure approach to protecting statistical databases. When updates are introduced, security depends on putting restrictions on the sizes of partition sets which may be queried. To overcome this problem, attempts have been made to add “dummy” records. Recent work has shown that this leads to high information loss.

This paper reconsiders the restrictions on the size of partitioning sets required to achieve a high level of security. Updates of two records at a time were studied earlier, and security was found to hold if the sizes of the partition sets were kept even. In this paper an extended model is presented, allowing very general updates to be performed. The security problem is thoroughly studied, giving if and only if conditions. The earlier result is shown to be part of a corollary to the main theorem of this paper. Alternatives to adding dummy records are presented and the practical implications of the theory for the database manager are discussed.
Model-based recognition in robot vision
Authors: Chin Roland T. , Dyer Charles R.
Published: July 2002

This paper presents a comparative study and survey of model-based object-recognition algorithms for robot vision. The goal of these algorithms is to recognize the identity, position, and orientation of randomly oriented industrial parts. In one form this is commonly referred to as the "bin-picking" problem, in which the parts to be recognized are presented in a jumbled bin. The paper is organized according to 2-D, 2½-D, and 3-D object representations, which are used as the basis for the recognition algorithms. Three central issues common to each category, namely, feature extraction, modeling, and matching, are examined in detail. An evaluation and comparison of existing industrial part-recognition systems and algorithms is given, providing insights for progress toward future robot vision systems.
Distributed discrete-event simulation
Authors: Misra Jayadev
Published: July 2002

Traditional discrete-event simulations employ an inherently sequential algorithm. In practice, simulations of large systems are limited by this sequentiality, because only a modest number of events can be simulated. Distributed discrete-event simulation (carried out on a network of processors with asynchronous message-communicating capabilities) is proposed as an alternative; it may provide better performance by partitioning the simulation among the component processors. The basic distributed simulation scheme, which uses time encoding, is described. Its major shortcoming is a possibility of deadlock. Several techniques for deadlock avoidance and deadlock detection are suggested. The focus of this work is on the theory of distributed discrete-event simulation.
Subproblem finder and instance checker, two cooperating modules for theorem provers
Authors: de Champeaux Dennis
Published: July 2002

Properties are proved about INSTANCE, a theorem prover module that recognizes that a formula is a special case and/or an alphabetic variant of another formula, and about INSURER, another theorem prover module that decomposes a problem, represented by a formula, into independent subproblems, using a conjunction. The main result of INSTANCE is soundness; the main result of INSURER is a maximum decomposition into subproblems (with some provisos). Experimental results show that a connection graph theorem prover extended with these modules is more effective than the resolution-based connection graph theorem prover alone.
Efficient implementation of graph algorithms using contraction
Authors: Gabow Harold N. , Galil Zvi , Spencer Thomas H.
Published: July 2002

The (
component
)
merging problem
is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of the problem have even more efficient solutions based on other data structures. The performance of the data structures is sped up by introducing a new algorithmic tool called
packets
.

The algorithms that use these solutions to the component merging problem also exploit new properties of two existing data structures. Specifically, Β-trees can be used simultaneously as a priority queue and a concatenable queue. Similarly, F-heaps support some kinds of split operations with no loss of efficiency.

An immediate application of the solution to the simplest version of the merging problem is an Ο(
t
(
m
,
n
)) algorithm for finding minimum spanning trees in undirected graphs
without
using F-heaps, where
t
(
m
,
n
) =
m
log
2
log
2
log
d
n
, the graph has
n
vertices and
m
edges, and
d
= max(
m
/
n
, 2). Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem.

The efficient solutions to the merging problem and the new observation about F-heaps lead to an Ο(
n
(
t
(
m
,
n
) +
n
log
n
)) algorithm for finding a maximum weighted matching in general graphs. This settles an open problem posed by Tarjan [ 15, p. 123], where the weaker bound of
O
(
nm
log (
n
2
/
m
)) was conjectured.
Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
Authors: Edelsbrunner Herbert , Mücke Ernst Peter
Published: July 2002

This paper describes a general-purpose programming technique, called Simulation of Simplicity, that can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task of providing a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those that do not use it. We believe that this technique will become a standard tool in writing geometric software.
View updates in relational databases with an independent scheme
Authors: Langerak Rom
Published: July 2002

A view on a database is a mapping that provides a user or application with a suitable way of looking at the data. Updates specified on a view have to be translated into updates on the underlying database. We study the view update translation problem for a relational data model in which the base relations may contain (indexed) nulls.

The representative instance is considered to be the correct representation of all data in the database; the class of views that is studied consists of total projections of the representative instance. Only independent database schemes are considered, that is, schemes for which global consistency is implied by local consistency. A view update can be an insertion, a deletion, or a modification of a single view tuple.

It is proven that the constant complement method of Bancilhon and Spyratos is too restrictive to be useful in this context. Structural properties of extension joins are derived that are important for understanding views. On the basis of these properties, minimal algorithms for translating a single view-tuple update are given.
Translation with optimization from relational calculus to relational algebra having aggregate functions
Authors: Nakano Ryohei
Published: July 2002

Most of the previous translations of relational calculus to relational algebra aimed at proving that the two languages have the equivalent expressive power, thereby generating very complicated relational algebra expressions, especially when aggregate functions are introduced. This paper presents a rule-based translation method from relational calculus expressions having both aggregate functions and null values to optimized relational algebra expressions. Thus, logical optimization is carried out through translation. The translation method comprises two parts: the translational of the relational calculus kernel and the translation of aggregate functions. The former uses the familiar step-wise rewriting strategy, while the latter adopts a two-phase rewriting strategy via standard aggregate expressions. Each translation proceeds by applying a heuristic rewriting rule in preference to a basic rewriting rule. After introducing SQL-type null values, their impact on the translation is thoroughly investigated, resulting in several extensions of the translation. A translation experiment with many queries shows that the proposed translation method generates optimized relational algebra expressions. It is shown that heuristic rewriting rules play an essential role in the optimization. The correctness of the present translation is also shown.

Each translation proceeds by applying a heuristic rewriting rule in preference to a basic rewriting rule. After introducing SQL-type null values, their impact on the translation is thoroughly investigated, resulting in several extensions of the translation. A translation experiment with many queries shows that the proposed translation method generates optimized relational
RECENT ADVANCES IN UNDERSTANDING LIGNIN BIOSYNTHESIS
Authors: Whetten Ross W. , MacKay John J. , Sederoff Ronald R.
Published: July 2002

▪ Abstract  After a long period of little change, the basic concepts of lignin biosynthesis have been challenged by new results from genetic modification of lignin content and composition. New techniques for making directed genetic changes in plants, as well as improvements in the analytical techniques used to determine lignin content and composition in plant cell walls, have been used in experimental tests of the accepted lignin biosynthetic pathway. The lignins obtained from genetically modified plants have shown unexpected properties, and these findings have extended the known range of variation in lignin content and composition. These results argue that the accepted lignin biosynthetic pathway is either incomplete or incorrect, or both; and also suggest that plants may have a high level of metabolic plasticity in the formation of lignins. If this is so, the properties of novel lignins could be of significant scientific and practical interest.
THE PLASTID DIVISION MACHINE
Authors: Osteryoung Katherine W , McAndrew Rosemary S
Published: July 2002

▪ Abstract  Plastid division is essential for the maintenance of plastid populations in cells undergoing division and for the accumulation of large chloroplast numbers in photosynthetic tissues. Although the mechanisms mediating plastid division are poorly understood, ultrastructural studies imply this process is accomplished by a dynamic macromolecular machine organized into ring structures at the plastid midpoint. A key component of the engine that powers this machine is the motor-like protein FtsZ, a cytoskeletal GTPase of endosymbiotic origin that forms a ring at the plastid division site, similar to the function of its prokaryotic relatives in bacterial cytokinesis. This review considers the phylogenetic distribution and structural properties of two recently identified plant FtsZ protein families in the context of their distinct roles in plastid division and describes current evidence regarding factors that govern their placement at the division site. Because of their evolutionary and mechanistic relationship, the process of bacterial cell division provides a valuable, though incomplete, paradigm for understanding plastid division in plants.
Standard Cosmology and Alternatives: A Critical Appraisal
Authors: Narlikar Jayant V. , Padmanabhan T.
Published: July 2002

▪ Abstract  This review takes a critical look at the cosmological scenario at the turn of the century by examining the available cosmological models in the light of the present observational evidence. The center stage is held by the big bang models, which are collectively referred to here as standard cosmology (SC) and its extensions. SC itself is characterized by a seven parameter set of models based on Einstein's general theory of relativity. The seven parameters are H0, ΩB, ΩDM, ΩΛ, ΩR (describing the background universe, and A, n (specifying the amplitude and power law index of initial fluctuation spectrum). The extended SC includes extrapolations of the SC to earlier epochs when the mean energies of the particles were greater than about 100 GeV. The strength of the SC is seen to lie in its successful prediction of the expansion of the universe, the abundance of light nuclei, and the spectrum and anisotropies of the cosmic microwave background (CMBR). The SC has led to a whole class of theories of structure formation, which are, in principle, testable observationally. The subject of twentieth century cosmology gained considerably from occasional ideas different from the SC; some of these are briefly outlined and placed in historical perspective. Currently there is only one alternative cosmology, the quasi steady state cosmology (QSSC), that has been developed to a stage where it can be compared with observations and also with the SC. Although the SC does appear quite successful, there are still many unresolved issues that keep the cosmological scene fairly open.
PROTEIN FOLDING: The Endgame
Authors: Levitt Michael , Gerstein Mark , Huang Enoch , Subbiah S. , Tsai Jerry
Published: July 2002

The last stage of protein folding, the “endgame,” involves the ordering of amino acid side-chains into a well defined and closely packed configuration. We review a number of topics related to this process. We first describe how the observed packing in protein crystal structures is measured. Such measurements show that the protein interior is packed exceptionally tightly, more so than the protein surface or surrounding solvent and even more efficiently than crystals of simple organic molecules. In vitro protein folding experiments also show that the protein is close-packed in solution and that the tight packing and intercalation of side-chains is a final and essential step in the folding pathway. These experimental observations, in turn, suggest that a folded protein structure can be described as a kind of three-dimensional jigsaw puzzle and that predicting side-chain packing is possible in the sense of solving this puzzle. The major difficulty that must be overcome in predicting side-chain packing is a combinatorial “explosion” in the number of possible configurations. There has been much recent progress towards overcoming this problem, and we survey a variety of the approaches. These approaches differ principally in whether they use ab initio (physical) or more knowledge-based methods, how they divide up and search conformational space, and how they evaluate candidate configurations (using scoring functions). The accuracy of side-chain prediction depends crucially on the (assumed) positioning of the main-chain. Methods for predicting main-chain conformation are, in a sense, not as developed as that for side-chains. We conclude by surveying these methods. As with side-chain prediction, there are a great variety of approaches, which differ in how they divide up and search space and in how they score candidate conformations.
THE MOLECULAR CONTROL OF CIRCADIAN BEHAVIORAL RHYTHMS AND THEIR ENTRAINMENT IN DROSOPHILA
Authors: Young Michael W.
Published: July 2002

Molecular and genetic characterizations of circadian rhythms in Drosophila indicate that function of an intracellular pacemaker requires the activities of proteins encoded by three genes: period (per), timeless (tim), and doubletime (dbt). RNA from two of these genes, per and tim, is expressed with a circadian rhythm. Heterodimerization of PER and TIM proteins allows nuclear localization and suppression of further RNA synthesis by a PER/TIM complex. These protein interactions promote cyclical gene expression because heterodimers are observed only at high concentrations of, per and tim RNA, separating intervals of RNA accumulation from times of PER/TIM complex activity. Light resets these molecular cycles by eliminating TIM. The product of dbt also regulates accumulation of per and tim RNA, and it may influence action of the PER/TIM complex. The recent discovery of PER homologues in mice and humans suggests that a related mechanism controls mammalian circadian behavioral rhythms.
Regulation of Phosphoinositide-Specific Phospholipase C
Authors: Rhee Sue Goo
Published: July 2002

▪ Abstract  Eleven distinct isoforms of phosphoinositide-specific phospholipase C (PLC), which are grouped into four subfamilies (β, γ, δ, and ∍), have been identified in mammals. These isozymes catalyze the hydrolysis of phosphatidylinositol 4,5-bisphosphate [PtdIns(4,5)P2] to inositol 1,4,5-trisphosphate and diacylglycerol in response to the activation of more than 100 different cell surface receptors. All PLC isoforms contain X and Y domains, which form the catalytic core, as well as various combinations of regulatory domains that are common to many other signaling proteins. These regulatory domains serve to target PLC isozymes to the vicinity of their substrate or activators through protein-protein or protein-lipid interactions. These domains (with their binding partners in parentheses or brackets) include the pleckstrin homology (PH) domain [PtdIns(3)P, βγ subunits of G proteins] and the COOH-terminal region including the C2 domain (GTP-bound α subunit of Gq) of PLC-β; the PH domain [PtdIns(3,4,5)P3] and Src homology 2 domain [tyrosine-phosphorylated proteins, PtdIns(3,4,5)P3] of PLC-γ; the PH domain [PtdIns(4,5)P2] and C2 domain (Ca2+) of PLC-δ; and the Ras binding domain (GTP-bound Ras) of PLC-∍. The presence of distinct regulatory domains in PLC isoforms renders them susceptible to different modes of activation. Given that the partners that interact with these regulatory domains of PLC isozymes are generated or eliminated in specific regions of the cell in response to changes in receptor status, the activation and deactivation of each PLC isoform are likely highly regulated processes.
DNA Primases
Authors: Frick David N. , Richardson Charles C.
Published: July 2002

▪ Abstract  DNA primases are enzymes whose continual activity is required at the DNA replication fork. They catalyze the synthesis of short RNA molecules used as primers for DNA polymerases. Primers are synthesized from ribonucleoside triphosphates and are four to fifteen nucleotides long. Most DNA primases can be divided into two classes. The first class contains bacterial and bacteriophage enzymes found associated with replicative DNA helicases. These prokaryotic primases contain three distinct domains: an amino terminal domain with a zinc ribbon motif involved in binding template DNA, a middle RNA polymerase domain, and a carboxyl-terminal region that either is itself a DNA helicase or interacts with a DNA helicase. The second major primase class comprises heterodimeric eukaryotic primases that form a complex with DNA polymerase alpha and its accessory B subunit. The small eukaryotic primase subunit contains the active site for RNA synthesis, and its activity correlates with DNA replication during the cell cycle.
A Dedication in Memoriam of Dr. Richard Skalak
Authors: Skalak Thomas C.
Published: July 2002

▪ Abstract  [Formula: see text] Richard Skalak (1923–1997) played a leadership role in the formative decades of the discipline of biomedical engineering through his technical contributions in biomechanics, his educational influence on students, and his service to many developing societies and journals. But always, the distinguishing marks of his involvement with any activity or person were his generosity, respect and tolerance for others, integrity, and curiosity. These very qualities are what first brought him as a traditional engineer trained in engineering mechanics into the young field of biomedical engineering in the 1960s, and they are what led him to new approaches to cellular and molecular engineering, tissue engineering, and orthopedic biomechanics. His technical papers and lectures on blood cell mechanics, pulmonary circulation, dental implants, and tissue growth were models of clarity and often pointed the way to new areas of exploration, while his personal writings offer advice on life, academic organizations, and the pursuit of significant work. He would be deeply appreciative that this first volume of the Annual Review of Biomedical Engineering is dedicated to his memory.
Magnetic Resonance Studies of Brain Function and Neurochemistry
Authors: Uğurbil Kâmil , Adriany Gregor , Andersen Peter , Chen Wei , Gruetter Rolf , Hu Xiaoping , Merkle Hellmut , Kim Dae-Shik , Kim Seong-Gi , Strupp John , Zhu Xiao Hong , Ogawa Seiji
Published: July 2002

▪ Abstract  In the short time since its introduction, magnetic resonance imaging (MRI) has rapidly evolved to become an indispensable tool for clinical diagnosis and biomedical research. Recently, this methodology has been successfully used for the acquisition of functional, physiological, and biochemical information in intact systems, particularly in the human body. The ability to map areas of altered neuronal activity in the brain, often referred to as functional magnetic resonance imaging (fMRI), is probably one of the most significant recent achievements that rely on this methodology. This development has permitted the examination of functional specialization in human and animal brains with unprecedented spatial resolution, as demonstrated by mapping at the level of orientation and ocular dominance columns in the visual cortex. These functional imaging studies are complemented by the ability to study neurochemistry using magnetic resonance spectroscopy, allowing the determination of metabolic processes that support neurotransmission and neurotransmission rates themselves.
Thomas McMahon: A Dedication in Memoriam
Authors: Howe Robert D. , Kronauer Richard E.
Published: July 2002

[Figure: see text]

▪ Abstract  Thomas A. McMahon (1943–1999) was a pioneer in the field of biomechanics. He made primary contributions to our understanding of terrestrial locomotion, allometry and scaling, cardiac assist devices, orthopedic biomechanics, and a number of other areas. His work was frequently characterized by the use of simple mathematical models to explain seemingly complex phenomena. He also validated these models through creative experimentation. McMahon was a successful inventor and also published three well-received novels. He was raised in Lexington, Massachussetts, attended Cornell University as an undergraduate, and earned a PhD at MIT. From 1970 until his death, he was a member of the faculty of Harvard University, where he taught biomedical engineering. He is fondly remembered as a warm and gentle colleague and an exemplary mentor to his students.
Protein Folding Theory: From Lattice to All-Atom Models
Authors: Mirny Leonid , Shakhnovich Eugene
Published: July 2002

▪ Abstract  This review focuses on recent advances in understanding protein folding kinetics in the context of nucleation theory. We present basic concepts such as nucleation, folding nucleus, and transition state ensemble and then discuss recent advances and challenges in theoretical understanding of several key aspects of protein folding kinetics. We cover recent topology-based approaches as well as evolutionary studies and molecular dynamics approaches to determine protein folding nucleus and analyze other aspects of folding kinetics. Finally, we briefly discuss successful all-atom Monte-Carlo simulations of protein folding and conclude with a brief outlook for the future.
The Developmental and Molecular Biology of Genes that Subdivide the Body of Drosophila
Authors: Mann Richard S. , Morata Ginés
Published: July 2002

▪ Abstract  During the past decade, much progress has been made in understanding how the adult fly is built. Some old concepts such as those of compartments and selector genes have been revitalized. In addition, recent work suggests the existence of genes involved in the regionalization of the adult that do not have all the features of selector genes. Nevertheless, they generate morphological distinctions within the body plan. Here we re-examine some of the defining criteria of selector genes and suggest that these newly characterized genes fulfill many, but not all, of these criteria. Further, we propose that these genes can be classified according to the domains in which they function. Finally, we discuss experiments that address the molecular mechanisms by which selector and selector-like gene products function in the fly.
UPS AND DOWNS IN PLANETARY SCIENCE
Authors: Shoemaker Carolyn S.
Published: July 2002

[Figure: see text]

▪ Abstract  The field of planetary science as it developed during the lifetimes of Gene and Carolyn Shoemaker has sustained a period of exciting growth. Surveying the skies for planet-crossing asteroids and comets and studying the results of their impact upon the planets, especially the Earth, was for Gene and Carolyn an intense and satisfying quest for knowledge. It all started when Gene envisioned man going to the Moon, especially himself. After that, one thing led to another: the study of nuclear craters and a comparison with Meteor Crater, Arizona; the Apollo project and a succession of unmanned space missions to the inner and outer planets; an awareness of cratering throughout our solar system; the search for near-Earth asteroids and comets; a study of ancient craters in Australia; and the impact of Shoemaker-Levy 9 on Jupiter. The new paradigm of impact cratering as a cause for mass extinction and the opening of space for the development of new life forms have been causes to champion.