The modeling of complex hydrocarbon mixtures is a current issue. The presently available analytical techniques are insufficient alone to fully characterize the molecular details of heavy oil fractions to the level for new development of a molecular-level kinetic model. Stochastic reconstruction (SR) methods which build a set of molecules that mimic the properties of complex mixtures by using partial analytical data help to overcome this drawback. Although the classical SR algorithm produces reasonable molecule sets for light and medium fractions, performance degrades for heavier fractions. The main reason for this is the lack of structural parameters needed to define the variations in side-chain and ring configurations. As an extension, a novel structural parameter set including specific parameters for ring and chain configurations was implemented to the SR algorithm. In addition to this, in order to ensure an extensive structural connection between the generated molecules and the experimental data, the H-1 NMR spectrum was divided into six different regions; and these hydrogen types were used in an objective function. In order to validate the SR. with an extended parameter set, it has been applied to six different petroleum asphaltenes. The extended parameter set resulted in a decrease in the objective function value between 45% and 85% compared to the basic parameter set. Moreover, the extended parameter set increases the fitting ability of the SR algorithm without sacrificing the compositional space of the generated molecules.